[CSP 2025]游记

眭岐锋

CSP-J

---

\(T1\)

---

循环结构 \(+\) 字符串，橙题，不说了肯定做出来了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 2000005 
int top,a[N];
string s;
signed main(){
	cin>>s,s=" "+s;
	for(int i=1;i<s.length();i++) if(s>='0'&&s<='9') a[++top]=s-'0';
	sort(a+1,a+top+1);
	for(int i=top;i;i--) cout<<a; 
	return 0;
} 

\(T2\)

---

循环结构 \(+\) 小学数学，橙题，不说了肯定做出来了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 2000005 
int n,m,x,y,cnt,a[N];
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n*m;i++){cin>>a;if(a>=a[1]) cnt++;}
	x=cnt/n+(cnt%n!=0);
	if(x%2==1) y=cnt-n*(x-1);
	else y=n-(cnt-n*(x-1))+1;
	cout<<x<<" "<<y<<endl; 
	return 0;
} 

\(T3\)

---

贪心 \(+\) 红黑树（\(map\)），黄题，不说了肯定做出来了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 2000005 
int n,k,a[N],pre[N],cnt;
map<int,int>mp;
signed main(){
	cin>>n>>k;
	mp[0]=-1;
	for(int i=1,r=-1;i<=n;i++){
		cin>>a;
		pre=pre[i-1]^a;
		if(mp[pre^k]!=0&&mp[pre^k]>=r) r=i,cnt++;
		mp[pre]=i;
	}
	cout<<cnt<<endl;
	return 0;
} 

\(T4\)

---

普通背包 \(+\) 出题人好心的帮忙解决了的数学部分，绿题，不说了肯定做出来了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 5005 
#define mx 5000
#define md 998244353
int n,a[N],dp[N],ans;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a;
	sort(a+1,a+n+1);
	dp[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=a+1;j<=mx+1;j++) ans=(ans+dp[j])%md;
		for(int j=mx+1;j>=mx+1-a;j--) dp[mx+1]=(dp[j]+dp[mx+1])%md;
		for(int j=mx;j>=a;j--) dp[j]=(dp[j]+dp[j-a])%md;
	}
	cout<<ans<<endl; 
	return 0;
} 

\(对拍\)

---

• \(T1\) 打了暴搜。
• \(T2\) 打了模拟。
• \(T3\) 打了暴搜。
• \(T4\) 打了状压。
  最后四个对拍一起跑了 \(1\) 个小时。

---

遗憾监考老师强调不能玩 \(dino\)。

---

CSP-S

---

\(T1\)

---

1. 先不管集合的数要 \(\le \frac{n}{2}\) 的条件，贪心直接放。
2. 如果数最多的集合的数 \(> \frac{n}{2}\)，取出放入其他集合后对答案影响最小的几个数，放入其他集合。可以证明，此时其他集合数的个数都会 \(\le \frac{n}{2}\)。
3. 此时答案最优。

挺简单，不到半小时就调完了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 200005 
#define mx 5000
#define md 998244353
int t,n,a[N],ans;
struct PT{int p[N],top;}q[4];
bool cmp(PT a,PT b){return a.top>b.top;}
signed main(){
	cin>>t;
	while(t--){
		cin>>n;
		ans=q[1].top=q[2].top=q[3].top=0;
		for(int i=1,a,b,c;i<=n;i++){
			cin>>a>>b>>c;
			if(a>=b&&a>=c) q[1].p[++q[1].top]=min(a-b,a-c),ans+=a;
			else if(b>=c&&b>=a) q[2].p[++q[2].top]=min(b-a,b-c),ans+=b;
			else if(c>=b&&c>=a) q[3].p[++q[3].top]=min(c-b,c-a),ans+=c; 
		}
		sort(q+1,q+3+1,cmp);
		for(int i=1;i<=q[1].top;i++) a=q[1].p;
		sort(a+1,a+q[1].top+1);
		for(int i=1;i<=q[1].top-n/2;i++) ans-=a;
		cout<<ans<<endl;
	}
	return 0;
} 

\(T2\)

---

1. 先求出 \(n\) 个点 \(m\) 条边的最小生成树。
2. 状压 \(k\) 个乡镇，与原先最小生成树的边一起再求最小生成树，更新答案。

时间复杂度 \(O(m\log_{2}{m}+2^knk\log_{2}{k})\)？不太对劲。造了个大数据，跑了 \(3\) 秒，又调了一个小时，还是 \(3\) 秒，最后相信评测机，不调了。

赛后在 \(luogu\) 跑得飞快。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 2000005 
int 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.fr<b.fr;}
bool cmpp(VL a,VL b){return a.fr<b.fr;}
int find(int w){return w==f[w]?w:f[w]=find(f[w]);} 
priority_queue<pair<int,pair<int,int> >,vector<pair<int,pair<int,int> > >,greater<pair<int,pair<int,int> > > >q;
signed main(){
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=1;i<=m;i++) scanf("%lld%lld%lld",&edge.u,&edge.v,&edge.fr);
	sort(edge+1,edge+m+1,cmp);
	for(int i=1;i<=m;i++) f=i;
	for(int i=1;i<=m;i++){
		if(find(edge.u)==find(edge.v))continue;
		p[0][++top]=edge,ans+=edge.fr;
		f[find(edge.u)]=find(edge.v),find(edge.u);
	}
	for(int i=1;i<=k;i++){
		scanf("%lld",&c);
		for(int j=1;j<=n;j++) scanf("%lld",&pp[j].fr),pp[j].pt=j;
		sort(pp+1,pp+n+1,cmpp);
		for(int j=1;j<=n;j++) p[j].u=n+i,p[j].v=pp[j].pt,p[j].fr=pp[j].fr;
	}
	for(int i=1;i<(1<<k);i++){
		while(!q.empty())q.pop();
		int anss=0,up=n-1,top=0;
		q.push({p[0][1].fr,{0,1}});
		for(int j=1;j<=k;j++) if((i>>(j-1))&1) q.push({p[j][1].fr,{j,1}}),up++,anss+=c[j];
		for(int i=1;i<=n+k;i++) f=i;
		while(top!=up){
			int x=q.top().second.first,y=q.top().second.second;
			q.pop();
			if(p[x][y+1].u!=0) q.push({p[x][y+1].fr,{x,y+1}});
			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);anss+=p[x][y].fr;
		}
		ans=min(anss,ans);
	}
	printf("%lld\n",ans);
	return 0;
} 

\(T3\)

---

写了个接近 \(100\) 行的 \(trie+hash\), 在比赛还剩 \(5\) 分钟才能运行，最后小样例过了，大样例没过，绝对 \(TLE\)。

无代码。

\(T4\)

---

只看了题。

---

预估

	\(T1\)	\(T2\)	\(T3\)	\(T4\)	\(sum\)
J	100	100	100	100	\(\le 400\)
S	100	100	0	0	200

希望吧。

来源：https://www.cnblogs.com/liuruian/p/19188423