2022蓝桥杯暑假练习赛3
全是暴力或模拟
题目：
1、试题 算法提高 栅格打印问题
解题方法：
1、特判掉(n<=1&&m<=1)的特殊情况
2、总共需要输出2n+1行，2m+1列。 根据题意输出时讨论当前行列的奇偶就行了。
#include<bits/stdc++.h>
using namespace std;
int n,m;
int main(){
cin>>n>>m;
if(n<=1&&m<=1) return 0;
for(int i=1;i<=2*n+1;i++){
for(int j=1;j<=2*m+1;j++){
if(i%2==1){
if(j%2==1) printf("+");
else printf("-");
}
else{
if(j%2==0) printf(" ");
else printf("|");
}
}
printf("\n");
}
}
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2、试题 算法训练 暗恋
解题方法：
1、题目要求的是最大纯色正方形，所以可能是由一个全1的正方形构成，也可能是由一个全0的正方形构成。
2、数据小，直接暴力O(
n
3
n^3
n3)就可以水过去。对于每个点都考虑将其作为正方形的左上角的时候，可能构成的最大纯色正方形，不断更新最大边长ans，最后输出面积就行了。
#include<bits/stdc++.h>
using namespace std;
int r,c;
int mp[205][205];
int maxn,ans;
bool check(int x,int y,int le){
int sum=0;
for(int i=x;i<x+le;i++){
for(int j=y;j<y+le;j++){
if(mp[x][y]!=mp[i][j]) return false;
}
}
return true;
}
void solve(){
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
for(int len=ans+1;len<maxn;len++){
if(i+len-1<=r&&j+len-1<=c){
if(check(i,j,len)) ans=len;
}
else break;
}
}
}
cout<<ans*ans<<"\n";
}
int main(){
cin>>r>>c;
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
cin>>mp[i][j];
}
}
maxn=max(r,c);
solve();
}
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3、试题 算法提高 大数加法
解题方法：
C++：直接模拟加法
Python：输入输出
#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int a[1100],b[1100],c[1100];
int j=0,len;
int main()
{
cin>>s1>>s2;
for(int i=s1.length()-1;i>=0;i--)
{
a[j++]=s1[i]-'0';
}
j=0;
for(int i=s2.length()-1;i>=0;i--)
{
b[j++]=s2[i]-'0';
}
int len=max(s1.length(),s2.length());
int i,t=0;
c[0]=(a[0]+b[0])%10;
if(a[0]+b[0]>=10)
{
t=1;
}
for(i=1;i<len;i++)
{
int k;
k=a[i]+b[i]+t;
if(k>=10)
{
t=1;
c[i]=k%10;
}
else
{
t=0;
c[i]=k;
}
}
if(a[len-1]+b[len-1]+t>=10) cout<<"1";
for(int i=len-1;i>=0;i--)
{
cout<<c[i];
}
}
a = int(input())
b = int(input())
print(a + b)
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4、试题 算法训练 黑白无常
解题方法：
最多n=8，直接考虑二进制，用0~((1<<n)-1)表示所有可能的情况，然后暴力判断每种情况就行了。
#include<bits/stdc++.h>
using namespace std;
int n;
int num[10];
int wh[10],bl[10];
int bi[10];
bool check(int x,int co){
int h=0,b=0;
for(int i=0;i<n;i++){
if(i==x) continue;
if(bi[i]==1) b++;
else h++;
}
if(co==1){
if(b==wh[x]&&h==bl[x]) return true;
else return false;
}
else{
if(b==wh[x]&&h==bl[x]) return false;
else return true;
}
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++) num[i]=i;
for(int i=0;i<n;i++) cin>>wh[i]>>bl[i];
for(int i=0;i<(1<<n);i++){
bool f=true;
for(int j=0;j<n;j++) bi[j]=(i>>j)&1;
for(int j=0;j<n;j++){
f=f&&check(j,bi[j]);
}
if(f){
int t=0;
for(int j=0;j<n;j++){
if(bi[j]==1){t=1;printf("%d",j+1);}
}
if(t==0) printf("0\n");
return 0;
}
}
puts("NoSolution.");
}
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4、试题 算法提高 班级排名
解题方法：
题目要求每次统计完一门科目后，就输出一次DaDa的排名。
数据小，我们用map<string,int>来记录每个人的成绩，然后每次统计完一门科目后，取暴力获取当前排名。最后统一输出。
#include<bits/stdc++.h>
using namespace std;
int n,m,k,now;
string s;
map<string,int>mp;
int res[105],num;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>s;
mp[s]=0;
}
cin>>m;
for(int i=1;i<=m;i++){
int cnt=0;
for(int j=1;j<=n;j++){
cin>>k>>s;
mp[s]+=k;
if(s=="DaDa") now=mp[s];
}
map<string,int>::iterator it;
for(it=mp.begin();it!=mp.end();it++){
if(it->second>now) cnt++;
}
res[++num]=cnt+1;
}
for(int i=1;i<=m;i++) printf("%d\n",res[i]);
}
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6、试题 算法提高 棋盘多项式
解题方法：
八皇后的变式。
直接dfs，对于每个新到达的值为1的点，我们只考虑其上边和左边是否已经由车可以影响到该点，不能就标记该点，否则跳过。
每次如果棋盘上已经有当前考虑车的个数now，就做出贡献1，并返回。
#include<bits/stdc++.h>
using namespace std;
int n,cnt,res;
int mp[10][10];
bool vis[10][10];
bool check(int x,int y){
if(mp[x][y]==0) return false;
for(int i=x;i>=1&&mp[i][y]!=0;i--) if(vis[i][y]) return false;
for(int j=y;j>=1&&mp[x][j]!=0;j--) if(vis[x][j]) return false;
return true;
}
void dfs(int x,int y,int now){
if(now==res){
cnt++;
return;
}
if(y==n+1){x++,y=1;}
if(x==n+1)return;
dfs(x,y+1,now);
if(check(x,y)){
vis[x][y]=1;
dfs(x,y+1,now+1);
vis[x][y]=0;
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>mp[i][j];
}
}
while(++res){
cnt=0;
memset(vis,0,sizeof(vis));
dfs(1,1,0);
if(cnt==0) break;
cout<<cnt<<"\n";
}
}