您当前的位置: 首页 >  蓝桥杯

不牌不改

暂无认证

  • 0浏览

    0关注

    422博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

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

不牌不改 发布时间:2022-03-16 20:07:12 ,浏览量:0

题目

题目链接

题解

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             
关注
打赏
1662186765
查看更多评论
0.0760s