分享
CSP-S 2025 总结
唐瑾恒 LV 3 @ 2025-11-2 11:49:46

考成依托了，故来写下总结

T1 社团招新

贪心 + 排序

solution

首先可以想到每个人可以只考虑满意度最大以及次大的社团，因为由题社团最多有 $\frac n2$ 个人，因此最多只有一个社团人数超过限制

借鉴反悔贪心的思路，我们可以先把每个人都放在满意度次大的社团中，然后再将人移动到满意度最大的社团。这里设 $a1$ 为最大满意度 , $a2$ 为次大满意度

不难想到最先将 $a1 - a2$ 最大的人移动到满意度最大的社团，然后再移动下一个

因此可以将 $a1 - a2$ 作为顺序排序，依次移动人，如果满意度最大的社团满人则不移动，否则移动，移动时统计答案即可

时间复杂度： $O(n \log n)$

code

（考场代码）

#include<bits/stdc++.h>
#define qwq ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

const int N = 1e5 + 5;

struct node{
	int id , w;
}p[N][5] , s[N];

int t , n , to[10];

bool cmp(const node &lhs , const node &rhs){
	return lhs.w > rhs.w;
}

void solve(){
	int ans = 0;
	
	cin >> n;
	
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= 3 ; j ++){
			cin >> p[i][j].w;
			p[i][j].id = j;
		}
		sort(p[i] + 1 , p[i] + 4 , cmp);
		s[i] = {i , p[i][1].w - p[i][2].w};
	}
	sort(s + 1 , s + n + 1 , cmp);
	
	for(int i = 1 ; i <= n ; i ++){
		int idx = s[i].id;
		
		if(to[p[idx][1].id] >= n / 2) to[p[idx][2].id] ++ , ans += p[idx][2].w;
		else to[p[idx][1].id] ++ , ans += p[idx][1].w;
	}
	cout << ans << '\n';
}

int main(){    qwq
	cin >> t;
	
	while(t --){
		memset(to , 0 , sizeof to);
		solve();
	}
	return 0;
}

T2 道路修复

生成树 + 贪心 + 状压

solution

首先可以想到一个很平凡的贪心：

答案的最小生成树的边一定只包含原图最小生成树的一些边 + 与乡村相连的一些边

证明可以考虑反证法

根据此贪心，我们可以想到先求出原图中的最小生成树，用 kruskal 即可。标记原图中的最小生成树所用到的边

随后可以考虑枚举每个乡村点的状态（选 / 不选），一共有 $2^k$ 种方式，因为 $k \leqslant 10$ 此复杂度可以接受。

对于一个状态 $S$ ,首先将所有乡村点权值加入 $sum$ ，即 $sum + \sum_{i \in S}{c_i}$ ，随后直接将所有乡村点所相连的边加入到原图的最小生成树中，然后对于新图再次求一遍最小生成树即可，最后统计每个状态的最小值就是答案

注意这样写有可能被卡，所以我们可以剪枝。具体地，设 $pmx$ 为原图最小生成树最大边，因为最小生成树一定为瓶颈生成树，所以答案中最小生成树最大边一定要小于等于 $pmx$ ，所以说我们加边时只加 $w \leqslant pmx$ 的边即可

可以考虑用桶排进行优化使复杂度少一只 $\log$

时间复杂度（跑不满）： $O(m\log m + 2^k kn \log kn)$

code

#include<bits/stdc++.h>
#define qwq ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
using namespace std;

const int N = 1e4 + 20;
const int M = 2e6 + 5;
const ll inf = 1e18;

struct node{
	int u , v , w;
}e[M] , ne[M] , tmp[N];

ll ans = inf;
int n , m , k , p[15][N] , pmx;
int fa[N];

bool cmp(const node &lhs , const node &rhs){
	return lhs.w < rhs.w;
}

int find(int x){
	if(x == fa[x]) return x;
	return fa[x] = find(fa[x]);
}

bool uni(int x , int y){
	int u = find(x) , v = find(y);
	if(u == v) return false;
	
	fa[u] = v;
	return true;
}

void kruskal(node edge[] , int m , int r , ll p0 , int flag = 0){
	ll cnt = 0 , sum = p0;
	
	sort(edge + 1 , edge + m + 1 , cmp);
	for(int i = 1 ; i <= n + k ; i ++) fa[i] = i;
	
	for(int i = 1 ; i <= m ; i ++){
		if(uni(edge[i].u , edge[i].v)){
			cnt ++ , sum += edge[i].w;
			if(flag) tmp[cnt] = edge[i];
			if(cnt == n + r - 1) break;
		}
	}
	if(flag) pmx = tmp[cnt].w;
	ans = min(ans , sum);
}

void solve(int s){
	ll p0 = 0 , t = 0 , idx = n - 1;
	
	for(int i = 1 ; i <= idx ; i ++){
		ne[i] = tmp[i];
	}
	
	for(int j = 0 ; j < k ; j ++){
		if(s & (1 << j)){
			p0 += p[j + 1][0] , t ++;
			
			for(int i = 1 ; i <= n ; i ++){
				if(p[j + 1][i] <= pmx) ne[++ idx] = {n + j + 1 , i , p[j + 1][i]};
			}
		}
	}
	kruskal(ne , idx , t , p0);
}

int main(){           qwq
	cin >> n >> m >> k; 
	
	for(int i = 1 ; i <= m ; i ++){
		cin >> e[i].u >> e[i].v >> e[i].w;
	}
	
	for(int i = 1 ; i <= k ; i ++){
		for(int j = 0 ; j <= n ; j ++){
			cin >> p[i][j];
		}
	}
	kruskal(e , m , 0 , 0 , 1);
	
	for(int i = 1 ; i < (1 << k) ; i ++){
		solve(i);
	}
	cout << ans;
	return 0;
}

upd : 讲个笑话，我考场时脑子抽了多写了一个对 p 数组排序，后面还死活没查出来，后来回来删掉这一句就过了

于是 $100$ -> $40$

凉凉

T3 谐音替换

字典树 + 哈希 + 扫描线

solution

考虑刻画一下询问替换是在干什么

对于询问 $(t1 , t2)$ ，可以将其转化为 $(ACB , ADB)$ ，其中 $A$ 为 $(t1 , t2)$ 的最长公共前缀， $B$ 为 $(t1 , t2)$ 的最长公共后缀，并且定义 $(C , D)$ 为 $(t1 , t2)$ 本质串

对于操作 $(s1 , s2)$ ，同理有如上转化

于是观察询问替换，我们不难发现询问就是让我们对于 $(t1 , t2)$ 找到如下 $(s1 , s2)$ 的数量满足：

$(t1 , t2)$ 和 $(s1 , s2)$ 本质串 $(C , D)$ 相同
$s_A$ 为 $t_A$ 的一个后缀
$s_B$ 为 $t_B$ 的一个前缀

对于 $1$ 要求，我们可以字符串哈希，开两个 map，将操作中和询问中本质串哈希值相同的字符串放在一起，再枚举桶内元素即可

对于 $2$ , $3$ 要求，我们开两个字典树。特别地，对于 $2$ 我们将 $A$ 反转，于是 $2$ 要求也转化为查询前缀可以和 $3$ 一样用字典树处理

如何快速查询前缀呢，注意到在字典树上有这样的一个性质：

如果 $A$ 是 $B$ 的前缀，在字典树上设 $f(S)$ 为 $S$ 字符串最后一个字符所在的节点 dfs 序， $g(S)$ 为 $S$ 字符串最后一个字符所在的节点子树中 dfs 序的最大值，则 $f(A) \leqslant f(B) \leqslant g(A)$

所以可以在字典树上求 dfn，对于 $2$ 要求即为 $f(t_A) \in [l1 , r1]$ 其中 $l1 = f(s_A) , r1 = g(s_A)$ 对于 $3$ 要求同理有 $f(t_B) \in [l2 , r2]$

于是原问题转化为二维数点， $(s1 , s2)$ 就是矩形， $(t1 , t2)$ 就是点对，分别对每个点对求出其被多少矩形包围。用扫描线处理一下即可，具体地可以将 $l , x$ 作为下标， $r , y$ 作为权值，对于下标扫一遍，扫描线可以用树状数组实现，注意要离散化下标

code

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 4e5 + 5;
const int M = 5e6 + 5;
const int mod = 998244353;
const int mod2 = 1e9 + 7;
const int P = 13131;

struct node{
	string pre , suf;
}ps[N] , pt[N];

struct trie{
	int ch[26] , dfn , lt;
}tr[M];

struct nline{
	int id , pr1 , pr2 , w;
};

struct ndot{
	int w , id;
};

int n , q , cnt;
int to[N << 1] , idx , tmp_a[N] , tmp_b[N] , tol;
int l1[N] , r1[N] , l2[N] , r2[N] , x[N] , y[N] , L[N] , X[N] , a[N] , ans[N];

map<int , vector<int> > mp1 , mp2;
vector<nline> v[N];
vector<ndot> g[N];

int hs(string s){
	int sum = 0;
	
	for(int i = 0 ; i < s.size() ; i ++){
		sum = (sum * P + s[i]) % mod;
	}
	return sum % mod;
}

// trie

int newnode(){
	++ cnt , tr[cnt].dfn = tr[cnt].lt = 0;
	for(int i = 0 ; i < 26 ; i ++){
		tr[cnt].ch[i] = 0;
	}
	return cnt;
}

void clear(){
	cnt = tol = 0;
	newnode();
}

int insert(string s){
	int now = 1;
	
	for(int i = 0 ; i < s.size() ; i ++){
		if(!tr[now].ch[s[i] - 'a']) tr[now].ch[s[i] - 'a'] = newnode();
		now = tr[now].ch[s[i] - 'a'];
	}
	return now;
}

void dfs(int u){
	tr[u].dfn = ++ tol;	
	for(int i = 0 ; i < 26 ; i ++){
		if(!tr[u].ch[i]) continue;
		dfs(tr[u].ch[i]);
	}
	tr[u].lt = tol;
}

// BIT

int b[M];

int lowbit(int x){
	return x & (-x);
}

int query(int x){
	int sum = 0;
	while(x){
		sum += b[x];
		x -= lowbit(x);
	}
	return sum;
}

void modify(int x , int k){
	if(!x) return;
	while(x < M){
		b[x] += k;
		x += lowbit(x);
	}
}

signed main(){
	cin >> n >> q;
	
	for(int i = 1 ; i <= n ; i ++){
		string S1 , S2;
		cin >> S1 >> S2;
		if(S1 == S2) continue;
		
		int l = 0 , r = S1.size() - 1;
		while(S1[l] == S2[l]) l ++;
		while(S1[r] == S2[r]) r --;
		
		string pa = S1.substr(0 , l) , pb = S1.substr(r + 1 , S1.size() - r - 1);
		string pc = S1.substr(l , r - l + 1) , pd = S2.substr(l , r - l + 1);
		reverse(pa.begin() , pa.end());
		
		ps[i] = {pa , pb};
		
		int base = (hs(pc) + mod) * (hs(pd) + 1) % mod2;
		to[++ idx] = base , mp1[base].push_back(i);
	}
	
	for(int i = 1 ; i <= q ; i ++){
		string S1 , S2;
		cin >> S1 >> S2;
		if(S1.size() != S2.size()) continue;
		
		int l = 0 , r = S1.size() - 1;
		while(S1[l] == S2[l]) l ++;
		while(S1[r] == S2[r]) r --;
		
		string pa = S1.substr(0 , l) , pb = S1.substr(r + 1 , S1.size() - r - 1);
		string pc = S1.substr(l , r - l + 1) , pd = S2.substr(l , r - l + 1);
		reverse(pa.begin() , pa.end());
		
		pt[i] = {pa , pb};

		int base = (hs(pc) + mod) * (hs(pd) + 1) % mod2;
		to[++ idx] = base , mp2[base].push_back(i);
	}
	sort(to + 1 , to + idx + 1);
	idx = unique(to + 1 , to + idx + 1) - (to + 1);

	for(int i = 1 ; i <= idx ; i ++){
		int idx1 = 0;
		clear();
		for(auto u : mp2[to[i]]) tmp_a[u] = insert(pt[u].pre);
		for(auto u : mp1[to[i]]) tmp_b[u] = insert(ps[u].pre); 
		dfs(1);
		for(auto u : mp1[to[i]]) l1[u] = tr[tmp_b[u]].dfn , l2[u] = tr[tmp_b[u]].lt , L[++ idx1] = l1[u] , L[++ idx1] = l2[u];
		for(auto u : mp2[to[i]]) x[u] = tr[tmp_a[u]].dfn , L[++ idx1] = x[u];
		
		clear();
		for(auto u : mp2[to[i]]) tmp_a[u] = insert(pt[u].suf);
		for(auto u : mp1[to[i]]) tmp_b[u] = insert(ps[u].suf);
		dfs(1);
		for(auto u : mp1[to[i]]) r1[u] = tr[tmp_b[u]].dfn , r2[u] = tr[tmp_b[u]].lt;
		for(auto u : mp2[to[i]]) y[u] = tr[tmp_a[u]].dfn;
		
		sort(L + 1 , L + idx1 + 1);
		idx1 = unique(L + 1 , L + idx1 + 1) - (L + 1);
		
		for(int i = 1 ; i <= idx1 + 1 ; i ++){
			g[i].clear() , v[i].clear();
		}
		for(auto u : mp1[to[i]]){
			int pl = lower_bound(L + 1 , L + idx1 + 1 , l1[u]) - L;
			v[pl].push_back({u , r1[u] , r2[u] , 1});
			
			pl = lower_bound(L + 1 , L + idx1 + 1 , l2[u]) - L;
			v[pl + 1].push_back({u , r1[u] , r2[u] , -1});
		}
		for(auto u : mp2[to[i]]){
			int px = lower_bound(L + 1 , L + idx1 + 1 , x[u]) - L;
			g[px].push_back({y[u] , u});
		}
		for(int i = 1 ; i <= idx1 + 1 ; i ++){
			for(auto u : v[i]){
				modify(u.pr1 , u.w); modify(u.pr2 + 1 , -u.w);
			}
			for(auto u : g[i]){
				ans[u.id] = query(u.w);
			}
		}
	}
	for(int i = 1 ; i <= q ; i ++){
		cout << ans[i] << '\n';
	}
	return 0;
}

目前还没有评论...

CSP-S 2025 总结

T1 社团招新

solution

code

T2 道路修复

solution

code

T3 谐音替换

solution

code

0 条评论

状态

开发

支持

关于

CSP-S 2025 总结

T1 社团招新

solution

code

T2 道路修复

solution

code

T3 谐音替换

solution

code

0 条评论

状态

开发

支持

关于

登录