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

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

Easy 表示数字

简要题意

给一个字符串，将每个完整的连续数字子串左右添上一对 *。

Solution

记录上个字符是不是数字，如果发生变化就添上 *，记得特判结尾。

Code

void R()
{
	bool t=0;
	string s;
	cin>>s;
	for (char c:s)
	{
		if (t^isdigit(c))
			cout<<'*',t^=1;
		cout<<c;
	}
	if (t) cout<<'*';
	return;
}

Medium 球格模型（简单版）

简要题意

给一个 网格，你可以向每格中放置任意数量的小球。

现要把恰好 个小球放入网格中，使得每行每列都至少存在一个小球。

构造方案或报告无解。

Solution

如果能对角线放置，每个球占掉一行一列显然最优。

对于一个长方形网格，对角线放置后会留下若干行/列未放置，再在对应行/列上任意一个位置放一个球就好。

若有剩余的球就随便放，若小球不足则无解。

Code

void R()
{
	auto ed=[&]()->void
	{
		cout<<-1;
		exit(0);
	};

	int n,m,k;
	cin>>n>>m>>k;
	vector<vector<int>> a(n,vector<int>(m));
	for (int i=0;i<min(n,m);i++)
		if (k) a[i][i]=1,k--;
		else ed();
	for (int i=min(n,m);i<n;i++)
		if (k) a[i][0]=1,k--;
		else ed();
	for (int i=min(n,m);i<m;i++)
		if (k) a[0][i]=1,k--;
		else ed();
	a[0][0]+=k;
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
			cout<<a[i][j]<<" \n"[j+1==m];
	return;
}

Hard 【模板】01背包

简要题意

给一个容量为 的背包和 个体积为 重量为 的物品，求向包中放入某些物品/放满背包后，包中物品的最大价值。

Solution

标题已经告诉你解法了， 背包。

设 代表背包已占用 空间的最大价值。

考虑放入一个体积为 重量为 的物品，有转移：

答案分别是 数组最大值和最后一位。

Code

void R()
{
	int n,V;
	cin>>n>>V;
	vector<int> dp(V+1,-1e9);
	dp[0]=0;
	for (int i=0;i<n;i++)
	{
		int v,w;
		cin>>v>>w;
		for (int j=V;j>=v;j--)
			dp[j]=max(dp[j],dp[j-v]+w);
	}
	cout<<*max_element(dp.begin(),dp.end())<<'\n'<<(dp[V]<0?0:dp[V]);
	return;
}