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

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

Easy 游游的整数切割

简要题意

给一个正整数，求把它划为前后两部分，使得两个数相加为偶数的方案数。

Solution

相当于数有多少个位置的奇偶性与最低位相同。

Code

void R()
{
	int ans=0;
	string s;
	cin>>s;
	for (char c:s)
		ans+=!((c^s.back())&1);
	cout<<ans-1;
	return;
}

Medium 矩阵的最小路径和

简要题意

给一个 的矩阵，选择一条从左上到右下的最短非降路径，记路径上各格内数字之和为该路径的权值，求最小路径权值。

Solution

记 为 到 的最小路径权值，有转移：

即为答案。

Code

void R()
{
	constexpr int inf=1e9;
	int n,m;
	cin>>n>>m;
	vector<vector<int>> a(n,vector<int>(m,inf)),dp(a);
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
			cin>>a[i][j];
		
	dp[0][0]=a[0][0];
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
		{
			if (i) dp[i][j]=min(dp[i][j],dp[i-1][j]+a[i][j]);
			if (j) dp[i][j]=min(dp[i][j],dp[i][j-1]+a[i][j]);
		}
	cout<<dp[n-1][m-1];
	return;
}

Hard 旅游

简要题意

给定一棵 点的树，起初树上每个节点都未染色，随后每次可以选择一个未染色节点，将它和与其相邻的节点都染色。钦定第一次染色节点为 ，求最多能进行多少次染色。

Solution

先钦定 为树根。

设 分别表示节点 不曾被选择/被选择时，其子树内最多能进行多少次染色，有转移：

即为答案。

Code

void R()
{
	int n,s;
	cin>>n>>s;
	s--;
	vector<int> dep(n);
	vector<vector<int>> adj(n),dp(n,vector<int>(2));
	for (int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		u--,v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	auto dfs=[&](auto &self,int u,int f)->void
	{
		dp[u][1]=1;
		for (int v:adj[u])
		{
			if (v==f) continue;
			dep[v]=dep[u]+1;
			self(self,v,u);
			dp[u][0]+=max(dp[v][0],dp[v][1]);
			dp[u][1]+=dp[v][0];
		}
	};

	dfs(dfs,s,s);
	cout<<dp[s][1];
	return;
}