百度站长工具官网,店招免费设计在线生成,中国施工企业管理协会官网,如何申请cn域名做网站一、前言
还是偏基础的bfs#xff0c;但是有几个题不是很好写
二、题目总览 三、具体题目
3.1 问题 A: 数据结构-队列-奇怪的电梯 我的代码
可以看成求一维平面的bfs最短路
#include bits/stdc.h
using i64 long long;
using pii std::pairint,int;
co…一、前言
还是偏基础的bfs但是有几个题不是很好写
二、题目总览 三、具体题目
3.1 问题 A: 数据结构-队列-奇怪的电梯 我的代码
可以看成求一维平面的bfs最短路
#include bits/stdc.h
using i64 long long;
using pii std::pairint,int;
constexpr int N 1e55,M 1e65,INF 0x3f3f3f3f;
std::vectorint a(N,0);
std::vectorbool vis(N,false);int n,st,ed;void bfs(){std::queuepii q;vis[st] true;pii p;p.first st,p.second 0;q.emplace(p);while(!q.empty()){auto t q.front();q.pop();if(t.firsted){std::cout t.second \n;return;}pii t1,t2;t1.first t.firsta[t.first];t1.second t.second1;if(t1.firstn!vis[t1.first]){vis[t1.first] true;q.emplace(t1);}t2.first t.first-a[t.first];t2.second t.second1;if(t2.first1!vis[t2.first]){vis[t2.first] true;q.emplace(t2);}}std::cout -1\n;
}void solve(){std::cin n st ed;for(int i 1;in;i) std::cin a[i];bfs();}
int main(){std::cin.tie(nullptr)-sync_with_stdio(false);int t 1;// std::cin t;for(int ti 0;tit;ti) {solve();}return 0;
}
3.2 问题 B: 连通块 我的代码
找全是1的联通块个数直接枚举每个点bfs当前未访问过的点即可
#include bits/stdc.h
using i64 long long;
using pii std::pairint,int;
constexpr int N 1e25,M 1e65,INF 0x3f3f3f3f;
int n,m;
int g[N][N];
bool vis[N][N];
int ans;
using node std::arrayint,3;
int dx[] {0,0,-1,1};
int dy[] {-1,1,0,0};
void bfs(int sx,int sy){std::queuenode q;node t;t[0] sx,t[1] sy,t[2] 0;q.emplace(t);vis[sx][sy] true;ans;while(!q.empty()){auto t q.front();q.pop();for(int i 0;i4;i){int u t[0]dx[i],v t[1]dy[i];if(u1||un||v1||vm||vis[u][v]||g[u][v]0) continue;node t1;vis[u][v] true;t1[0] u,t1[1] v,t1[2] t[2]1;q.emplace(t1);}}
}
void solve(){std::cin n m;for(int i 1;in;i){for(int j 1;jm;j){std::cin g[i][j];}}for(int i 1;in;i){for(int j 1;jm;j){if(!vis[i][j]g[i][j]1){bfs(i,j);}}}std::cout ans \n;
}
int main(){std::cin.tie(nullptr)-sync_with_stdio(false);int t 1;// std::cin t;for(int ti 0;tit;ti) {solve();}return 0;
}
3.3 问题 C: 广搜——营救 我的代码
用char读图不能用int后续就是简单的求二维平面的bfs最短路
#include bits/stdc.h
using i64 long long;
using pii std::pairint,int;
constexpr int N 1e35,M 1e65,INF 0x3f3f3f3f;
int n;
char g[N][N];
bool vis[N][N];
int sx,sy,ex,ey;
using node std::arrayint,3;
int dx[] {0,0,-1,1};
int dy[] {-1,1,0,0};void bfs(){std::queuenode q;node tt;tt[0] sx,tt[1] sy,tt[2] 0;q.emplace(tt);vis[sx][sy] true;while(!q.empty()){auto t q.front();q.pop();if(t[0]ext[1]ey){std::cout t[2] \n;return;}for(int i 0;i4;i){int u t[0]dx[i],v t[1]dy[i];if(u1||un||v1||vn||vis[u][v]||g[u][v]1) continue;vis[u][v] true;node t1;t1[0] u,t1[1] v,t1[2] t[2]1;q.emplace(t1);}}
}
void solve(){std::cin n;for(int i 1;in;i){for(int j 1;jn;j){std::cin g[i][j];}}std::cin sx sy ex ey;bfs();
}
int main(){std::cin.tie(nullptr)-sync_with_stdio(false);int t 1;// std::cin t;for(int ti 0;tit;ti) {solve();}return 0;
}
3.4 问题 D: 迷宫的最短路径 我的代码
注意输出不要漏单词或者空格其他没啥好说的
#include bits/stdc.h
using i64 long long;
using pii std::pairint,int;
constexpr int N 1e35,M 1e65,INF 0x3f3f3f3f;
int n,m;
char g[N][N];
bool vis[N][N];
int sx,sy,ex,ey;
int dx[] {0,0,-1,1};
int dy[] {-1,1,0,0};
using node std::arrayint,3;void bfs(){std::queuenode q;node tt;tt[0] sx,tt[1] sy,tt[2] 0;q.emplace(tt);vis[sx][sy] true;while(!q.empty()){auto t q.front();q.pop();if(t[0]ext[1]ey){std::cout The min steps are: t[2] !\n;return;}for(int i 0;i4;i){int u t[0]dx[i],v t[1]dy[i];if(u1||un||v1||vm||vis[u][v]||g[u][v]#) continue;vis[u][v] true;node t1;t1[0] u,t1[1] v,t1[2] t[2]1;q.emplace(t1);}}std::cout sorry!\n;
}void solve(){std::cin n m;for(int i 1;in;i){for(int j 1;jm;j){std::cin g[i][j];if(g[i][j]S){sxi,syj;}else if(g[i][j]G){exi,eyj;}}}bfs();
}
int main(){std::cin.tie(nullptr)-sync_with_stdio(false);int t 1;// std::cin t;for(int ti 0;tit;ti) {solve();}return 0;
}
3.5 问题 E: 象棋中的马之进阶 我的代码
求八方向二维平面最短路的bfs
#include bits/stdc.h
using i64 long long;
using pii std::pairint,int;
constexpr int N 1e35,M 1e65,INF 0x3f3f3f3f;
bool vis[N][N];
int sx,sy,ex,ey;
int dx[] {-2,-1,1,2,2,1,-1,-2};
int dy[] {1,2,2,1,-1,-2,-2,-1};
using node std::arrayint,3;void bfs(){std::queuenode q;node tt;tt[0] sx,tt[1] sy,tt[2] 0;q.emplace(tt);vis[sx][sy] true;while(!q.empty()){auto t q.front();q.pop();if(t[0]ext[1]ey){std::cout t[2] \n;return;}for(int i 0;i8;i){int u t[0]dx[i],v t[1]dy[i];if(u1||u9||v1||v10||vis[u][v]) continue;vis[u][v] true;node t1;t1[0] u,t1[1] v,t1[2] t[2]1;q.emplace(t1);}}std::cout 0 \n;
}
void solve(){std::cin sx sy ex ey;bfs();
}
int main(){std::cin.tie(nullptr)-sync_with_stdio(false);int t 1;// std::cin t;for(int ti 0;tit;ti) {solve();}return 0;
}
3.6 问题 F: 搜索——我的世界 我的代码
求三维空间最短路的bfs
#include bits/stdc.h
using i64 long long;
using pii std::pairint,int;
constexpr int N 1e25,M 1e65,INF 0x3f3f3f3f;int k,n,m;
char g[N][N][N];
bool vis[N][N][N];
int dx[] {0,0,-1,1,0,0};
int dy[] {-1,1,0,0,0,0};
int dz[] {0,0,0,0,1,-1};
using node std::arrayint,4;
int sx,sy,sz,ex,ey,ez;
void bfs(){std::queuenode q;node tt;tt[0] sz,tt[1] sx,tt[2] sy,tt[3] 0;q.emplace(tt);vis[sx][sy][sz] true;while(!q.empty()){auto t q.front();q.pop();if(t[0]ezt[1]ext[2]ey){std::cout t[3] \n;return;}for(int i 0;i6;i){int u t[0]dz[i],v t[1]dx[i],w t[2]dy[i];if(u1||uk||v1||vn||w1||wm||vis[u][v][w]||g[u][v][w]^) continue;vis[u][v][w] true;node t1;t1[0] u,t1[1] v,t1[2] w,t1[3] t[3]1;q.emplace(t1);}}std::cout 2333333 \n;
}
void solve(){std::cin k n m;for(int i 1;ik;i){for(int j 1;jn;j){for(int l 1;lm;l){std::cin g[i][j][l];if(g[i][j][l]S){sxj,syl,szi;}else if(g[i][j][l]E){exj,eyl,ezi;}}}}bfs();
}
int main(){std::cin.tie(nullptr)-sync_with_stdio(false);int t 1;// std::cin t;for(int ti 0;tit;ti) {solve();}return 0;
}
3.7 问题 G: 最小倍数 我的代码
不会爆long long思路见代码
#include bits/stdc.h
using i64 long long;
using pii std::pairint,int;
constexpr int N 1e55,M 1e65,INF 0x3f3f3f3f;
i64 n;void bfs(){std::queuei64 q;q.emplace(1);while(!q.empty()){auto t q.front();q.pop();if(t%n0){std::cout t \n;return;}q.emplace(t*10);q.emplace(t*101);}
}
void solve(){while(std::cin n){if(n0) break;bfs();}
}
int main(){std::cin.tie(nullptr)-sync_with_stdio(false);int t 1;// std::cin t;for(int ti 0;tit;ti) {solve();}return 0;
}
3.8 问题 H: 01组成的N的倍数 我的代码
会爆long long和unsigned long long而且用高精度也会超时时间复杂度卡得有点死只能用string
#include bits/stdc.h
using namespace std;
using i64 long long;
constexpr int N1e65;
struct node{string str;i64 sum;
} now,temp;
queuenode q;
int vis[N];
int n;
void bfs(){queuenode q;memset(vis,0,sizeof(vis));now.str1;now.sum1%n;vis[now.sum]1;q.push(now);while(!q.empty()){nowq.front();q.pop();if(now.sum0){cout now.str endl;break;}temp.strnow.str0;temp.sum(now.sum*10)%n;if(vis[temp.sum]0){vis[temp.sum]1;q.push(temp);}temp.strnow.str1;temp.sum(now.sum*101)%n;if(vis[temp.sum]0){vis[temp.sum]1;q.push(temp);}}
}
int main(){while(~scanf(%d,n)){bfs();}return 0;
}
3.9 问题 I: 新迷宫探险 我的代码
注意多组数据写法跟前面的求二维平面最短路的bfs一样
#include bits/stdc.h
using i64 long long;
using pii std::pairint,int;
constexpr int N 1e25,M 1e65,INF 0x3f3f3f3f;
int n;
char g[N][N];
bool vis[N][N];
int sx,sy,ex,ey;
int dx[] {0,0,-1,1};
int dy[] {-1,1,0,0};
using node std::arrayint,3;
void bfs(){std::queuenode q;node tt;tt[0] sx,tt[1] sy,tt[2] 0;vis[sx][sy] true;q.emplace(tt);while(!q.empty()){auto t q.front();q.pop();if(t[0]ext[1]ey){std::cout t[2] \n;return;}for(int i 0;i4;i){int u t[0]dx[i],v t[1]dy[i];if(u1||un||v1||vn||vis[u][v]||g[u][v]#) continue;vis[u][v] true;node t1;t1[0] u,t1[1] v,t1[2] t[2]1;q.emplace(t1);}}std::cout -1 \n;
}
void solve(){while(std::cin n){for(int i 1;in;i){for(int j 1;jn;j){std::cin g[i][j];}}memset(vis,false,sizeof vis);sx 1,sy 1,ex n,ey n;bfs();}
}
int main(){std::cin.tie(nullptr)-sync_with_stdio(false);int t 1;// std::cin t;for(int ti 0;tit;ti) {solve();}return 0;
}
3.10 问题 J: 山峰和山谷 我的代码
枚举每个没有访问过的点bfs看是否能够形成山峰或者山谷
#include bits/stdc.h
using i64 long long;
using pii std::pairint,int;
constexpr int N 1e35,M 1e65,INF 0x3f3f3f3f;
int n;
int g[N][N];
bool vis[N][N];
int ans1,ans2;
int dx[] {0,0,-1,1,-1,1,1,-1};
int dy[] {-1,1,0,0,1,1,-1,-1};using node std::arrayint,2;void bfs(int i,int j){std::queuenode q;node tt;tt[0] i,tt[1] j;q.emplace(tt);vis[i][j] true;bool flag1 false,flag2 false;int cnt 1;while(!q.empty()){auto t q.front();q.pop();for(int i 0;i8;i){int u t[0]dx[i],v t[1]dy[i];if(u1||un||v1||vn||(vis[u][v]g[u][v]g[t[0]][t[1]])) continue;if(g[u][v]g[t[0]][t[1]]) flag1true;else if(g[u][v]g[t[0]][t[1]]) flag2true;else{cnt;vis[u][v] true;node t1;t1[0] u,t1[1] v;q.emplace(t1);}}}if(flag1flag2) return;if(flag1) ans1;else if(flag2) ans2;if(cntn*n) ans1,ans2;
}
void solve(){std::cin n;for(int i 1;in;i){for(int j 1;jn;j){std::cin g[i][j];}}for(int i 1;in;i){for(int j 1;jn;j){if(!vis[i][j]){bfs(i,j);}}}std::cout ans1 ans2 \n;
}
int main(){std::cin.tie(nullptr)-sync_with_stdio(false);int t 1;// std::cin t;for(int ti 0;tit;ti) {solve();}return 0;
}
3.11 问题 K: 兔兔之漂亮图 我的代码
这题看代码吧暂时不知道要怎么说清楚这个思路
#include bits/stdc.h
using i64 long long;
using pii std::pairint,int;
constexpr int N 3e55,M 1e65,INF 0x3f3f3f3f;
constexpr int P 998244353;i64 power(i64 a, i64 b) {i64 res 1;for (; b; b / 2, a a*a%P) {if (b % 2) {res res*a%P;}}return res;
}std::vectorstd::vectorint edges(N,std::vectorint());
std::vectorint a(N,0);
int n,m;
i64 ans;
std::queueint q;
i64 t 2;void bfs(){for(int i 1;in;i){if(a[i]!0) continue;a[i] 1;i64 cnt1 1,cnt2 0;q.emplace(i);while(!q.empty()){auto u q.front();q.pop();for(auto v:edges[u]){if(a[v]0){a[v] 3-a[u];if(a[v]1) cnt11;else cnt21;q.emplace(v);}else if(a[u]a[v]!3){ans 0;break;}}}if(ans0) break;//power(2,cnt)ansans*((power(t,cnt1)%Ppower(t,cnt2)%P)%P)%P;}}
void solve(){std::cin n m;for(int i 1;in;i){edges[i].clear();a[i] 0;}ans 1;while(m--){int u,v;std::cin u v;edges[u].emplace_back(v);edges[v].emplace_back(u);}bfs();std::cout ans \n;
}
int main(){std::cin.tie(nullptr)-sync_with_stdio(false);int t 1;std::cin t;for(int ti 0;tit;ti) {solve();}return 0;
}
3.12 问题 L: 兔兔的导航系统 我的代码
原题
2024算法基础公选课练习三DFS1的L题
#include bits/stdc.h
using i64 long long;
using pii std::pairint,int;
constexpr int N 2e55,M 1e65,INF 0x3f3f3f3f;int n,m,k;
std::vectorstd::vectorint edges(N,std::vectorint());
std::vectorstd::vectorint reverse_edges(N,std::vectorint());
std::vectorbool vis(N,false);
std::vectorint dist(N,INF);
std::vectorint p(N,0);
int st,ed;
int maxn0,minn0;
void bfs() {std::queueint q;vis[st] true;dist[st] 0;q.emplace(st);while(!q.empty()) {auto t q.front();q.pop();for(int i 0;ireverse_edges[t].size();i) {int to reverse_edges[t][i];if(vis[to]) continue;vis[to] true;dist[to] dist[t]1;q.emplace(to);}}
}void solve(){std::cin n m;while(m--){int u,v;std::cin u v;edges[u].emplace_back(v);reverse_edges[v].emplace_back(u);}std::cin k;for(int i 1;ik;i) std::cin p[i];st p[1],ed p[k];bfs();for(int i 1;ik-1;i) {int u p[i],v p[i1];bool flag false;//用于判断是否当前u-v是最短路for(int j 0;jedges[u].size();j) {int w edges[u][j];if(dist[w]dist[u]-1) {if(vw) {flag true;}else {maxn;}}}if(!flag) minn,maxn;}std::cout minn maxn \n;
}
int main(){std::cin.tie(nullptr)-sync_with_stdio(false);int t 1;// std::cin t;for(int ti 0;tit;ti) {solve();}return 0;
}
3.13 问题 M: 龙哥的换根树 我的代码
bfs两次然后换根dp
#include bits/stdc.h
using i64 long long;
using pii std::pairint,int;
constexpr int N 2e55,M 1e65,INF 0x3f3f3f3f;
i64 n,k,c;
void bfs(int root,std::vectorstd::vectorint edges,std::vectorbool vis,std::vectori64 dist){std::queueint q;vis[root] true;q.emplace(root);dist[root] 0;while(!q.empty()){auto u q.front();q.pop();for(auto v:edges[u]){if(vis[v]) continue;vis[v] true;dist[v] dist[u]1;q.emplace(v);}}
}
void solve(){std::cin n k c;std::vectorstd::vectorint edges(n5,std::vectorint());std::vectorbool vis(n5,false);std::vectori64 dist(n5,INF);//vector建边for(int i 1;in-1;i){int u,v;std::cin u v;edges[u].emplace_back(v);edges[v].emplace_back(u);}i64 ans0,max0,tmp0,leaf1;bfs(1,edges,vis,dist);//拷贝dist数组留用std::vectori64 prev_dist(n5);std::copy(dist.begin(),dist.end(),prev_dist.begin());//找到最远的叶子结点leaf和这个最远距离maxfor(int i 1;in;i){if(dist[i]max){max dist[i];leaf i;}}//初始化for(int i 1;in;i){vis[i] false;dist[i] INF;}//以这个叶子结点为根进行bfsbfs(leaf,edges,vis,dist);//枚举换根到每个点最大价值for(int i 1;in;i){ans std::max(ans,dist[i]*k-prev_dist[i]*c);}std::cout ans \n;
}
int main(){std::cin.tie(nullptr)-sync_with_stdio(false);int t 1;std::cin t;for(int ti 0;tit;ti) {solve();}return 0;
}
