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

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

Easy 小美的外卖订单编号

简要题意

每天的第 个订单起初有编号 ，为防止编号过大，当某个订单编号超过 时就从 开始重新编号。

多次给定 ，询问第 单的编号。

Solution

答案即为 。

Code

void R()
{
	int q;
	cin>>q;
	while (q--)
	{
		int m,x;
		cin>>m>>x;
		cout<<(x-1)%m+1<<'\n';
	}
	return;
}

Medium 买卖股票的最好时机(一)

简要题意

给定连续 天股票价格，你可以选择至多一天买进一份股票，并在之后选择一天卖出这份股票，求最大收益。

Solution

预处理前缀 与后缀 ，每个位置上二者之差取 即为答案。

Code

void R()
{
	int n,ans=0;
	cin>>n;
	vector<int> p(n),mn(n),mx(n);
	for (int &x:p) cin>>x;
	mn[0]=p[0];
	mx[n-1]=p[n-1];
	for (int i=1;i<n;i++)
		mn[i]=min(mn[i-1],p[i]);
	for (int i=n-2;i>=0;i--)
		mx[i]=max(mx[i+1],p[i]);
	for (int i=0;i<n;i++)
		ans=max(ans,mx[i]-mn[i]);
	cout<<ans;
	return;
}

Hard 数位染色

简要题意

给一个数，问能否将这个数的所有数位分成两份，使得两份内的数的和相等。

Solution

考虑对所有数位做一个背包，如果能取到所有数位之和一半的值，就说明有解。

Code

void R()
{
	i64 x,sum=0;
	cin>>x;
	vector<int> dp(163);
	dp[0]=1;
	for (int t=x%10;x;x/=10,t=x%10)
	{
		for (int i=162;i>=t;i--)
			dp[i]|=dp[i-t];
		sum+=t;
	}
	cout<<(sum%2==0&&dp[sum/2]?"Yes":"No");
	return;
}