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

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

Easy ranko的手表

简要题意

给两个 xx:xx 形式的时间，但部分数位被替换为 ?，保证前者小于后者，求前后者相差时间可能的最大最小值。

Solution

枚举前后两个时间，判断二者是否满足形式，对所有满足的时间差取最值就是答案。

Code

void R()
{
	auto chk=[&](int x,string &s)->bool
	{
		int hh=x/60,mm=x%60;
		string tmp;
		tmp+=hh/10+'0';
		tmp+=hh%10+'0';
		tmp+=':';
		tmp+=mm/10+'0';
		tmp+=mm%10+'0';
		for (int j=0;j<5;j++)
			if (tmp[j]!=s[j]&&s[j]!='?')
				return 0;
		return 1;
	};

	int mn=1e9,mx=0;
	string s,t;
	cin>>s>>t;
	for (int i=0;i<1440;i++)
		for (int j=i+1;j<1440;j++)
			if (chk(i,s)&&chk(j,t))
				mn=min(mn,j-i),mx=max(mx,j-i);
	cout<<mn<<' '<<mx;
	return;
}

Medium 跳台阶

简要题意

从 级开始，每次可以向上跳 级台阶，求跳到 级台阶的不同方案数。

Solution

答案递推式为 。

等价于求斐波那契数列的第 项，直接递推即可。

Code

int jumpFloor(int n)
{
    int now=1,lst=0;
    while (n--)
    {
        now+=lst;
        lst=now-lst;
    }
    cout<<now;
    return now;
}

Hard [CQOI2007]涂色PAINT

简要题意

给定一个目标字符串。刚开始你有一个等长的空白画板。

每次操作你可以对一个区间写上相同的字母，求在画板上书写出目标字符串所需最小步数。

Solution

设 表示在区间 上都写好目标位置字符的最小步数，有转移：

即为答案。

Code

void R()
{
	constexpr int inf=1e9;
	string s;
	cin>>s;
	int n=s.size();
	vector<vector<int>> dp(n,vector<int>(n,inf));
	for (int i=0;i<n;i++) dp[i][i]=1;

	for (int len=1;len<n;len++)
		for (int l=0,r=len;r<n;l++,r++)
		{
			if (s[l]==s[r]) dp[l][r]=min(dp[l+1][r],dp[l][r-1]);
			else
			{
				for (int k=l;k<r;k++)
					dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
			}
		}
	cout<<dp[0][n-1];
	return;
}