• C++
  • 五一集训--蓝桥杯省赛集训--蓝桥真题

  • @ 2024-5-5 9:09:09

image image image image image image image image image

9 条评论

  • @ 2024-5-5 11:51:39
    //代码
    #include<bits/stdc++.h>
    using namespace std;
    int x[509][509],s[509][509],n,a,b,c,d,cnt; //左下角坐标为(a,b),右下角坐标为(c,d)
    int main(){
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		cin>>a>>b>>c>>d;
    		x[a+1][b+1]++;//从左下角开始++
    		x[a+1][d+1]--;//从右下角开始--
    		x[c+1][b+1]--;//从左上角开始--
    		x[c+1][d+1]++;//从右上角开始++
    	}
    //对整张图执行一遍上述操作,则只会有 a+1 行 b+1 列到 c 行 d 列被++
    	for(int i=1;i<=505;i++)
    		for(int j=1;j<=505;j++){
    			s[i][j]=x[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
    			if(s[i][j]) cnt++;
    		}
    	cout<<cnt;
    	return 0;
    }
    
    • @ 2024-5-5 11:50:59
      //十三届蓝桥杯省赛真题第六题:面积
      //知识点---二维差分
      //思路:对于给定的矩形两个顶点,我们可以暴力枚举区域内的每一个坐标并标记,等所
      //有矩形都标记完了之后再遍历整张地图,记录有多少个被标记的点,即为答案。这个方
      //法的缺点是每个矩形都要枚举,时间复杂度较高,但是这个题的数据规模是可以过的
      //二维差分思路:对于每个矩形只需标记四个顶点,后面再通过一次循环来判断该点是否
      //被覆盖。
      //这题要注意坐标点和长度的区别
      
      #include<bits/stdc++.h>
      using namespace std;
      int s[509][509],n,a,b,c,d,cnt; //左下角坐标为(a,b),右下角坐标为(c,d)
      int main(){
      	cin>>n;
      	for(int i=1;i<=n;i++){
      		cin>>a>>b>>c>>d;
      		for(int j=a+1;j<=c;j++)//染色的区域为 a+1 行,b+1 列到 c 行 d 列
      			for(int k=b+1;k<=d;k++)
      				s[j][k]=1;
      	}
      	for(int i=1;i<=505;i++)
      		for(int j=1;j<=505;j++)
      			if(s[i][j]) cnt++;
      	cout<<cnt;
      	return 0;
      }
      
      
      • @ 2024-5-5 11:43:36
        //十三届蓝桥杯省赛真题第五题:农作物
        //知识点---DFS 连通性
        //思路:DFS 典型应用-数连通区域个数,依次查看地图上每个点,如果可以收割则四方向
        //收割每一个点,同时计数器++,直到地图上没有可以收割的点了为止
        
        
        #include<bits/stdc++.h>
        using namespace std;
        char d[509][509];
        int n,m,cnt;
        int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};//下上右左四方向
        void dfs(int x,int y){
        	d[x][y]='X';//把这个格子收割
        	for(int i=0;i<4;i++){
        		int nx=x+dx[i],ny=y+dy[i];//查看邻居这一格
        		if(d[nx][ny]=='R') dfs(nx,ny);//如果是农作物,则也割掉
        	}
        }
        int main(){
        	cin>>n>>m;
        	for(int i=1;i<=n;i++)
        		for(int j=1;j<=m;j++) cin>>d[i][j];
        	for(int i=1;i<=n;i++)
        		for(int j=1;j<=m;j++) {
        			if(d[i][j]=='R') {//如果遇到农作物,开始收割
        				cnt++;//记录收割的区域数量,而不是收割的格子面积
        				dfs(i,j);
        			}
        		}
        	cout<<cnt;
        	return 0;
        }
        
        • @ 2024-5-5 11:42:04
          //十三届蓝桥杯省赛真题第四题:最大值
          //知识点---二分查找答案
          
          #include<bits/stdc++.h>
          using namespace std;
          int n,w[509],h[509],k;
          bool OK(int x){//对于边长 x,算出可以剪出多少个
          	int sum=0;
          	for(int i=1;i<=n;i++)
          		sum+=(w[i]/x)*(h[i]/x);
          	return sum>=k;//判断剪出的个数有没有超过 k,没超过则拆分失败
          }
          int main(){
          	cin>>n;
          	for(int i=1;i<=n;i++) cin>>w[i]>>h[i];
          	cin>>k;
          	int l=1,r=min(*max_element(w+1,w+1+n),*max_element(h+1,h+1+n));//能剪出来的最大边长为这两个数组中最大值的较小者,再大的边长必然一个都剪不出来
          	
          	int ans=1;//初始答案保守一点
          	while(l<=r){//求最大值的二分
          		int mid=(l+r)/2;//中点
          		if(OK(mid)) ans=mid,l=mid+1;//中点可以,则比中点小的都可以,记录此时中点作为答案,后续猜比中点大的范围
          		else r=mid-1;//中点不可以,则比中点大的都不可以,后续猜比中点小的范围
          	}
          	cout<<ans;
          	return 0;
          }
          
          • @ 2024-5-5 11:41:32
            //十三届蓝桥杯省赛真题第四题:最大值
            //知识点---二分法 2	
            //思路:从最大可能的边长开始,向下找答案,找答案的过程可以二分,可以暴力枚举,
            //判断答案是否可行的方式是对于每个边长,把他能剪出来的纸片数量与 K 比较
            
            #include<bits/stdc++.h>
            using namespace std;
            int n,w[509],h[509],k;
            bool OK(int x){//对于边长 x,算出可以剪出多少个
            	int sum=0;
            	for(int i=1;i<=n;i++)
            		sum+=(w[i]/x)*(h[i]/x);
            	return sum>=k;//判断剪出的个数有没有超过 k,没超过则拆分失败
            }
            int main(){
            	cin>>n;
            	for(int i=1;i<=n;i++) cin>>w[i]>>h[i];
            	cin>>k;
            	int big=min(*max_element(w+1,w+1+n),*max_element(h+1,h+1+n));//能剪出来的最大边长为这两个数组中最大值的较小者,再大的边长必然一个都剪不出来
            	for(int i=big;i>=1;i--)//i 从最大值开始向下枚举,一定是先剪不出来,在临界点之后每个边长都能剪出来,临界点即所求最大值
            		if(OK(i)) {
            			cout<<i;
            			return 0;
            		}
            }
            
            • @ 2024-5-5 11:32:00
              //十三届蓝桥杯省赛真题第三题:组合
              //知识点---数学题+暴力枚举	
              //数学结论:当(a,b)=1 且 n≥ab 时,关于 x,y 的不定方程 ax+by=n 必有非负整数解。
              //则凑不出来的糖果数量一定小于 N*M,枚举所有这样的数,依次判断能不能拆成若干个
              //N 和 M 的和即可,找到最大那个
              
              #include<bits/stdc++.h>
              using namespace std;
              int a,b;
              bool OK(int n){//判断 n 能否由若干个 a 和 b 加出来
              	while(n>=0){//每次拆出 1 个 a,若剩余部分能被 b 整除,则能被若干个 a 和 b 加出来
              		if(n%b==0) return 1;
              		n-=a;
              	}
              	return 0;
              }
              int main(){
              	cin>>a>>b;
              	for(int i=a*b;i>=1;i--)//从范围的上限开始向下枚举
              		if(!OK(i)) {//如果这个 i 拆不出来,则这个 i 就是所求的最大数量
              			cout<<i;
              			return 0;
              		}
              }
              //注:可进一步证明这个数必为 a*b-a-b,这里就不证了,对编程部分没有太大意义
              
              
              
              • @ 2024-5-5 11:13:23
                //十三届蓝桥杯省赛真题第二题:分成整数
                //知识点---暴力法+数位分离	
                //思路:找到所有和为 n 的互不相同的三个数,依次确认这三个数没有 3 和 7,每找到一组,cnt++
                //易错点:枚举是要细化枚举的范围,比如本题n最大值500,三重循环的暴力就会超时,拿不到满分
                #include<bits/stdc++.h>
                using namespace std;
                bool have37(int x){//判断整数 x 是否含有数字 3 或 7
                	while(x) {//对 x 每个数字数位分离
                		if(x%10==3||x%10==7) return 1;//如果个位为 3 或 7,则这个数有 3 或 7
                		x/=10;//删去个位
                	}
                	return 0;//如果循环结束后还没返回 1,说明这个数没有 3 或 7
                }
                int main(){
                	int n,cnt=0;//计数器初始化
                	cin>>n;
                	for(int i=1;i<n/3;i++)//保证枚举出来的三个数递增,则 i 最多取到 n/3-1
                		for(int j=i+1;j<n/2;j++)//保证枚举出来的三个数递增,则 j 至少为 i+1 且最多取到n/2-1
                			if(!have37(i)&&!have37(j)&&!have37(n-i-j)&&n-i-j>j)
                			//如果枚举出来的三个数字都没有 3 或 7,且第三个数字最大
                				cnt++;//计数器++
                	cout<<cnt;
                	return 0;
                }
                
                • @ 2024-5-5 11:04:45
                  //十三届蓝桥杯省赛真题第一题:比较大小
                  //方法二:知识点---max 函数
                  #include<bits/stdc++.h>
                  using namespace std;
                  int main(){
                  	int a,b;
                  	cin>>a>>b;
                  	cout<<max(a,b);
                  	return 0;
                  }
                  
                  • @ 2024-5-5 11:04:04
                    //十三届蓝桥杯省赛真题第一题:比较大小
                    //方法一:知识点---if结构
                    #include<bits/stdc++.h>
                    using namespace std;
                    int main(){
                    	int a,b;
                    	cin>>a>>b;
                    	if(a>b) cout<<a;
                    	else cout<<b;
                    	return 0;
                    }
                    
                    • 1