- C++
五一集训--蓝桥杯省赛集训--蓝桥真题
- 2024-5-5 9:09:09 @
9 条评论
-
mrhowe SU @ 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