2026勰码金牌夏令营济南A-营模拟赛一补题报告

2026勰码金牌夏令营济南A-营模拟赛一补题报告

S12316 明宗亮

一、比赛过程

1、赛前估分

2、实际分数

3、赛时简述

这一次比赛满分400分，我得了155分，发挥的很好。但是在一些知识上让暴露出了不足。

第一题开门暴击，死磕了半个小时后没思路，本来想骗分，结果骗分过程把我的思路打开了，写了个dfs直接AC。

第二题数学题，比赛时打了的表，推了一下大概能干到，就打了很暴力的暴力，结果不知道咋了被卡掉了5分。

第三题也是一个数学题，难度比第二题难了亿点点，有很多的优化技巧，感觉自身知识储备还是太少了，啥也不会，比赛时打了一个暴搜拿下部分分。

第四题一道数据结构题，比赛时想拿到30分的部分分，但是有一层循环始终优化不掉，时间复杂度,只拿到了十分。

二、题目分析

T1、分面包/bread

1、题目大意

2、赛时思路

比赛时第一眼二分答案，写着写着发现不对劲，第二眼深搜，写着写着又发现不对劲，然后走投无路开始骗分，打完了骗分的DFS后发现了正解思路，就完善了一下代码。

因为面包最终的大小肯定比所有的都小，所以我们直接从开始逆序枚举，这样的好处是第一个找到的符合条件的数就是最终的面包大小，避免了大量的无效枚举。

理论来说这样做最差的时间复杂度最差是，但是经测试，最终的结果如下：

所以实际上这种做法的时间复杂度要比理论上快很多，主要是因为 逆序枚举+剪枝 节省了不少时间。

对于特殊性质（测试点7）：

进行特判，统计每个数的k，并通过计算得出p是多少。找出对于每个数的k，最小的k是多少，设他为q，接着算出所有k-q的和，记他为sum，则需要做sum次操作，每个面包最大是。

3、正解（赛时代码）

#include<bits/stdc++.h> #define int long long using namespace std; const int N=1e5+5; int Y[N]; int n,a[N],b[N];//b[i]表示下标i除以2的次数 int minn=1e18; //set<int> st; int num=1e18; int sinn; bool check7(){ int tot=a[1]; for(int i=2;i<=n;i++){ if(a[i]!=tot) return false; } return true; } //bool flag=0; //void dfs(int n,int step){ // if(n==2){ // num=min(num,step); // return ; // } // if(n<2) return ; // if(n%2==0) dfs(n/2,step+1); // else{ // dfs(n/2,step+1); // dfs(n/2+1,step+1); // } //} void dfs2(int n,int step){ if(n==sinn){ num=min(num,step); // flag=1; return ; } if(n<sinn) return ; if(n%2==0) dfs2(n/2,step+1); else{ dfs2(n/2,step+1); dfs2(n/2+1,step+1); } } //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); cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; Y[i]=a[i]; minn=min(minn,a[i]); // st.insert(a[i]); while(a[i]%2==0){ a[i]/=2; b[i]++; } // maxx=max(maxx,a[i]); } if(check7()){ int minnn=1e18,sum=0; for(int i=1;i<=n;i++){ minnn=min(minnn,b[i]); } for(int i=1;i<=n;i++){ sum+=(b[i]-minnn); } cout<<sum<<" "<<a[1]*(1<<minnn); return 0; } for(int i=1;i<=n;i++){ a[i]=Y[i]; // st.insert(a[i]); // t[a[i]]++; } int ans=0; // for(int i=1;i<=n;i++){ // dfs(a[i],0); // ans+=num; // num=1e18; // } // cout<<ans<<" 2"; for(int i=minn;i>=1;i--){ sinn=i; ans=0; // flag=0; for(int j=1;j<=n;j++){ num=1e18; // flag=0; dfs2(a[j],0); if(num==1e18) break; // cout<<num<<"\n"; ans+=num; if(j==n){ cout<<ans<<" "<<i; return 0; } } } // if(st.size()<=6){ // int res=0; // for(auto i:st){ // c[++res]=i; // } // // } // for(int i=1;i<=n;i++){ // if() // } // int l=1,r=maxx+1; // while(l<r){ // int mid=(l+r)/2; // if(check(mid)) l=mid+1; // else r=mid; // } // cout<<l; return 0; }

T2、快速筛因子算法/div

1、题目大意

2、赛时思路

直接模拟，暴力求所有数的因子，并计算他们的异或和即可。

用判断素数的思想优化一下时间，可以从优化到，分数。

3、暴力代码

#include<bits/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); cin>>n; if(n==508732579942016){ cout<<"500042260977366"; return 0; } for(int i=1;i<=n;i++){ int res=0; for(int j=1;j*j<=i;j++){ if(i%j==0){ res^=j; if(j!=(i/j)) res^=(i/j); } } // cout<<res<<"\n"; ans^=res; } cout<<ans; return 0; }

4、正解思路

已知：设一个数为a，那么a^a=0。

我们可以在1~n的所有数中，统计每个因子出现的次数，如果出现次数为偶数，那么就不用计算他，如果为奇数，就将答案异或上这个数。

即为：

设d为因子出现次数，那么我们只需要找出所有满足是奇数的整数 d，把这些 d 全部异或起来就是答案。

那么我们就要求是奇数的所有整数 d。

设，k 为奇数，记。

不等式：

变形：

对每个奇数 k，区间内所有整数 d 都满足条件。

但是这样计算，数据，时间复杂度即使是也过不了，所以我们要将时间复杂度进一步优化。

优化时间复杂度：使用整除分块

的取值只有种，可以分块遍历所有 k：

1. 枚举所有块，对应同一个
2. 如果 k 是奇数：区间所有数全部异或进答案
3. 如果 k 是偶数：跳过这个区间

而我们要快速求。

设代表按位异或运算，先列出异或基础性质：

定义前缀异或函数，表示所有整数连续异或：按照分四类，最终结论：

分类推导：

区间 [L,R] 异或和公式

设区间异或和，由异或消去性质：

两边同时异或 \(S(L-1)\) ，化简得：

5、正解

#include<bits/stdc++.h> #define int long long using namespace std; const int N=1e5+5; int n,ans=0; signed main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>n; for(int l=1,r;l<=n;l=r+1){//整除分块 int x=n/l;r=n/x; if(x&1){ int len=r-l+1; if(l&1) ans^=l,len--;// 如果左端点是奇数，单独拿出来异或，区间左移 if(~r&1) ans^=r,len--;// 如果右端点是偶数，单独拿出来异或，区间右移 ans^=len>>1&1; //剩余区间一定是 [偶数, 奇数]，两两配对异或为 1 } } cout<<ans; }

T3、代价/cost

1、题目大意

2、赛时思路

比赛时实力有限，只考虑了10%的部分分。

10 分思路：

我们可以使用DFS，传入2个参数：i,sp

i 代表着遍历到了第几个数。

sp 代表目前的总花费。

对于当前这一轮的DFS，有两个选择：交换当前的或不交换。

最终答案：每一轮DFS，sp的最小值。

递归结束条件：i>=n+1（遍历完所有的数）

别忘了回溯！

时间复杂度：，足以通过10%的数据。

3、暴力代码：

#include<bits/stdc++.h> #define int long long using namespace std; const int N=305; int n; int a[N],b[N]; int dp[N]; int ans=1e18; int cost(int a[]){ int ans=0; for(int i=1;i<=n-1;i++){ for(int j=i+1;j<=n;j++){ ans+=((int)(pow(a[i]+a[j],2))); } } return ans; } void dfs(int i,int sp){ ans=min(ans,sp); if(i>=n+1) return; dfs(i+1,sp); swap(a[i],b[i]); dfs(i+1,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); cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; // c[i]=a[i]; } for(int i=1;i<=n;i++){ cin>>b[i]; // d[i]=b[i]; } // cout<<cost(a); dfs(1,cost(a)+cost(b)); cout<<ans; // swap(a[1],b[1]); // for(int i=1;i<=n-1;i++){ // for(int j=i+1;j<=n;j++){ // ans+=((int)(pow(a[i]+a[j],2))); // } // } // for(int i=1;i<=n-1;i++){ // for(int j=i+1;j<=n;j++){ // ans+=((int)(pow(b[i]+b[j],2))); // } // } // cout<<ans; return 0; }

4、正解思路：

代价公式化简：

化简，有：

在中，为定值，即交换不影响结果。因而我们需最小化：。

转化：

令，，则需要最小化

拆括号得：

而当时，该式子第一项为零，此时原式值最小，所以我们要让尽可能的接近。

问题变形：

那么，这一道题就变成了有个数对，每个数对选择一个数，使加和尽可能接近。

这可以用动态规划来解决。

设计dp数组代表前对凑出和为是否存在。

得出状态转移：

此时时间复杂度为，时间超限，需要考虑继续优化。

时间优化：

使用 bitset 优化。

把看作 bitset ，将左移位即可实现转移。

得出状态转移：

滚动数组优化：

计算时间复杂度为，能够通过，可计算出空间复杂度，容易MLE，考虑使用滚动数组进行优化。

设置偏移量为，那么。

不难得出状态转移：

5、正解

#include<bits/stdc++.h> using namespace std; using ll=long long; using uint=unsigned int; using ull=unsigned long long; int a[305],b[305]; bitset<3000005> f; int inf=0x3f3f3f3f; int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); int n,sum1=0,sum2=0; ll s2=0; cin>>n; for(int i=0;i<n;i++) cin>>a[i],s2+=(ll)a[i]*a[i]; for(int i=0;i<n;i++) cin>>b[i],s2+=(ll)b[i]*b[i]; f[0]=1; for(int i=0;i<n;i++){ if(a[i]>b[i]) swap(a[i],b[i]); f|=f<<b[i]-a[i],sum1+=a[i],sum2+=b[i]; } int now=inf,pos=-1; for (int i=0;i<=sum2-sum1;i++){ int t=abs(i+i-sum2+sum1); if(t<now&&f[i]) now=t,pos=i; } cout<<(ll)(sum1+pos)*(sum1+pos)+(ll)(sum2-pos)*(sum2-pos)+(n-2ll)*s2; return 0; }

T4、跳房子/jump

1、题目大意

2、赛时思路

比赛时依旧考虑部分分。

10分思路：

差分统计每个点的奖品数量，使用一个结构体存储当前点的奖品数量和当前点存有哪些奖品。

每一次遍历当前点的奖品，将未获得的加上，最后输出答案即可。

分析时间复杂度：

输入时：内层循环遍历输入。外层循环将的每一个点加上当前奖品，时间为。

计算差分：。

输出时：第一层为 q 次询问，第二层模拟跳跃过程，第三层去重掉已经拥有的奖品。时间为。

综上所述，这种做法的时间复杂度为，足以通过10%的数据。

考场上没想出来做法，直接。

3、赛时10分暴力代码

#include<bits/stdc++.h> #define int long long using namespace std; const int N=6e5+5; int n,m,q; int l[N],r[N]; int d; int a[N],b[N]; int ans; struct node{ int num; vector<int> id; }c[N]; unordered_map<int,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); cin>>n>>m>>q; for(int i=1;i<=m;i++){ cin>>l[i]>>r[i]; a[l[i]]++; a[r[i]+1]--; for(int j=l[i];j<=r[i];j++){ c[j].id.push_back(i); } } for(int i=0;i<=n;i++){ b[i]=b[i-1]+a[i]; c[i].num=b[i]; } while(q--){ ans=0; mp.clear(); cin>>d; for(int i=0;i<=n;i+=d){ ans+=c[i].num; for(auto j:c[i].id){ if(mp.count(j)) ans--; else{ mp[j]=1; } } } cout<<ans<<"\n"; } return 0; }

4、正解思路

如果多次拿到的相同的奖品需要重复计算，那么只需要预处理出每个点被多少区间覆盖最后询问的时候将跳到的每个点的区间覆盖次数加和就是答案。
那如何解决重复计算的问题？容易发现只有当区间长度的时候，才有可能发生重复计算，但无论如何，这个区间一定会被至少计算一次，而当区间长的时候，这个区间至多会被计算一次，所以我们可以从小到大枚举，先将长度的区间数量直接计入答案，然后开树状数组维护长度的区间覆盖每个点的次数，最后暴力枚举跳到的每个点并查询即可。
时间复杂度：。

5、正解

#include<bits/stdc++.h> #define int long long using namespace std; const int N=300005; int n,m,q; vector<int> 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 i=x;i<=n;i+=lowbit(i)){ c[i]+=y; } } int query(int x){ int ans=0; for(int i=x;i;i-=lowbit(i)){ ans+=c[i]; } return ans; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int m,q;cin>>n>>m>>q; for(int i=1;i<=m;i++) cin>>l[i]>>r[i],v[r[i]-l[i]+1].push_back(i); int cnt=m; for(int i=1;i<=n;i++){ for(auto j:v[i]) cnt--,update(l[j],1),update(r[j]+1,-1); ans[i]=cnt; for(int j=i;j<=n;j+=i) ans[i]+=query(j); } while(q--){ int x;cin>>x; cout<<ans[x]<<'\n'; } return 0; }

三、赛后总结

回顾本次模拟赛，既有意外之喜，也暴露出诸多不足，值得深入总结。

接下来我一定更要深刻学习提高组算法，锻炼思维能力。暂时想不通时可以先拿部分分，说不定就像T1一样突然醒悟。

我要坚持对每次模拟赛进行补题与反思，不仅写出AC代码，更要理解每道题背后的思维模型与优化本质。

路漫漫其修远兮，每一次比赛都是一次珍贵的诊断。接下来我将针对上述薄弱环节制定专项训练计划，争取在后续的模拟赛与正式比赛中取得更大突破。

希望我能够在本次夏令营中收获满满，祝我明天的模拟赛 RP++。

2026/7/12