调手表
题目 调手表
思路分析
感觉是bfs 求某点到任意点的最短距离 的最大值
但是 每一步的选法是不定的 即 可以走1步 也可以走k步 这里涉及一个选择的问题
也就是说 在这个图里面 权并不是固定为1的
但这个数据范围有些过大 感觉最短路……
事实是居然可以全过 蓝桥杯啊蓝桥杯
或者好像还可以用跳台阶的思路
从原本的 到第n阶至少需要多少步 变成到任意阶至少需要多少步 然后取一个max 其实就是最后取个max(f[1]~f[n])
照思路来写的话 是这样
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=1e5+10;
int f[N];//到i点需要的最小步数 从两种可能的来 (i+n-1)%n点走1步 或者(i+n-k)%n点走k步
int n,k;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
memset(f,0x3f,sizeof f);//因为求最小步数 所以初始化为最大值 便于转移
f[0]=0,f[1]=1,f[k]=1;
for(int i=0;i<n;i++){
f[i]=min({f[i],f[(i+n-1)%n]+1,f[(i+n-k)%n]+1});
}
int res=-1;
for(int i=0;i<n;i++){
res=max(res,f[i]);
}
cout<<res;
return 0;
}
只能过五个
有个问题是 时间是环状的 需要处理循环依赖和周期性的问题
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int f[N];
int n,k;
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n >> k;
memset(f, 0x3f, sizeof(f));
f[0]=0,f[1]=1,f[k]=1;
// 由于环形结构，可能需要多次遍历来确保所有状态达到最优
bool changed = true;
while (changed) {
changed = false;
for (int i = 0; i < n; i++) {
int new_fi=min(f[(i+n-1)%n],f[(i+n-k)%n])+1;
if (new_fi < f[i]) {
f[i] = new_fi;
changed = true;
}
}
}
int res=-1;
for(int i=0;i<n;i++){
res=max(res,f[i]);
}
cout<<res;
return 0;
}
很容易忽略这一点 害
这怎么说呢 这种题目在事先不知道的情况下 能用bfs但是没把握全过 可dp一不小心可能满盘皆输
太抽象了
有这么简单？ 4道dfs、bfs 真练好暴力蓝桥杯随便打啊
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=1e5+10;
int d[N];
int n,k,res=-1;
int bfs(int u){
queue<int> q;
memset(d,-1,sizeof d);
q.push(u);
d[u]=0;
while(!q.empty()){
int cur=q.front();q.pop();
res=max(res,d[cur]);
if(d[(cur+1)%n]==-1){
d[(cur+1)%n]=d[cur]+1;
q.push((cur+1)%n);
}
if(d[(cur+k)%n]==-1){
d[(cur+k)%n]=d[cur]+1;
q.push((cur+k)%n);
}
}
return res;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
cout<<bfs(0);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int f[N];
int n,k;
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n >> k;
memset(f, 0x3f, sizeof(f));
f[0]=0,f[1]=1,f[k]=1;
// 由于环形结构，可能需要多次遍历来确保所有状态达到最优
bool changed = true;
while (changed) {
changed = false;
for (int i = 0; i < n; i++) {
int new_fi=min(f[(i+n-1)%n],f[(i+n-k)%n])+1;
if (new_fi < f[i]) {
f[i] = new_fi;
changed = true;
}
}
}
int res=-1;
for(int i=0;i<n;i++){
res=max(res,f[i]);
}
cout<<res;
return 0;
}
💬 评论