[CSP 2025]游记

循环结构 字符串橙题不说了肯定做出来了。#includebits/stdc.husing namespace std;#define int long long#define N 2000005int top,a[N];string s;signed main(){cins,s s;for(int i1;is.length();i) if(s[i]0s[i]9) a[top]s[i]-0;sort(a1,atop1);for(int itop;i;i--) couta[i];return 0;}循环结构 小学数学橙题不说了肯定做出来了。#includebits/stdc.husing namespace std;#define int long long#define N 2000005int n,m,x,y,cnt,a[N];signed main(){cinnm;for(int i1;in*m;i){cina[i];if(a[i]a[1]) cnt;}xcnt/n(cnt%n!0);if(x%21) ycnt-n*(x-1);else yn-(cnt-n*(x-1))1;coutx yendl;return 0;}贪心 红黑树黄题不说了肯定做出来了。#includebits/stdc.husing namespace std;#define int long long#define N 2000005int n,k,a[N],pre[N],cnt;mapint,intmp;signed main(){cinnk;mp[0]-1;for(int i1,r-1;in;i){cina[i];pre[i]pre[i-1]^a[i];if(mp[pre[i]^k]!0mp[pre[i]^k]r) ri,cnt;mp[pre[i]]i;}coutcntendl;return 0;}普通背包 出题人好心的帮忙解决了的数学部分绿题不说了肯定做出来了。#includebits/stdc.husing namespace std;#define int long long#define N 5005#define mx 5000#define md 998244353int n,a[N],dp[N],ans;signed main(){cinn;for(int i1;in;i) cina[i];sort(a1,an1);dp[0]1;for(int i1;in;i){for(int ja[i]1;jmx1;j) ans(ansdp[j])%md;for(int jmx1;jmx1-a[i];j--) dp[mx1](dp[j]dp[mx1])%md;for(int jmx;ja[i];j--) dp[j](dp[j]dp[j-a[i]])%md;}coutansendl;return 0;}对拍打了暴搜。打了模拟。打了暴搜。打了状压。最后四个对拍一起跑了 个小时。遗憾监考老师强调不能玩 。CSP-S先不管集合的数要 的条件贪心直接放。如果数最多的集合的数 取出放入其他集合后对答案影响最小的几个数放入其他集合。可以证明此时其他集合数的个数都会 。此时答案最优。挺简单不到半小时就调完了。#includebits/stdc.husing namespace std;#define int long long#define N 200005#define mx 5000#define md 998244353int t,n,a[N],ans;struct PT{int p[N],top;}q[4];bool cmp(PT a,PT b){return a.topb.top;}signed main(){cint;while(t--){cinn;ansq[1].topq[2].topq[3].top0;for(int i1,a,b,c;in;i){cinabc;if(abac) q[1].p[q[1].top]min(a-b,a-c),ansa;else if(bcba) q[2].p[q[2].top]min(b-a,b-c),ansb;else if(cbca) q[3].p[q[3].top]min(c-b,c-a),ansc;}sort(q1,q31,cmp);for(int i1;iq[1].top;i) a[i]q[1].p[i];sort(a1,aq[1].top1);for(int i1;iq[1].top-n/2;i) ans-a[i];coutansendl;}return 0;}先求出 个点 条边的最小生成树。状压 个乡镇与原先最小生成树的边一起再求最小生成树更新答案。时间复杂度 不太对劲。造了个大数据跑了 秒又调了一个小时还是 秒最后相信评测机不调了。赛后在 跑得飞快。#includebits/stdc.husing namespace std;#define int long long#define N 2000005int n,m,k,f[N],top,c[N],ans;struct EDGE{int u,v,fr;}edge[N],p[15][20005];struct VL{int fr,pt;}pp[N];bool cmp(EDGE a,EDGE b){return a.frb.fr;}bool cmpp(VL a,VL b){return a.frb.fr;}int find(int w){return wf[w]?w:f[w]find(f[w]);}priority_queuepairint,pairint,int ,vectorpairint,pairint,int ,greaterpairint,pairint,int q;signed main(){scanf(%lld%lld%lld,n,m,k);for(int i1;im;i) scanf(%lld%lld%lld,edge[i].u,edge[i].v,edge[i].fr);sort(edge1,edgem1,cmp);for(int i1;im;i) f[i]i;for(int i1;im;i){if(find(edge[i].u)find(edge[i].v))continue;p[0][top]edge[i],ansedge[i].fr;f[find(edge[i].u)]find(edge[i].v),find(edge[i].u);}for(int i1;ik;i){scanf(%lld,c[i]);for(int j1;jn;j) scanf(%lld,pp[j].fr),pp[j].ptj;sort(pp1,ppn1,cmpp);for(int j1;jn;j) p[i][j].uni,p[i][j].vpp[j].pt,p[i][j].frpp[j].fr;}for(int i1;i(1k);i){while(!q.empty())q.pop();int anss0,upn-1,top0;q.push({p[0][1].fr,{0,1}});for(int j1;jk;j) if((i(j-1))1) q.push({p[j][1].fr,{j,1}}),up,anssc[j];for(int i1;ink;i) f[i]i;while(top!up){int xq.top().second.first,yq.top().second.second;q.pop();if(p[x][y1].u!0) q.push({p[x][y1].fr,{x,y1}});if(find(p[x][y].u)find(p[x][y].v))continue;top;f[find(p[x][y].u)]find(p[x][y].v),find(p[x][y].u);anssp[x][y].fr;}ansmin(anss,ans);}printf(%lld\n,ans);return 0;}