补题链接：第十一届中国大学生程序设计竞赛网络预选赛（CCPC Online 2025） - 比赛主页 - 比赛 - QOJ.ac

过了很久了才来补题，也是怠慢了

E. 看比赛回放

思路

签到，输出2*(m-(n+1)/2)+1即可

代码

void solve(){ int n,m; cin>>n>>m; cout<<2*(m-(n+1)/2)+1<<"\n"; }

K. 置换环

思路

签到，答案为n*(n+1)/2，逆序输出即可

代码

void solve(){ int n;cin>>n; vector<int> a(n+1); cout<<n*(n+1)/2<<"\n"; for(int i=n;i>=1;i--){ cout<<i<<" "; }cout<<"\n"; }

A. 整点正方形计数2

思路

赛时就感觉挺麻烦的，写了一个小时中间还wa了一发，但后来想通了发现并不是那么复杂

考虑枚举n*m的所有点，以其为正方形的某个顶点，统计答案

对于某个点(i,j)来说，考虑将其分成四部分，即右上、右下、左上、左下，这四部分中的每个部分又可以分成两个部分，即正规的和斜着的正方形

令a=m-j即点(i,j)的右边剩余边长，b=n-i下面剩余边长，c=j左边，d=i上面

假设现在统计右上部分能够形成的正方形

1.正规的，min(a,d)个

2.斜着的，如下图所示我们将其长定义为l与h，那么显然对于l和h是有限制的，其中

那么我们不妨枚举l和h的所有可能值统计答案，由于当前l与h是成立的那么小于l与h的正方形也是成立的，所以我们只需要枚举l的可能值，寻找h的最大值即可，细节问题可以看代码，最后发现其是一段相等的数+等差数列，快速得出答案即可

代码

#include<bits/stdc++.h> using namespace std; #define int long long int check(int mx,int l,int h){ if(mx==0||l==0||h==0) return 0; int mxl=min(mx-1,l); int ans=0; if(h>=mx){ int n=mxl; int a1=mx-mxl; ans=a1*n+((n-1)*n/2); }else{ int x=mx-h; if(x>=mxl){ return mxl*h; } ans+=x*h; int n=(mxl-x); int a1=mx-mxl; ans+=a1*n+((n-1)*n/2); } return ans; } void solve(){ int n,m; cin>>n>>m; vector<vector<int>> ans(n+1,vector<int>(m+1)); for(int i=0;i<=n;i++){ for(int j=0;j<=m;j++){ int a=m-j; int b=n-i; int c=j; int d=i; 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 i=0;i<=n;i++){ for(int j=0;j<=m;j++){ cout<<ans[i][j]<<" "; }cout<<"\n"; } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout<<fixed<<setprecision(2); int _=1; // cin>>_; while(_--) solve(); return 0; }

G. 序列与整数对

思路

赛后补题，队友赛时用主席树维护过的？

存储x,y的位置，哪个出现次数少遍历哪个，用二分找另一个的数量，再加上记忆化就能过，复杂度分析参考根号分治

代码

#include<bits/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 vector<int> #define vb vector<bool> typedef pair<int,int> pll; const int N=2e5+10; const int inf=1e18; const int mod=998244353; void solve(){ int n,q; cin>>n>>q; vector<int> a(n+1); map<int,vector<int>> mp; for(int i=1;i<=n;i++){ cin>>a[i]; mp[a[i]].push_back(i); } map<pll,int> ans; while(q--){ int x,y;cin>>x>>y; if(x==y){ int m=mp[x].size(); cout<<(m*(m-1)/2)<<"\n"; continue; } if(ans[{x,y}]){ cout<<ans[{x,y}]<<"\n"; continue; } vi vx=mp[x]; vi vy=mp[y]; int res=0; if(vx.size()<vy.size()){ for(auto p:vx){ res+=vy.end()-lower_bound(vy.begin(),vy.end(),p); } }else{ for(auto p:vy){ res+=lower_bound(vx.begin(),vx.end(),p)-vx.begin(); } } ans[{x,y}]=res; cout<<res<<"\n"; } } signed main() { vcoistnt cout<<fixed<<setprecision(2); int _=1; // cin>>_; while(_--) solve(); return 0; }

C. 造桥与砍树

思路

很明显此题是最小生成树

考虑到最小生成树的普遍的两种做法：Kruskal 和 Prim

Kruskal需要生成n*(n-1)/2条边，显然根据此题的范围来说是不可行的

Prim从一个起点开始，每次维护最小的边加进去，此题对于某个点来说我们可以得到与其相连的所有边，但不用全部遍历每次查询找到最小即可

所以此题Prim是可行的

代码

#include<bits/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 vector<int> #define vb vector<bool> typedef pair<int,int> pll; typedef tuple<int,int,int> TI; const int N=2e5+10; const int inf=1e18; const int mod=998244353; void solve(){ int n,k;cin>>n>>k; multiset<int> s; for(int i=1;i<=n;i++){ int x;cin>>x; x%=k; s.insert(x); } priority_queue<TI,vector<TI>,greater<TI>> pq; auto get=[&](int x){ auto it=s.lower_bound(k-x); return *(it==s.end() ? s.begin():it); }; int x=*s.begin();s.erase(s.begin()); int y=get(x); pq.push({(x+y)%k,x,y}); int ans=0; while(!pq.empty()&&!s.empty()){ auto [w,x,y]=pq.top();pq.pop(); if(!s.count(y)){ continue; } ans+=w; s.erase(s.find(y)); int a=get(y); int b=get(x); pq.push({(y+a)%k,y,a}); pq.push({(x+b)%k,x,b}); } cout<<ans<<"\n"; } signed main() { vcoistnt cout<<fixed<<setprecision(2); int _=1; cin>>_; while(_--) solve(); return 0; }