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

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

Easy 小欧的括号嵌套

简要题意

构造一个长度为 ，最大嵌套层数为 的合法括号序列。

Solution

先构造一个 层括号，再放剩下 对括号即可。

Code

void R()
{
	int n,r;
	cin>>n>>r;
	for (int i=0;i<r;i++) cout<<'(';
	for (int i=0;i<r;i++) cout<<')';
	while ((n--)>r) cout<<"()";
	return;
}

Medium 不相邻取数

简要题意

给一个正数数组，要求不相邻取数，求取出数字和的最大值。

Solution

因为是正数数组，所以不可能有连续三个数不取。

记 表示取数以 结尾，取出数字和的最大值，有转移：

即为答案。

Code

void R()
{
	int n;
	cin>>n;
	vector<i64> a(n),dp(n);
	for (i64 &x:a) cin>>x;
	for (int i=0;i<n;i++)
	{
		if (i>1) dp[i]=max(dp[i],dp[i-2]);
		if (i>2) dp[i]=max(dp[i],dp[i-3]);
		dp[i]+=a[i];
	}
	cout<<*max_element(dp.begin(),dp.end());
	return;
}

Hard 小红的树

简要题意

给一棵有根树，对部分节点进行染色，多次询问子树内染色点数。

Solution

直接 DFS 预处理一遍子树内染色点数即可 应答。

Code

void R()
{
	int n;
	string s;
	cin>>n;
	vector<int> siz(n);
	vector<vector<int>> adj(n);
	for (int i=1;i<n;i++)
	{
		int p;
		cin>>p;
		adj[p-1].push_back(i);
	}
	cin>>s;

	auto dfs=[&](auto &self,int u,int f)->void
	{
		siz[u]=(s[u]=='R');
		for (int v:adj[u])
		{
			if (v==f) continue;
			self(self,v,u);
			siz[u]+=siz[v];
		}
	};

	dfs(dfs,0,0);

	int q;
	cin>>q;
	while (q--)
	{
		int x;
		cin>>x;
		cout<<siz[x-1]<<'\n';
	}
	return;
}