补题链接第十一届中国大学生程序设计竞赛网络预选赛CCPC Online 2025 - 比赛主页 - 比赛 - QOJ.ac过了很久了才来补题也是怠慢了E. 看比赛回放思路签到输出2*(m-(n1)/2)1即可代码void solve(){ int n,m; cinnm; cout2*(m-(n1)/2)1\n; }K. 置换环思路签到答案为n*(n1)/2逆序输出即可代码void solve(){ int n;cinn; vectorint a(n1); coutn*(n1)/2\n; for(int in;i1;i--){ couti ; }cout\n; }A. 整点正方形计数2思路赛时就感觉挺麻烦的写了一个小时中间还wa了一发但后来想通了发现并不是那么复杂考虑枚举n*m的所有点以其为正方形的某个顶点统计答案对于某个点(i,j)来说考虑将其分成四部分即右上、右下、左上、左下这四部分中的每个部分又可以分成两个部分即正规的和斜着的正方形令am-j即点(i,j)的右边剩余边长bn-i下面剩余边长cj左边di上面假设现在统计右上部分能够形成的正方形1.正规的min(a,d)个2.斜着的如下图所示我们将其长定义为l与h那么显然对于l和h是有限制的其中那么我们不妨枚举l和h的所有可能值统计答案由于当前l与h是成立的那么小于l与h的正方形也是成立的所以我们只需要枚举l的可能值寻找h的最大值即可细节问题可以看代码最后发现其是一段相等的数等差数列快速得出答案即可代码#includebits/stdc.h using namespace std; #define int long long int check(int mx,int l,int h){ if(mx0||l0||h0) return 0; int mxlmin(mx-1,l); int ans0; if(hmx){ int nmxl; int a1mx-mxl; ansa1*n((n-1)*n/2); }else{ int xmx-h; if(xmxl){ return mxl*h; } ansx*h; int n(mxl-x); int a1mx-mxl; ansa1*n((n-1)*n/2); } return ans; } void solve(){ int n,m; cinnm; vectorvectorint ans(n1,vectorint(m1)); for(int i0;in;i){ for(int j0;jm;j){ int am-j; int bn-i; int cj; int di; ans[i][j]min(a,d); ans[i][j]min(a,b); ans[i][j]min(c,d); ans[i][j]min(c,b); ans[i][j]check(a,min(b,d),max(b,d)); ans[i][j]check(b,min(c,a),max(c,a)); ans[i][j]check(c,min(b,d),max(b,d)); ans[i][j]check(d,min(c,a),max(c,a)); } } for(int i0;in;i){ for(int j0;jm;j){ coutans[i][j] ; }cout\n; } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); coutfixedsetprecision(2); int _1; // cin_; while(_--) solve(); return 0; }G. 序列与整数对思路赛后补题队友赛时用主席树维护过的存储x,y的位置哪个出现次数少遍历哪个用二分找另一个的数量再加上记忆化就能过复杂度分析参考根号分治代码#includebits/stdc.h using namespace std; #define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define int long long #define vi vectorint #define vb vectorbool typedef pairint,int pll; const int N2e510; const int inf1e18; const int mod998244353; void solve(){ int n,q; cinnq; vectorint a(n1); mapint,vectorint mp; for(int i1;in;i){ cina[i]; mp[a[i]].push_back(i); } mappll,int ans; while(q--){ int x,y;cinxy; if(xy){ int mmp[x].size(); cout(m*(m-1)/2)\n; continue; } if(ans[{x,y}]){ coutans[{x,y}]\n; continue; } vi vxmp[x]; vi vymp[y]; int res0; if(vx.size()vy.size()){ for(auto p:vx){ resvy.end()-lower_bound(vy.begin(),vy.end(),p); } }else{ for(auto p:vy){ reslower_bound(vx.begin(),vx.end(),p)-vx.begin(); } } ans[{x,y}]res; coutres\n; } } signed main() { vcoistnt coutfixedsetprecision(2); int _1; // cin_; while(_--) solve(); return 0; }C. 造桥与砍树思路很明显此题是最小生成树考虑到最小生成树的普遍的两种做法Kruskal 和 PrimKruskal需要生成n*(n-1)/2条边显然根据此题的范围来说是不可行的Prim从一个起点开始每次维护最小的边加进去此题对于某个点来说我们可以得到与其相连的所有边但不用全部遍历每次查询找到最小即可所以此题Prim是可行的代码#includebits/stdc.h using namespace std; #define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define int long long #define vi vectorint #define vb vectorbool typedef pairint,int pll; typedef tupleint,int,int TI; const int N2e510; const int inf1e18; const int mod998244353; void solve(){ int n,k;cinnk; multisetint s; for(int i1;in;i){ int x;cinx; x%k; s.insert(x); } priority_queueTI,vectorTI,greaterTI pq; auto get[](int x){ auto its.lower_bound(k-x); return *(its.end() ? s.begin():it); }; int x*s.begin();s.erase(s.begin()); int yget(x); pq.push({(xy)%k,x,y}); int ans0; while(!pq.empty()!s.empty()){ auto [w,x,y]pq.top();pq.pop(); if(!s.count(y)){ continue; } answ; s.erase(s.find(y)); int aget(y); int bget(x); pq.push({(ya)%k,y,a}); pq.push({(xb)%k,x,b}); } coutans\n; } signed main() { vcoistnt coutfixedsetprecision(2); int _1; cin_; while(_--) solve(); return 0; }