UVa 10663 Non-Powerful Subsets-洪萨配资

题目描述

我们定义一个自然数子集为“非幂集”，如果该子集中不存在任何子集（可以是它本身）使得其元素之和等于某个幂数。这里的幂数定义为：对于所有NNN和M≥2M \geq 2M≥2，形如NMN^MNM的数。注意，111不被视为幂数。

给定整数aaa和bbb，我们的目标是找出区间[a,b][a, b][a,b]中满足上述性质的第一个最大子集。子集XXX排在YYY前面，如果XXX中至少存在一个元素小于或等于YYY中的每个元素。如果第一个值相同，则输出第二个值更小的解，依此类推。一个子集被称为“最大的”，如果不能再向其中添加任何元素而不破坏性质。

输入格式

输入文件包含多个测试用例，每行一个。每个测试用例包含两个整数aaa和bbb，满足1≤a≤b≤10001 \leq a \leq b \leq 10001≤a≤b≤1000。输入以EOF\texttt{EOF}EOF结束。

输出格式

对于每个输入，输出一行，包含属于该子集的数字，按升序排列并用空格分隔。子集至少包含一个元素。

样例输入

2 3 3 20 4 28

样例输出

2 3 3 7 10 11 5 6 7 17 28

题目分析与解题思路

问题理解

我们需要在区间[a,b][a, b][a,b]中找到一个满足以下条件的子集：

非幂性：子集的任何子集（包括自身）的元素之和不能是幂数。
最大性：不能再向该子集中添加任何[a,b][a, b][a,b]中的元素而不破坏非幂性。
字典序最小：在所有最大子集中，选择“第一个”最大的子集，即按题目定义的偏序关系最小的子集。

题目中的偏序定义可以理解为：比较两个子集排序后的元素序列，按字典序比较，选择较小的那个。

关键观察

幂数定义：幂数是形如NMN^MNM的数，其中N≥2N \geq 2N≥2，M≥2M \geq 2M≥2，且111不是幂数。在区间[1,1000][1, 1000][1,1000]中，幂数包括4,8,9,16,25,27,32,36,49,64,81,100,…4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, \ldots4,8,9,16,25,27,32,36,49,64,81,100,…等。
单个元素的限制：如果某个数本身就是幂数，那么它绝对不能出现在子集中，因为单个元素就构成了一个子集，其和就是该幂数。
组合限制：对于子集中的任意多个元素，它们的和不能是幂数。这意味着我们需要避免某些数字组合。

解题策略

由于题目要求的是字典序最小的极大子集，我们可以采用贪心策略：

按升序处理数字：从aaa到bbb依次考虑每个数字。
检查能否加入：对于当前数字nnn，检查如果将其加入当前子集，是否会与现有元素形成幂数和。
加入决策：如果能安全加入，则加入；否则跳过。
继续处理：处理下一个数字，直到区间结束。

这样得到的子集就是字典序最小的极大子集，因为：

我们总是优先考虑较小的数字
一旦能加入就加入，确保得到的子集在字典序上尽可能小
最终得到的子集是极大的，因为后续数字都不能再加入

检查安全性的方法

我们需要高效地检查加入数字nnn是否会破坏非幂性。设当前子集的所有可能的子集和为集合SSS（包括空集和000）。加入数字nnn后，新的子集和集合将变为S∪{n}∪{s+n∣s∈S}S \cup \{n\} \cup \{s + n \mid s \in S\}S∪{n}∪{s+n∣s∈S}。

检查安全性的条件为：

nnn本身不是幂数
对于所有s∈Ss \in Ss∈S，s+ns + ns+n不是幂数

由于b≤1000b \leq 1000b≤1000，最大可能的子集和不超过1000×1000/2=5005001000 \times 1000 / 2 = 5005001000×1000/2=500500，我们可以预处理所有不超过500500500500500500的幂数。

算法步骤

预处理幂数：生成所有不超过500500500500500500的幂数。
对于每个测试用例：
- 初始化当前子集和集合S={0}S = \{0\}S={0}（空集的和）
- 初始化结果集合R=∅R = \emptysetR=∅
- 对于nnn从aaa到bbb：
  - 如果nnn是幂数，跳过
  - 检查对于所有s∈Ss \in Ss∈S，s+ns + ns+n是否是幂数
  - 如果没有冲突，将nnn加入RRR，并更新S=S∪{n}∪{s+n∣s∈S}S = S \cup \{n\} \cup \{s + n \mid s \in S\}S=S∪{n}∪{s+n∣s∈S}
- 输出RRR

复杂度分析

预处理幂数：O(Mlog⁡M)O(\sqrt{M} \log M)O(MlogM)，其中M=500500M = 500500M=500500，可以接受。
每个测试用例：
- 最多处理100010001000个数字
- 每次检查时，SSS的大小最多约100010001000（实际上更少，因为很多和会重复）
- 总操作约1000×1000=1061000 \times 1000 = 10^61000×1000=106次，加上集合操作，可以在时限内完成。

实现细节

使用unordered_set存储当前子集和集合，实现O(1)O(1)O(1)的平均查找和插入。
使用两个unordered_set交替更新，避免频繁复制。
预处理幂数数组，实现O(1)O(1)O(1)的幂数检查。

参考代码

// Non-Powerful Subsets// UVa ID: 10663// Verdict: Accepted// Submission Date: 2025-12-15// UVa Run Time: 0.620s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAXSUM=500600;boolisPower[MAXSUM];intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);// 预处理所有幂数（N^M，N>=2，M>=2）for(intn=2;n*n<MAXSUM;n++){intv=n*n;while(v<MAXSUM){isPower[v]=true;v*=n;}}inta,b;while(cin>>a>>b){unordered_set<int>sums[2];// 两个集合交替使用vector<int>r;// 结果集合intu=0,v=1;// 当前和下一个集合的索引for(intn=a;n<=b;n++){if(isPower[n])continue;// n本身是幂数，跳过// 检查是否安全：对于所有当前和s，s+n不能是幂数boolsafe=true;for(autos:sums[u]){if(isPower[s+n]){safe=false;break;}}if(!safe)continue;// 安全，加入结果r.push_back(n);// 更新子集和集合sums[v].clear();for(autos:sums[u]){sums[v].insert(s);sums[v].insert(s+n);}sums[v].insert(n);// 交换当前和下一个集合swap(u,v);}// 输出结果if(!r.empty()){cout<<r[0];for(size_t i=1;i<r.size();++i){cout<<' '<<r[i];}}cout<<'\n';}return0;}