2026勰码金牌夏令营济南A-营模拟赛一补题报告S12316 明宗亮一、比赛过程1、赛前估分赛前估分T1 分面包T2 快速筛因子算法T3 代价T4 跳房子总分80 pts40 pts10 pts10 pts140 pts2、实际分数实际分数T1 分面包T2 快速筛因子算法T3 代价T4 跳房子总分100 pts35 pts10 pts10 pts155 pts3、赛时简述这一次比赛满分400分我得了155分发挥的很好。但是在一些知识上让暴露出了不足。第一题开门暴击死磕了半个小时后没思路本来想骗分结果骗分过程把我的思路打开了写了个dfs直接AC。第二题数学题比赛时打了的表推了一下大概能干到就打了很暴力的暴力结果不知道咋了被卡掉了5分。第三题也是一个数学题难度比第二题难了亿点点有很多的优化技巧感觉自身知识储备还是太少了啥也不会比赛时打了一个暴搜拿下部分分。第四题一道数据结构题比赛时想拿到30分的部分分但是有一层循环始终优化不掉时间复杂度,只拿到了十分。二、题目分析T1、分面包/bread1、题目大意2、赛时思路比赛时第一眼二分答案写着写着发现不对劲第二眼深搜写着写着又发现不对劲然后走投无路开始骗分打完了骗分的DFS后发现了正解思路就完善了一下代码。因为面包最终的大小肯定比所有的都小所以我们直接从开始逆序枚举这样的好处是第一个找到的符合条件的数就是最终的面包大小避免了大量的无效枚举。理论来说这样做最差的时间复杂度最差是但是经测试最终的结果如下所以实际上这种做法的时间复杂度要比理论上快很多主要是因为 逆序枚举剪枝 节省了不少时间。对于特殊性质测试点7进行特判统计每个数的k并通过计算得出p是多少。找出对于每个数的k最小的k是多少设他为q接着算出所有k-q的和记他为sum则需要做sum次操作每个面包最大是。3、正解赛时代码#includebits/stdc.h #define int long long using namespace std; const int N1e55; int Y[N]; int n,a[N],b[N];//b[i]表示下标i除以2的次数 int minn1e18; //setint st; int num1e18; int sinn; bool check7(){ int tota[1]; for(int i2;in;i){ if(a[i]!tot) return false; } return true; } //bool flag0; //void dfs(int n,int step){ // if(n2){ // nummin(num,step); // return ; // } // if(n2) return ; // if(n%20) dfs(n/2,step1); // else{ // dfs(n/2,step1); // dfs(n/21,step1); // } //} void dfs2(int n,int step){ if(nsinn){ nummin(num,step); // flag1; return ; } if(nsinn) return ; if(n%20) dfs2(n/2,step1); else{ dfs2(n/2,step1); dfs2(n/21,step1); } } //bool check(int n){ // if(flag) return true; // if(dfs(n)-1) return false; // else return true; //} signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); freopen(bread.in,r,stdin); freopen(bread.out,w,stdout); cinn; for(int i1;in;i){ cina[i]; Y[i]a[i]; minnmin(minn,a[i]); // st.insert(a[i]); while(a[i]%20){ a[i]/2; b[i]; } // maxxmax(maxx,a[i]); } if(check7()){ int minnn1e18,sum0; for(int i1;in;i){ minnnmin(minnn,b[i]); } for(int i1;in;i){ sum(b[i]-minnn); } coutsum a[1]*(1minnn); return 0; } for(int i1;in;i){ a[i]Y[i]; // st.insert(a[i]); // t[a[i]]; } int ans0; // for(int i1;in;i){ // dfs(a[i],0); // ansnum; // num1e18; // } // coutans 2; for(int iminn;i1;i--){ sinni; ans0; // flag0; for(int j1;jn;j){ num1e18; // flag0; dfs2(a[j],0); if(num1e18) break; // coutnum\n; ansnum; if(jn){ coutans i; return 0; } } } // if(st.size()6){ // int res0; // for(auto i:st){ // c[res]i; // } // // } // for(int i1;in;i){ // if() // } // int l1,rmaxx1; // while(lr){ // int mid(lr)/2; // if(check(mid)) lmid1; // else rmid; // } // coutl; return 0; }T2、快速筛因子算法/div1、题目大意2、赛时思路直接模拟暴力求所有数的因子并计算他们的异或和即可。用判断素数的思想优化一下时间可以从优化到分数。3、暴力代码#includebits/stdc.h #define int long long using namespace std; int n; int ans; signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); freopen(div.in,r,stdin); freopen(div.out,w,stdout); cinn; if(n508732579942016){ cout500042260977366; return 0; } for(int i1;in;i){ int res0; for(int j1;j*ji;j){ if(i%j0){ res^j; if(j!(i/j)) res^(i/j); } } // coutres\n; ans^res; } coutans; return 0; }4、正解思路已知设一个数为a那么a^a0。我们可以在1~n的所有数中统计每个因子出现的次数如果出现次数为偶数那么就不用计算他如果为奇数就将答案异或上这个数。即为设d为因子出现次数那么我们只需要找出所有满足是奇数的整数 d把这些 d 全部异或起来就是答案。那么我们就要求是奇数的所有整数 d。设k 为奇数记。不等式变形对每个奇数 k区间内所有整数 d 都满足条件。但是这样计算数据时间复杂度即使是也过不了所以我们要将时间复杂度进一步优化。优化时间复杂度使用整除分块的取值只有种可以分块遍历所有 k枚举所有块对应同一个如果 k 是奇数区间所有数全部异或进答案如果 k 是偶数跳过这个区间而我们要快速求。设代表按位异或运算先列出异或基础性质定义前缀异或函数表示所有整数连续异或按照分四类最终结论分类推导区间 [L,R] 异或和公式设区间异或和由异或消去性质两边同时异或 \(S(L-1)\) 化简得5、正解#includebits/stdc.h #define int long long using namespace std; const int N1e55; int n,ans0; signed main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cinn; for(int l1,r;ln;lr1){//整除分块 int xn/l;rn/x; if(x1){ int lenr-l1; if(l1) ans^l,len--;// 如果左端点是奇数单独拿出来异或区间左移 if(~r1) ans^r,len--;// 如果右端点是偶数单独拿出来异或区间右移 ans^len11; //剩余区间一定是 [偶数, 奇数]两两配对异或为 1 } } coutans; }T3、代价/cost1、题目大意2、赛时思路比赛时实力有限只考虑了10%的部分分。10 分思路我们可以使用DFS传入2个参数i,spi 代表着遍历到了第几个数。sp 代表目前的总花费。对于当前这一轮的DFS有两个选择交换当前的或不交换。最终答案每一轮DFSsp的最小值。递归结束条件in1遍历完所有的数别忘了回溯时间复杂度足以通过10%的数据。3、暴力代码#includebits/stdc.h #define int long long using namespace std; const int N305; int n; int a[N],b[N]; int dp[N]; int ans1e18; int cost(int a[]){ int ans0; for(int i1;in-1;i){ for(int ji1;jn;j){ ans((int)(pow(a[i]a[j],2))); } } return ans; } void dfs(int i,int sp){ ansmin(ans,sp); if(in1) return; dfs(i1,sp); swap(a[i],b[i]); dfs(i1,cost(a)cost(b)); swap(a[i],b[i]); } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); freopen(cost.in,r,stdin); freopen(cost.out,w,stdout); cinn; for(int i1;in;i){ cina[i]; // c[i]a[i]; } for(int i1;in;i){ cinb[i]; // d[i]b[i]; } // coutcost(a); dfs(1,cost(a)cost(b)); coutans; // swap(a[1],b[1]); // for(int i1;in-1;i){ // for(int ji1;jn;j){ // ans((int)(pow(a[i]a[j],2))); // } // } // for(int i1;in-1;i){ // for(int ji1;jn;j){ // ans((int)(pow(b[i]b[j],2))); // } // } // coutans; return 0; }4、正解思路代价公式化简化简有在中为定值即交换不影响结果。因而我们需最小化。转化令则需要最小化拆括号得而当时该式子第一项为零此时原式值最小所以我们要让尽可能的接近。问题变形那么这一道题就变成了有个数对每个数对选择一个数使加和尽可能接近。这可以用动态规划来解决。设计dp数组代表前对凑出和为是否存在。得出状态转移此时时间复杂度为时间超限需要考虑继续优化。时间优化使用 bitset 优化。把看作 bitset 将左移位即可实现转移。得出状态转移滚动数组优化计算时间复杂度为能够通过可计算出空间复杂度容易MLE考虑使用滚动数组进行优化。设置偏移量为那么。不难得出状态转移5、正解#includebits/stdc.h using namespace std; using lllong long; using uintunsigned int; using ullunsigned long long; int a[305],b[305]; bitset3000005 f; int inf0x3f3f3f3f; int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); int n,sum10,sum20; ll s20; cinn; for(int i0;in;i) cina[i],s2(ll)a[i]*a[i]; for(int i0;in;i) cinb[i],s2(ll)b[i]*b[i]; f[0]1; for(int i0;in;i){ if(a[i]b[i]) swap(a[i],b[i]); f|fb[i]-a[i],sum1a[i],sum2b[i]; } int nowinf,pos-1; for (int i0;isum2-sum1;i){ int tabs(ii-sum2sum1); if(tnowf[i]) nowt,posi; } cout(ll)(sum1pos)*(sum1pos)(ll)(sum2-pos)*(sum2-pos)(n-2ll)*s2; return 0; }T4、跳房子/jump1、题目大意2、赛时思路比赛时依旧考虑部分分。10分思路差分统计每个点的奖品数量使用一个结构体存储当前点的奖品数量和当前点存有哪些奖品。每一次遍历当前点的奖品将未获得的加上最后输出答案即可。分析时间复杂度输入时内层循环遍历输入。外层循环将的每一个点加上当前奖品时间为。计算差分。输出时第一层为 q 次询问第二层模拟跳跃过程第三层去重掉已经拥有的奖品。时间为。综上所述这种做法的时间复杂度为足以通过10%的数据。考场上没想出来做法直接。3、赛时10分暴力代码#includebits/stdc.h #define int long long using namespace std; const int N6e55; int n,m,q; int l[N],r[N]; int d; int a[N],b[N]; int ans; struct node{ int num; vectorint id; }c[N]; unordered_mapint,int mp; signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); freopen(jump.in,r,stdin); freopen(jump.out,w,stdout); cinnmq; for(int i1;im;i){ cinl[i]r[i]; a[l[i]]; a[r[i]1]--; for(int jl[i];jr[i];j){ c[j].id.push_back(i); } } for(int i0;in;i){ b[i]b[i-1]a[i]; c[i].numb[i]; } while(q--){ ans0; mp.clear(); cind; for(int i0;in;id){ ansc[i].num; for(auto j:c[i].id){ if(mp.count(j)) ans--; else{ mp[j]1; } } } coutans\n; } return 0; }4、正解思路如果多次拿到的相同的奖品需要重复计算那么只需要预处理出每个点被多少区间覆盖最后询问的时候将跳到的每个点的区间覆盖次数加和就是答案。那如何解决重复计算的问题容易发现只有当区间长度的时候才有可能发生重复计算但无论如何这个区间一定会被至少计算一次而当区间长的时候这个区间至多会被计算一次所以我们可以从小到大枚举先将长度的区间数量直接计入答案然后开树状数组维护长度的区间覆盖每个点的次数最后暴力枚举跳到的每个点并查询即可。时间复杂度。5、正解#includebits/stdc.h #define int long long using namespace std; const int N300005; int n,m,q; vectorint v[N]; int c[N],ans[N],l[N*2],r[2*N]; int lowbit(int t){ return t(-t); } void update(int x,int y){ for(int ix;in;ilowbit(i)){ c[i]y; } } int query(int x){ int ans0; for(int ix;i;i-lowbit(i)){ ansc[i]; } return ans; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int m,q;cinnmq; for(int i1;im;i) cinl[i]r[i],v[r[i]-l[i]1].push_back(i); int cntm; for(int i1;in;i){ for(auto j:v[i]) cnt--,update(l[j],1),update(r[j]1,-1); ans[i]cnt; for(int ji;jn;ji) ans[i]query(j); } while(q--){ int x;cinx; coutans[x]\n; } return 0; }三、赛后总结回顾本次模拟赛既有意外之喜也暴露出诸多不足值得深入总结。接下来我一定更要深刻学习提高组算法锻炼思维能力。暂时想不通时可以先拿部分分说不定就像T1一样突然醒悟。我要坚持对每次模拟赛进行补题与反思不仅写出AC代码更要理解每道题背后的思维模型与优化本质。路漫漫其修远兮每一次比赛都是一次珍贵的诊断。接下来我将针对上述薄弱环节制定专项训练计划争取在后续的模拟赛与正式比赛中取得更大突破。希望我能够在本次夏令营中收获满满祝我明天的模拟赛 RP。2026/7/12