蓝桥杯刷题冲刺 | 倒计时17天

作者：指针不指南吗
专栏：蓝桥杯倒计时冲刺

🐾马上就要蓝桥杯了，最后的这几天尤为重要，不可懈怠哦🐾

1.长草

• 题目

• 链接： 长草 - 蓝桥云课 (lanqiao.cn)

  题目描述

  小明有一块空地，他将这块空地划分为 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.分考场

• 题目

  链接： 分考场 - 蓝桥云课 (lanqiao.cn)

  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+1dfs(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 会使用成 并查集 ，老生常谈