CSP-S2025第二轮 不完全题解

0 前言

这场的难度真的是谁都预料不到的。

另外T2道路修建的出题人是谁，这对我真的很重要。

1 前置芝士

A.社团招新（club）

• 贪心（反悔贪心）

B.道路修建（road）

• 最小生成树（MST）
• Kruskal算法
• 状态压缩
• 归并排序

C.谐音替换（replace）

（这题不会，先瞎写几个，待补）

• Trie
• 字符串哈希
• AC自动机

D.员工招聘（employ）

（这题完全不会，待补）

2 思路

A.社团招新

这题一开场一个小时都不会，最开始写了一个很唐的贪心然后假了，然后扔了去想T2了。最后T2没鼓捣出来的时候突然会这题了，10min过掉了大样例。

我们考虑贪心，首先让每个人都选好感度最高的部门，也就是先对于每个 $i$ 都取 $a_i$ 三个中的最大的。

如果这个时候符合条件那么就结束。但我们发现，这时候至多只有一个部门不符合约束。

那么考虑怎么样才能让挪动一部分人使得答案最大而且符合约束。

假设不满足约束的部门是 $1$，$S_1$ 是 $1$ 部门的成员集合，记对于成员 $i$，$a_i$ 中的最大值和次大值分别是 $a_{i,max}$ 和 $a_{i,sec}$，则挪动一个成员的 贡献是 $a_{i,sec}-a_{i,max}$，那么我们只需要从这 $|S_1|$ 个成员里面挑选出 $|S_1|-\frac{n}{2}$ 个贡献最大的，也就是影响最小的即可。

整体做法只需要排一遍序。时间复杂度 $O(n\log n)$。

B.道路修建

赛时先会了 $32pts$ 做法，然后会了 $64pts$ 做法，结果最后 $64pts$ 做法没调出来，出场后发现做法加一个状压和双指针就是正解了，遗憾离场。

首先想一下简单的暴力，最先应该想到的是枚举要选哪几个城镇，也就是状压一下。

考虑每个城镇带来的贡献。记当前状态中选了 $j$ 个城镇，最简单的暴力肯定是原图暴力加上 $jn$ 条跑 Kruskal，不难发现时间复杂度达到了惊人的 $O(2^k(kn+m)\alpha(kn+m)\log(kn+m))$，实际上已经并不算劣。

考虑怎么优化。

首先，不难发现，原图的 $m$ 条边并非全都有用，如果在原图内都无法选上MST的边一定没有用，所以可以对原图先跑一遍Kruskal，因此只剩下了 $n$ 条边，复杂度优化到了 $O(m\log m+2^k kn\alpha(n)\log kn )$。

其次，我们发现没有必要在每次枚举状态的时候都加入 $jn$ 条边，可以存下状态对应的MST，再将新加城镇的边与对应选择城镇数量减一的状态合并，因此每次只需要加上 $n$ 条边，复杂度可以去掉一个 $k$，变成$O(m\log m+2^kn\alpha(n)\log n)$。

最后，带着一个 $\log$ 还是太慢了怎么办？

我们发现每次枚举状态都跑了一次 Kruskal，也就是对边集排了序，这样显然有很多重复的排序操作。那么怎么办呢？

不难发现可以 $O(n)$ 地将两个有序序列合并，因此可以将每个城镇对应新加的边集预处理排序，在每次合并的时候仿照归并排序，$O(n)$ 地进行合并。

这样最后只有一个由于并查集带来的 $\alpha(n)$，最终的时间复杂度是 $O(m\log m+2^k n\alpha(n)+kn\log n)$

C.谐音替换

不会，待补。

D.员工招聘

2026年1月16日 补

3 代码

A.社团招新

考场原代码，如下。

#include<bits/stdc++.h>
#define int long long

const int N=114514;
 
int read(){
	int s=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while('0'<=c&&c<='9'){s=(s<<3)+(s<<1)+(c-'0');c=getchar();}
	return s*f;
}
struct psn{
	int v[4],maxn[4];
};
psn a[N];
int ans;
int n;
std::vector<int> cnt[4];
void solve(){
	std::sort(a+1,a+1+n,[](psn x,psn y){
		if(x.v[x.maxn[1]]==y.v[y.maxn[1]]){
			if(x.v[x.maxn[2]]==y.v[y.maxn[2]])return x.v[x.maxn[3]]>y.v[y.maxn[3]];
			else return x.v[x.maxn[2]]>y.v[y.maxn[2]];	
		}
		return x.v[x.maxn[1]]>y.v[y.maxn[1]];
	});
	for(int i=1;i<=n;++i){
		cnt[a[i].maxn[1]].push_back(i);
		ans+=a[i].v[a[i].maxn[1]];
	}
	int pos=0;
	if(cnt[1].size()>n/2)pos=1;
	if(cnt[2].size()>n/2)pos=2;
	if(cnt[3].size()>n/2)pos=3;
//	printf("(%lld)\n",pos);
	if(pos==0){
		printf("%lld\n",ans);
		return;
	}
	std::vector<int> tmp(0);
	for(auto &i:cnt[pos]){
		tmp.push_back(a[i].v[a[i].maxn[2]]-a[i].v[a[i].maxn[1]]);
//		printf("(%lld)\n",a[i].v[a[i].maxn[2]]-a[i].v[a[i].maxn[1]]);
	}std::sort(tmp.begin(),tmp.end(),std::greater<int>());
	for(int i=0;i<cnt[pos].size()-(n/2);++i){
//		printf("##(%#lld)\n",tmp[i]);
		ans+=tmp[i];
	}
	printf("%lld\n",ans);
}
signed main(){
    //赛后补——这里本来应该有freopen，但是为了便于阅读我现在给删掉了
	int T=read();
	while(T--){
		n=read();
		cnt[1].clear();
		cnt[2].clear();
		cnt[3].clear();
		ans=0;
		for(int i=1;i<=n;++i){
			a[i].v[1]=read();
			a[i].v[2]=read();
			a[i].v[3]=read();
			int tmp[4]={0,a[i].v[1],a[i].v[2],a[i].v[3]};
			std::sort(tmp+1,tmp+4,std::greater<int>());
			bool vis[4]={0,0,0,0};
			for(int j=1;j<=3;++j){
				for(int k=1;k<=3;++k){
					if(!vis[k]&&tmp[j]==a[i].v[k]){a[i].maxn[j]=k;vis[k]=1;break;}
				}
			}
		}
		solve();
	}
	return 0;
}
//���εĻ� Ť������������
//�����ߺľ� ���յ��������һ����ɫ
//���İ���ļ�� ����С������
//�������� �������� �ܽ��ҵĶ��� 

//���ۼ����������ۼ���
//����ƽ�����Ե������˵
//����ʲôʱ����ϧ�̻�
//����Լ���� ��Դ������

//��ִ�� �ij漳ȡ�����ν��
//��������� չ������ ����������˵ 

//赛后补——严肃吐槽山外的机器，Dev-C++不知道中文用了什么神异的编码，我不说没有人看得出来上面是《夏虫》的部分歌词

B.道路修建

还没写代码，待补。

C.谐音替换

不会，待补

D.员工招聘

不会，待补

补上了

4 后记

如果可以的话，NOIP2025，一定，一定。