用me做后缀的网站沈阳有什么网站

用me做后缀的网站,沈阳有什么网站,北京的建筑设计公司,做网站用什么主题题目描述 我们定义一个自然数子集为“非幂集”#xff0c;如果该子集中不存在任何子集#xff08;可以是它本身#xff09;使得其元素之和等于某个幂数。这里的幂数定义为#xff1a;对于所有 NNN 和 M≥2M \geq 2M≥2 #xff0c;形如 NMN^MNM 的数。注意#xff0c; 11…题目描述我们定义一个自然数子集为“非幂集”如果该子集中不存在任何子集可以是它本身使得其元素之和等于某个幂数。这里的幂数定义为对于所有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≥2M≥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}∪{sn∣s∈S}S \cup \{n\} \cup \{s n \mid s \in S\}S∪{n}∪{sn∣s∈S}。检查安全性的条件为nnn本身不是幂数对于所有s∈Ss \in Ss∈Ssns nsn不是幂数由于b≤1000b \leq 1000b≤1000最大可能的子集和不超过1000×1000/25005001000 \times 1000 / 2 5005001000×1000/2500500我们可以预处理所有不超过500500500500500500的幂数。算法步骤预处理幂数生成所有不超过500500500500500500的幂数。对于每个测试用例初始化当前子集和集合S{0}S \{0\}S{0}空集的和初始化结果集合R∅R \emptysetR∅对于nnn从aaa到bbb如果nnn是幂数跳过检查对于所有s∈Ss \in Ss∈Ssns nsn是否是幂数如果没有冲突将nnn加入RRR并更新SS∪{n}∪{sn∣s∈S}S S \cup \{n\} \cup \{s n \mid s \in S\}SS∪{n}∪{sn∣s∈S}输出RRR复杂度分析预处理幂数O(Mlog⁡M)O(\sqrt{M} \log M)O(M​logM)其中M500500M 500500M500500可以接受。每个测试用例最多处理100010001000个数字每次检查时SSS的大小最多约100010001000实际上更少因为很多和会重复总操作约1000×10001061000 \times 1000 10^61000×1000106次加上集合操作可以在时限内完成。实现细节使用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//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXSUM500600;boolisPower[MAXSUM];intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);// 预处理所有幂数N^MN2M2for(intn2;n*nMAXSUM;n){intvn*n;while(vMAXSUM){isPower[v]true;v*n;}}inta,b;while(cinab){unordered_setintsums[2];// 两个集合交替使用vectorintr;// 结果集合intu0,v1;// 当前和下一个集合的索引for(intna;nb;n){if(isPower[n])continue;// n本身是幂数跳过// 检查是否安全对于所有当前和ssn不能是幂数boolsafetrue;for(autos:sums[u]){if(isPower[sn]){safefalse;break;}}if(!safe)continue;// 安全加入结果r.push_back(n);// 更新子集和集合sums[v].clear();for(autos:sums[u]){sums[v].insert(s);sums[v].insert(sn);}sums[v].insert(n);// 交换当前和下一个集合swap(u,v);}// 输出结果if(!r.empty()){coutr[0];for(size_t i1;ir.size();i){cout r[i];}}cout\n;}return0;}总结本题的关键在于理解题目要求的是字典序最小的极大子集而不是大小最大的子集。通过贪心策略按升序处理数字并检查加入后是否与现有元素形成幂数和我们可以高效地得到正确答案。使用unordered_set存储子集和集合以及预处理幂数数组是算法高效运行的关键。该算法的时间复杂度为O((b−a1)⋅∣S∣)O((b-a1) \cdot |S|)O((b−a1)⋅∣S∣)其中∣S∣|S|∣S∣是当前子集和集合的大小对于题目范围完全可行。