2026UPC暑假训练赛第八场

A题唐克老师最近学习了一种有趣的题型——《构造题》这种题目是根据题意去构造一组符合规则的输出有的是序列有的是数据结构有的是图和树今天唐克老师做了一道基础的题目这道题的要求如下以下提到的 i,j 满足均 i j1. 构造一个尽可能长的数组 ai在数组中不能有数字重复出现并且要保证数组元素是升序的即 ai aj2. 当数组的元素个数 ≥ 2 时对于任意一组 i,j 满足 aj % ai 03. 对于任意元素 ai 满足 L ≤ ai ≤ R现在唐克老师已经完成了这道题但是他不知道他的结果是否正确所以他希望你帮他计算一下两个问题1. 最长数组的长度应该是多少2. 有多少种符合长度最长的数组构造方案观察题目长度最优考虑a,2*a,4*a,8*a据此可算出最长长度对于所有方案的枚举假设当前是第i个数如果这个数字b满足b(cnt-i)r,cnt是最大长度即满足于是对于每种情况做最小枚举即可代码如下#include bits/stdc.h using namespace std; int ans 0; void search(int x, int l, int r, int cnt) { if (cnt 0) { ans; return; } for (int i 2 * x; (i (cnt - 1)) r; i x) { search(i, l, r, cnt - 1); } }//递推 int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin t; while (t--) { int l, r; cin l r; int o r, cnt 0; for (; o l; o 1) cnt; for (int i l; (i (cnt - 1)) r; i) { search(i, l, r, cnt - 1); } cout cnt ans \n; ans 0; } }A有更妙的解法对于因子大于2的只能是3所有大于4的都2*2本来可以拆成两个如果有4只能说明长度算错了而且只能一个33*32*2*2可以拆成多个下面给出O1做法#includebits/stdc.h using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cint; while(t--) { long long l,r; cinlr; long long cnt0; long long xl; while(xr)cnt,x1; long long Ar/(1(cnt-1))-l1;//都是2 if(A0)A0;//cnt-1代表起始的可以很小长度是cnt迭代了cnt-1次 long long B0; if(cnt2) { long long dm3*(1(cnt-2));//一个3 Br/dm-l1; } if(B0)B0; long long ansAB*(cnt-1); coutcnt ans\n; } }B众所周知唐克老师热衷于给班级的同学们排座位希望以此来促进同学们的学习这天唐克老师又有了一个新的座位思路——让成绩好的同学和成绩差的同学交叉着坐是不是就可以让成绩差的同学更好的向成绩好的同学学习让成绩好的同学更好的帮助成绩差的同学呢现在唐克老师已经把前 n 位同学的座位排好了但是他发现好像座位排的有点问题于是唐克老师决定重新设定要求他认为只要对于第 i 位同学来说要么他左右两侧的同学成绩都比他好要么左右两侧的同学成绩都比他差那么就满足唐克老师的要求当然这里头尾两位同学不需要满足上述条件现在唐克老师想知道如果他有足够多任意成绩的同学最少需要替换这 n 个同学中的几个人可以使得这个座位满足唐克老师的要求显然分两种情况第一个为好学生和差学生即可注意我们计算答案要考虑数值更替也就是如果i是差生cnt[i],代表i之前处理好的次数如果i1比i差可以把i1变成1e9,对于i1更有利(因为差生优生一定交替)这是思考过程体现在代码上可以直接跳到i2,但是题目数据给的1-1e9对于多个1和多个1e9需要特判代码如下#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin n; vectorint a(n); int _0 0, _1 0; for (int i 0; i n; i) cin a[i]; vectorint num_0(a), num_1(a); for (int i 0; i n; i) { if (i % 2 0) { // 弱 if (i 1 n num_0[i 1] num_0[i]) { if (num_0[i 1] ! 1e9num_0[i]!1e9) num_0[i 1] 1e9; _0; } } else { // 强 if (i 1 n num_0[i 1] num_0[i]) { if (num_0[i 1] ! 1num_0[i1]!1) num_0[i 1] 1; _0; } } } for (int i 0; i n; i) { if (i % 2 0) // qiang { if (i 1 n num_1[i 1] num_1[i]) { if (num_1[i 1] ! 1num_1[i1]!1) num_1[i 1] 1; _1; } } else { if (i 1 n num_1[i 1] num_1[i]) { if (num_1[i 1] ! 1e9num_1[i1]!1e9) num_1[i 1] 1e9; _1; } } } cout min(_0, _1) \n; }C最近又开始流行串姓名手串了店家会把刻有单个字或者字母的小珠子摆在篮子里然后大家可以找自己的名字或者自己想要的珠子最后把珠子串起来组成一条手串而唐克老师今天心血来潮决定也来玩一玩但是由于中文珠子不好找于是他决定使用 xls 三个字母现在唐克老师一共从篮子里找出 n 颗刻有 x,l,s 三个字母之一的珠子并且摆成了一排现在唐克老师准备从中拿出一些珠子组成他的名字—— xls但是由于珠子比较多所以唐克老师懒得将它们重新排序了他只会用从排列顺序依次为 x,l,s 的三颗珠子来组成一个手串形式化的我们可以理解为能够组成手串的三颗珠子编号为 i,j,k那么必须要满足 i j k并且 ai x, aj l, aks例如 xxllssslx唐克老师可以取出 1,3,5 这三颗珠子组成一串手串用 2,4,6 这三颗珠子组成另一串手串而剩下 7,8,9 三个珠子为 slx 没办法组成一个手串计数即可不过多赘述#includebits/stdc.h using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); string s; cins; int x0,l0,s_0; int xl0; int ans0; for(int i0;is.size();i) { if(s[i]x)x; else if(s[i]l) { if(x0) { l--,x--; xl; } } else { if(xl0) { xl--; ans; } } } coutans\n; }D唐克老师认为每个数字都拥有或多或少的力量而一个数字拥有的力量多少取决于它每一位的数字和例如 123 拥有的力量就是 1236现在唐克老师想知道如果给定一个区间 [l,r] 在这个区间内力量值最大的数是多少它的力量值是几l与r的差值小于等于1e5枚举即可复杂度1e6#includebits/stdc.h using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); long long l,r; cinlr; long long max_0,max_num; for(long long ir;il;i--) { long long now0,curi; while(cur)nowcur%10,cur/10; if(nowmax_)max_now,max_numi; } coutmax_num\nmax_\n; }问题 IDiff-prime Pairs题目描述Eddy has solved lots of problem involving calculating the number of coprime pairs within some range. This problem can be solved with inclusion-exclusion method. Eddy has implemented it lots of times. Someday, when he encounters another coprime pairs problem, he comes up with diff-prime pairs problem. diff-prime pairs problem is that given N, you need to find the number of pairs (i, j), where and are both prime and i ,j ≤ N. gcd(i, j) is the greatest common divisor of i and j. Prime is an integer greater than 1 and has only 2 positive divisors.Eddy tried to solve it with inclusion-exclusion method but failed. Please help Eddy to solve this problem.Note that pair (i1, j1) and pair (i2, j2) are considered different if i1 ≠ i2 or j1 ≠ j2.总的来说题干是要求除以最大公因数后为两个质数的数对及求符合要求的合数成对排列数那么我们可以转化为先求质数然后找某个因子下质数的数量计算方案cnt*(cnt-1)/2相加即可对于n1e7埃氏筛即可在有序的质数数组中进行二分查找(双指针也可以并且肯定不会TIE)#includebits/stdc.h using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); vectorint a(1e7 1); a[0] a[1] 1; for (int i 2; i * i 1e7; i) { for (int j i * i; j 1e7; j i) { a[j] 1; } } vectorlong long prime; int n; cin n; for (int i 2; i n; i) if (!a[i]) prime.push_back(i); long long ans 0; for (long long i 1; i n / 3; i) { long long cnt 0; long long left 0, right prime.size() - 1; if (i 1) { cnt right 1; ans (cnt - 1) * cnt; continue; } while (left right) { long long mid left (right - left 1) / 2; if (prime[mid] * i n) left mid; else right mid - 1; } cnt left 1; ans (cnt - 1) * cnt; } cout ans \n; }