????马上就要蓝桥杯了,最后的这几天尤为重要,不可懈怠哦????
1.长草
-
题目
-
题目描述
小明有一块空地,他将这块空地划分为 n 行 m 列的小块,每行和每列的长度都为 1。
小明选了其中的一些小块空地,种上了草,其他小块仍然保持是空地。
这些草长得很快,每个月,草都会向外长出一些,如果一个小块种了草,则它将向自己的上、下、左、右四小块空地扩展,
这四小块空地都将变为有草的小块。请告诉小明,k 个月后空地上哪些地方有草。
输入描述
输入的第一行包含两个整数 n*,*m。
接下来 n 行,每行包含 m 个字母,表示初始的空地状态,字母之间没有空格。如果为小数点,表示为空地,如果字母为 g,表示种了草。
接下来包含一个整数 k。 其中,2≤n,m≤1000,1≤k≤1000。
输出描述
输出 n 行,每行包含 m 个字母,表示 k 个月后空地的状态。如果为小数点,表示为空地,如果字母为 g,表示长了草。
输入输出样例
示例
输入
4 5 .g... ..... ..g.. ..... 2
输出
gggg. gggg. ggggg .ggg.
-
第一次 AC 0%
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; int const N=1100; int n,m,k; char g[N][N]; int d[N][N]; queue<PII> q; void bfs() { int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0}; while(q.size()) { auto t=q.front(); q.pop(); for(int i=0;i<4;i++) { int x=t.first+dx[i],y=t.second+dy[i]; if(d[x][y]==-1&&x<=n&&x>=1&&y<=m&&y>=1&&g[x][y]=='.') { q.push({x,y}); g[x][y]='g'; d[x][y]=d[t.first][t.second]+1; if(d[x][y]==k) return ; } } } } int main() { scanf("%d%d",&n,&m); memset(d,-1,sizeof d); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>g[i][j]; if(g[i][j]=='g') { q.push({i,j}); d[i][j]=0; } } scanf("%d",&k); bfs(); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cout<<g[i][j]; } cout<<endl; } return 0; }
-
题解
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> PII; int const N=1100; int n,m,k,cnt; char g[N][N]; int d[N][N]; queue<PII> q; int len; void bfs() { int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0}; while(q.size()&&k>0) { auto t=q.front(); q.pop(); for(int i=0;i<4;i++) { int x=t.first+dx[i],y=t.second+dy[i]; if(d[x][y]==-1&&x<=n&&x>=1&&y<=m&&y>=1&&g[x][y]=='.') { q.push({x,y}); g[x][y]='g'; } } len--; //一个点向四周扩展完之后,len--,表示这层的一个点已经完成扩展 //这里是重点!!! if(len==0) //len ==0 说明这层的点已经全部完成扩展,令 len 重新等于刚扩展过程中放进去点的个数(即q.size(),我们之前的点都已经pop掉了,所以现在队列里面的点都是新放进去,属于下一层的点),并且层数k-- { k--; len=q.size(); } } } int main() { scanf("%d%d",&n,&m); memset(d,-1,sizeof d); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>g[i][j]; if(g[i][j]=='g') { q.push({i,j}); } } len=q.size(); //最开始计往里面放了几个元素 len=q.size( ) scanf("%d",&k); bfs(); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cout<<g[i][j]; } cout<<endl; } return 0; }
-
反思
第一次的扩展层数不正确,代码没有实现成功;
题解中的记录扩展层数的方式:
- 最开始计往里面放了几个元素 len=q.size( )
- 一个点向四周扩展完之后,len–,表示这层的一个点已经完成扩展
- len ==0 说明这层的点已经全部完成扩展,令 len 重新等于刚扩展过程中放进去点的个数(即q.size(),我们之前的点都已经pop掉了,所以现在队列里面的点都是新放进去,属于下一层的点),并且层数k–
2.分考场
-
题目
n 个人参加某项特殊考试。
为了公平,要求任何两个认识的人不能分在同一个考场。
求最少需要分几个考场才能满足条件。
输入描述
第一行,一个整数 n (1≤n≤100),表示参加考试的人数。
第二行,一个整数 m,表示接下来有 m 行数据。
以下 m 行每行的格式为:两个整数 a*,b,用空格分开 ( 1≤a,b≤*n )表示第 a 个人与第 b 个人认识。
输出描述
输出一行一个整数,表示最少分几个考场。
输入输出样例
示例
输入
5 8 1 2 1 3 1 4 2 3 2 4 2 5 3 4 4 5
输出
4
-
第一次 AC 0%
#include<bits/stdc++.h> using namespace std; const int N=110; int n,m,ans; int p[N],s[N]; int find(int x) { if(x!=p[x]) p[x]=find(p[x]); return p[x]; } void add(int a,int b) { s[b]+=s[a]; ans=max(ans,s[b]); p[b]=find(p[a]); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { p[i]=i; s[i]=1; } while(m--) { int a,b; scanf("%d%d",&a,&b); add(a,b); } cout<<ans; return 0; }
想错了,这题长得真像并查集,a和b认识,b和c认识,但是a和b不一定认识
经过思考,我的思路:
先把n个数放在一个房间里面,a,b 认识,把其中一个从他们房间里面移出去;
移到隔壁房间,隔壁房间有认识的人,往下轮,直到找到没有认识的人房间,如果都不行,就新建一个房间 ans++
怎么实现呢
-
题解
#include<bits/stdc++.h> using namespace std; const int N=110; int n,m; bool g[N][N]; //矩阵数组:两个人认识为1,不认识为 0 vector<int>q[N]; //定义一个二维空间数组 int ans=0x3f3f3f3f; //定义最后需要的房间 bool check(int id,int p) //判断 p 这个考场,能不能放 id 这个人 { for(int j=0;j<q[p].size();j++) //q[p].size() 表示考场的人数,精髓 { if(g[id][q[p][j]]) return false; } return true; } void dfs(int id,int cnt) { if(cnt>=ans) //剪枝:一定不是最小的结果,回溯 return; if(id==n+1) // 所有人 都遍历了,回溯 { ans=min(ans,cnt); return; } for(int p=1;p<=cnt;p++) //遍历每一个考场 { if(check(id,p)) //考场里没有熟人 { q[p].push_back(id); //id放在 p这个考场里面 dfs(id+1,cnt); //放下一个 学生 q[p].pop_back(); //恢复现场 } } if(cnt<n) //经过上面的遍历每一个考场,没有 dfs ,说明没有考场可以放 id,so开一个新的考场 { q[cnt+1].push_back(id); //cnt+1 dfs(id+1,cnt+1); q[cnt+1].pop_back(); //回复现场 } } int main() { cin>>n>>m; while(m--) { int a,b; cin>>a>>b; if(a!=b) g[a][b]=1,g[b][a]=1; } dfs(1,0); //编号为 1,房间数号 0 cout<<ans; return 0; }
-
反思
怎么实现呢?我想了用邻接表,但是没有实现出来
题解中的vector二维数组真是妙
vector 二维数组:
-
vector<int> q[m]
表示可以往 q[1],q[2] 里面放一个数组,q[2][3]
表示 q[2]这个数组的 第 3个元素,根据上面题中理解更透彻而且还可以 使用
q[2].size()
就很方便
审题,避免整个思路方向性出现错误,dfs 会使用成 并查集 ,老生常谈
-