2018年蓝桥杯C/C++B组国赛-调手表

题目

题目链接

题解

BFS。

题目大意：

假设当前的数是 0 0 0，可以选择 + k +k +k或 + 1 +1 +1再对 n n n取模来改变当前的数，因为对 n n n取模，所以当前的数总共可以变为 0 ∼ n − 1 0\sim n-1 0∼n−1，求从 0 0 0第一次变成这 n n n个数所需要加的最多次数。也就是说 0 0 0变成 1 1 1需要加 3 3 3次， 0 0 0变成 2 2 2需要加 4 4 4次，那么答案就是较大的数 4 4 4。

一开始想的是递推（动态规划），但是感觉转移不了。如果顺序枚举每个数，那么转移方程应该表示为该数从 + k +k +k转移过来或从 + 1 +1 +1转移过来，但如果转移前的状态还未确定，那么本状态也就是不确定或者不正确的，所以抛弃了这种方法。

换个思考方式，既然当前状态没法由 + k +k +k或从 + 1 +1 +1转移过来，那么不妨将该状态转移到 + k +k +k或 + 1 +1 +1状态上去，也就是说只需要让本状态所需要经过次数 + 1 +1 +1，就可以得到本状态对应的数 + k +k +k和 + 1 +1 +1所需要的次数了，前提是得到每个数的次数只能被赋值一次，因为只有第一次才是次数最少的（满足题目大意中“第一次”的要求），不难想到这与BFS有点像，控制一下每个数是否已经得到过了，如果得到过了就不再进行赋值了，只有没得到过的才进行赋值并加入队列用于更新其他数。

代码

#include
using namespace std;
const int N = 1e5+10;

int dp[N]; // dp[i]表示i的出现最少（第一次出现）需要按几次
int st[N]; // st[i]表示i是否已经进过队列，也即i是否已经被更新过了
int ans;

int main()
{
	int n, k;
	cin >> n >> k;
	
	queue  q;
	dp[0] = 0;
	st[0] = true;
	
	q.push (0);
	
	while (q.size ()) {
		int t = q.front ();
		ans = max (ans, dp[t]);
		q.pop ();
		
		int t1 = (t + k) % n;
		int t2 = (t + 1) % n;
		if (!st[t1]) 
			dp[t1] = dp[t] + 1, 
			st[t1] = true,
			q.push (t1);
		if (!st[t2])
			dp[t2] = dp[t] + 1, 
			st[t2] = true,
			q.push (t2);
	}	
	
	cout