牛客春招刷题训练营 - 2025.3.25 题解

活动地址：牛客春招刷题训练营 - 编程打卡活动

Easy 构造C的歪

简要题意

找到一个整数 ，使得 排序后构成等差数列。

Solution

令 是等差邻项，构造下一项就好。

Code

void R()
{
	i64 a,b,c;
	cin>>a>>b;
	if (a>=b) swap(a,b);
	c=2*b-a;
	cout<<c;
	return;
}

Medium 查找两个字符串a,b中的最长公共子串

简要题意

求 的最长公共子串。若有重复，输出短串中最早出现的那个。

Solution

数据范围很小，暴力枚举长串子串用 hash/map/unordered_map 记录，在短串中从长到短从前到后枚举子串 check 即可。

Code

void R()
{
	map<string,bool> mp;
	string s,t;
	cin>>s>>t;
	if (s.size()<t.size()) swap(s,t);
	int n=s.size(),m=t.size();
	for (int i=0;i<n;i++)
		for (int j=1;i+j<=n;j++)
			mp[s.substr(i,j)]=1;

	for (int j=m;j>=1;j--)
		for (int i=0;i+j<=m;i++)
			if (mp.count(t.substr(i,j)))
			{
				cout<<t.substr(i,j)<<'\n';
				return;
			}
	return;
}

Hard 气球谜题

简要题意

个气球排成一排，每个气球有一个初始颜色，颜色共有三种。

你可以花费 的代价对第 个气球染色，求让所有同色气球连续摆放的最小代价。

Solution

状压 DP。

考虑确定第 个气球的代价需要什么前置条件？

需要确定第 个气球是什么颜色，还要知道之前有没有摆过这个颜色的气球，第 个气球是不是这个颜色。

于是想到设 表示摆完第 个气球，已经摆过气球颜色的状压为 S，第 个气球的颜色是 ，且摆放方案合法的最小代价。

转移方程为： 。

Code

void R()
{
	int n;
	string s;
	cin>>n>>s;
	vector<int> t(n);
	vector<vector<array<i64,3>>> dp(n,vector<array<i64,3>>(8,{inf,inf,inf}));
	for (int &x:t) cin>>x;
	for (int i=0;i<3;i++)
		if (s[0]=='0'+i)
			dp[0][1<<i][i]=0;
		else
			dp[0][1<<i][i]=t[0];

	//dp[i-1][S][k]->dp[i][S|(1<<j)][j]
	for (int i=1;i<n;i++)
		for (int j=0;j<3;j++)
			for (int k=0;k<3;k++)
				for (int S=0;S<8;S++)
				{
					if ((S>>j&1)&&k!=j)
						continue;
					i64 con=dp[i-1][S][k];
					if (s[i]!='0'+j) con+=t[i];
					dp[i][S|(1<<j)][j]=min(dp[i][S|(1<<j)][j],con);
				}

	i64 ans=inf;
	for (int i=0;i<8;i++)
		for (int j=0;j<3;j++)
			ans=min(ans,dp[n-1][i][j]);
	cout<<ans<<'\n';
	return;
}