题目链接
题解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
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?