一、找素数
题目链接：找素数跳转链接
题目要求：
找第100002个素数。
解题思路：
一个签到题，暴力求解就好啦，要注意一下while循环里面的num++不要放在后面。
#include<bits/stdc++.h> using namespace std; bool pd(int x) { for(int i=2;i<=sqrt(x);i++) { if(x%i==0) { return false; } } return true; } int main() { int m = 0,num = 1; while(m!=100002) { num++; if(pd(num)) { m++; } } cout<<num; return 0; }
二、分考场
题目链接：分考场
这个题我也不会，5115，全排列应该能骗分，大家有思路的可以去看看，后面会补。
三、合根植物
题目链接：进去登录点题集 真题 搜索合根植物
题目要求：
w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。
这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？
解题思路：
这是一个并查集的题目，很简单，套板子就好了，不会并查集的话我这里放一个链接，可以去看看，我觉得讲得很通透。
链接：通俗易懂并查集
#include<bits/stdc++.h> using namespace std; const int N = 1000010; int m,n,k,pre[N],ans; bool vis[N]; void init() { memset(vis,0,sizeof(vis)); for(int i=1;i<=n*m;i++) { pre[i] = i; } } int find(int x) { if(x!=pre[x]) { return pre[x] = find(pre[x]); } return x; } void join(int x,int y) { int xx = find(x); int yy = find(y); if(xx!=yy) { pre[yy] = xx; } } int main() { scanf("%d%d%d",&n,&m,&k); init(); for(int i=0;i { int x,y; scanf("%d%d",&x,&y); join(x,y); } for(int i=1;i<=n*m;i++) { vis[find(i)] = 1; } for(int i=1;i<=n*m;i++) { ans += vis[i]; } cout<<ans<<endl; return 0; }
四、大胖子走迷宫
题目链接：进去登录点题集 真题 搜索大胖子走迷宫
题目要求：
解题思路：这是一个非常恶心（我认为）的bfs题，一开始我看的蒙了怎么还能变身？？？？这是人吗，我减肥咋不能这么快，不过作为聪明的OIer（不是，肯定有解决的办法）
咱们先读入地图啊 然后弄一个判断是否走过的数组 还有上下左右四个方向啊 结构体（pair也行）
一个判断越界的函数 一个判断当前体重的函数
一个bfs（不会的赶紧去学）
案例图
+++++++++
+++++++++
+++++++++
+++++++++
+++++++++
***+*****
+++++++++
+++++++++
+++++++++
你这胖子体型占5*5，在33的地方，进队列！判断！因为死胖子一开始很胖 判断的时候记得根据他提醒判断循环，然后如果每次都让队列进一次死胖子原地不动 然后走四个方向 如果这个方向能走 那么把这个方向压入队头 到时候取出来的就是这个方向的位置了 死胖子经过时间流逝会变瘦 然后判断一下即可。
#include <bits/stdc++.h> using namespace std; const int N=310; char s[N][N];//地图 int n,k; int dx[] = {1,0,0,-1};//方向~ int dy[] = {0,-1,1,0}; bool vis[N][N]; struct node{ int x,y,num,len;//位置 时间 体重 }; bool judge(int x,int y,int len) //判断是否搜过越界 { if(vis[x][y]||y+len>n||y-len<1||x+len>n||x-len<1) { return 0; } for(int i=x-len;i<=x+len;i++)//如果不越界没搜过 就看当前往这个方向走会不会有障碍 { for(int j=y-len;j<=y+len;j++)//根据体重范围判断 { if(s[i][j]=='*') { return 0; } } } return 1; } int f(int cnt)//当前的体重哦哦哦哦哦 { if(cnt { return 2; } else if(cnt<2*k) { return 1; } return 0; } int bfs() { queueq;//新的队列q q.push({3,3,0,2});//把位置 时间 体重干进去 vis[3][3]=1;//搜过了 while(q.size()) { node t=q.front(); q.pop(); int x=t.x; int y=t.y; int num=t.num; int len=t.len; if(x==n-2&&y==n-2) { return num; } if(len!=0)//不是最轻的情况 { q.push({x,y,num+1,f(num+1)});//原地不动 } for(int i=0;i<4;i++) { int nx=x+dx[i]; int ny=y+dy[i]; if(judge(nx,ny,len))//能搜 { vis[nx][ny]=1; q.push({nx,ny,num+1,f(num+1)});//干干干 } } } } int main() { cin>>n>>k; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cin>>s[i][j]; } } int ans=bfs(); cout<<ans; return 0; }
总结：
今天题目bfs变种大家要好好理解方便自己更熟练的使用bfs。
