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

时间:2022-03-13 01:12:01

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

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

文章目录

1.长草

  • 题目

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

    题目描述

    小明有一块空地,他将这块空地划分为 nm 列的小块,每行和每列的长度都为 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+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 会使用成 并查集 ,老生常谈

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