[CSP-S 2025]重游记

userId_undefined
ymhh
倔强青铜空间掌握者CSP-J二等奖

2026-10-02 00:08:49

发布于：广东

41阅读
0回复
0点赞

提示

我只做前面两道题目，ee

T1

注意到至多只有一个社团会超人，因此考虑将人多的社团放到其他社团去

#include<algorithm>
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
const int N = 1e5;
int T;
vector<int> instead;
int cnt1,cnt2,cnt3,ans;
int n,a[N+5][4],idx[N+5];

void solve()
{
	instead.clear();
	cnt1 = cnt2 = cnt3 = ans = 0;
	
	cin>>n;
	for(int i=1;i<=n;i++) 
	{
		for(int j=1;j<=3;j++) cin>>a[i][j];
		if(a[i][1]>=max(a[i][2],a[i][3])) 
		{
			cnt1++;idx[i] = 1;
			ans+=a[i][1];
		}
		else if(a[i][2]>=max(a[i][1],a[i][3]))
		{
			cnt2++;idx[i] = 2;
			ans+=a[i][2];
		}
		else if(a[i][3]>=max(a[i][1],a[i][2]))//这里要有else，不然如果a[i][1]=a[i][2]=a[i][3]就会重复算
		{
			cnt3++;idx[i] = 3;
			ans+=a[i][3];
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		if(cnt1>n/2)
		{
			if(idx[i]==1) instead.push_back(a[i][1]-max(a[i][2],a[i][3]));
		}
		if(cnt2>n/2)
		{
			if(idx[i]==2) instead.push_back(a[i][2]-max(a[i][1],a[i][3]));
		}
		if(cnt3>n/2)
		{
			if(idx[i]==3) instead.push_back(a[i][3]-max(a[i][1],a[i][2]));
		}
	}
	sort(instead.begin(),instead.end());
	
	for(int i=0;i<max(cnt1,max(cnt2,cnt3))-n/2;i++) ans-=instead[i];
	
	cout<<ans<<'\n';
}

int main()
{
	cin>>T;
	while(T--) solve();
	return 0;
}

T2

注意到 k≤10k\le 10，考虑 2k2^k 枚举改造哪些乡村。

你会发现，不用每次都排序，可以先将 mm 条边排好序，乡村的边借用链表思想。

目前是 O(mlog⁡m+2k(m+nk))O(m \log m+2^k(m+nk)) 会超时。

注意到可以先筛选出 n−1n-1 条边，因此可以变为 O(mlog⁡m+2knk)O(m \log m+2^knk)。

#include<algorithm>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int N = 1e4;
const int M = 1e6;
struct edge
{
	int u,v,w;
}a[N+10*N+5],box[M+5];
bool can[15];
ll ans = 2e18;
int n,m,k,tot,c[N+5],fa[N+15];

bool cmp(edge x,edge y)
{
	return x.w<y.w;
}

void init(bool flag)
{
	if(flag) memset(can,false,sizeof(can));
	for(int i=1;i<=n+k;i++)
	{
		fa[i] = i;
	}
}

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

void merge(int u,int v)
{
	u = find(u),v = find(v);
	if(u!=v) fa[u] = v;
}

void input()
{
	init(false);
	
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		
		box[i] = {u,v,w};	
	}
	sort(box+1,box+1+m,cmp);
	
	for(int i=1;i<=m;i++)
	{
		int u = find(box[i].u);
		int v = find(box[i].v);
		
		if(u!=v)
		{
			merge(u,v);
			a[++tot] = box[i];
		}
		if(tot==n-1) break;
	}
}

void sol(int mask)
{
	ll res = 0;
	int cnt = 0;
	init(true);
	
	for(int i=0;i<k;i++)
	{
		if(mask&(1<<i)) 
		{
			cnt++;
			res+=c[i+1];
			can[i+1] = true;
		}
		if(res>ans) return ;
	}
	
	int used = 0;
	for(int i=1;i<=tot;i++)
	{
		int u = a[i].u;
		int v = a[i].v;
		
		if(u>n&&(!can[u-n])) continue;
		if(v>n&&(!can[v-n])) continue;
		
		int fu = find(u);
		int fv = find(v);
		if(fu!=fv)
		{
			used++;
			merge(u,v);
			res+=a[i].w;
		}
		
		if(used==cnt+n-1) break;
	}
	
	if(ans>res) ans = res;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	cin>>n>>m>>k;
	input();
	for(int i=1;i<=k;i++)
	{
		cin>>c[i];
		for(int j=1;j<=n;j++)
		{
			int w;
			cin>>w;
			
			a[++tot] = {i+n,j,w};
		}
	}
	sort(a+1,a+1+tot,cmp);
	
//	cout<<"check tot "<<tot<<'\n';
	
	for(int mask=0;mask<(1<<k);mask++)
	{
		sol(mask);
	}
	
	cout<<ans;
	return 0;
}

后续改题

T1

我学到了代码实现方法

T2

其实完全不用链表的插入方式，可以之间将 n−1+nkn-1+nk 条边排好序，在后续处理中遇到未加入的乡村直接跳过即可。

总结

题目整体难度不大，主要是代码能力的考验

userId_undefined
去预览
0/2000

全部评论 8

热门讨论