第13届蓝桥杯省赛C/C++ B组实况记录（赛题见附件）

4月28日更新

成绩出来了！省一低空飞过！
自己从大一开始接触第一行代码，第一节C语言课开始就被算法大佬碾压，蓝桥杯大概是自己唯一能参加的算法竞赛了。连续三届省一，也算圆了自己的信息竞赛梦了。蓝桥杯决赛要等到6月下旬，应该没时间打了。再会了蓝桥杯！

第13届蓝桥杯省赛C/C++ B组实况记录

这是自己最后一场蓝桥杯比赛了，但是这次做的并不好。

A：九进制转十进制

简单的进制转化，直接用计算器算即可。

#include<iostream>
using namespace std;
int main(){
    int a = 9; 
    cout<<2*1+2*a+2*a*a*a;
}

答案：1478

B：顺子日期

这题的争议挺大的，想不到组委会会出这么不严谨的题。争议主要体现在两个方面：

含0的序列，如012，算不算顺子？

倒序序列，如321，算不算顺子？
我是按照“012”是顺子，“321”不是顺子来做的。

#include<iostream>
using namespace std;
bool date(int n){
  int year = n/10000;
  int month = n/100%100;
  int day = n%100;
  if(month==1||month==3||month==5||month==7||month==8||month==10||month==12){
      if(day<32&&day>0){
          return true;
      }
      else{
          return false;
      }
  }
  else if(month==11||month==4||month==6||month==9){
      if(day<31&&day>0){
          return true;
      }
      else{
          return false;
      }
  }
  else if(month==2){
      if(day<29&&day>0){
          return true;
      }
      else{
          return false;
      }
  }
  else{
      
      return false;
  }
}

bool shunzi(int n){
  int a = n;
  int a8 = n%10;
  n/=10;
  int a7 = n%10;
  n/=10;
  int a6 = n%10;
  n/=10;
  int a5 = n%10;
  n/=10;
  int a4 = n%10;
  n/=10;
  int a3 = n%10;
  n/=10;
  int a2 = n%10;
  n/=10;
  int a1 = n%10;
  n/=10;
  
  if(a4+1==a5&&a5+1==a6){
      return true;
  }
  else if(a5+1==a6&&a6+1==a7){
      return true;
  }
  else if(a6+1==a7&&a7+1==a8){
      return true;
  }
  else{
      return false;
  }
} 

int main()
{
  int cnt = 0;
  cout<<"顺子日期:\n"; 
  for(int i = 20220101;i<=20221231;i++){
      if(date(i)){
          if(shunzi(i)){
              ++cnt;
              cout<<i<<endl;
          }
      }
  }
  cout<<cnt;
  return 0;

}

答案：14

C：刷题统计

第三道题就是大题，蓝桥杯真有你的，为了防作弊真是拼了
签到题，注意两点：

数据量是10^18，需要用long long ，不能用int。

要取模相除，不要循环累加，不然一定会超时。

#include<iostream>
#define ll long long 
using namespace  std;

int main(){
  
  ll a;
  ll b;
  ll n;        //总题数 
  cin>>a;
  cin>>b;
  cin>>n;
  ll week = a*5+b*2;        //每周刷的题 
  if(n%week==0){
      cout<<n/week*7;
      return 0;
  }
  ll ws = n/week;    
  ll ans = ws*7;        
  n%=week;                //最后一周刷的题 
  ll lastw = 0; 
  bool finish = 0;
  for(ll i = 1;i<=5;i++){
      lastw+=a;
  
      if(lastw>=n){
          ans+=i;finish = true;break;
      }
  }
  if(!finish){
      for(ll i = 1;i<=2;i++){
          lastw+=b;
          if(lastw>=n){
          ans+=i;finish = true;break;
          }
      }
  }
  cout<<ans;

  return 0;
}

D：刷题统计

手算前几个很很容易发现规律

N=1: 0
N=2: 2 2
N=3: 4 2 4
N=4: 6 4 4 6
N=5: 8 6 4 6 8

.........
当然这个题数据量比较小，直接暴力也是能满分的。

#include<iostream>
using namespace std;
int main(){
  int N=6;
  cin>>N;
  if(N==0){
      cout<<0;
      return 0;
  } 
  else if(N==1){
      cout<<0;
      return 0;
  }
  int mid = 0;
  if(N%2==0){
      mid = N/2;
      for(int i = 1;i<=mid;i++){
          cout<<N*2-i*2<<endl;
      }
      for(int i = mid;i>=1;i--){
          cout<<N*2-i*2<<endl;
      }
  }
  else if(N%2==1){
      mid = N/2;
      for(int i = 1;i<=mid;i++){
          cout<<N*2-i*2<<endl;
      }
      cout<<N*2-mid*2-2<<endl;
      for(int i = mid;i>=1;i--){
          cout<<N*2-i*2<<endl;
      }
      
  }
  return 0;
}

E：X进制算法

考试的时候直接跳过了

F: 统计子矩阵

感觉像是DP，比赛的时候研究了20分钟没找到递推规律，暴力骗分了复杂度好像是$O(n^4)$还是$O(n^6)$？不敢想了

#include<iostream>
#define ll long long
using namespace std;
const int N = 500;
const int M = 500;
ll ans = 0;
int K;

int mt[N+1][M+1];

bool Plus(int x1,int y1,int x2,int y2){
    ll sum = 0;
    for(int i = x2;i<=x1;i++){
        for(int j = y2;j<=y1;j++){
            sum+=mt[i][j];
        }
    }
    if(sum<=K){

        return true;
    }
    else{
        return false;
    }
}

int main(){
    int n,m;
    cin>>n>>m;
    cin>>K;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            cin>>mt[i][j];
        }
    }

    for(int x1 = 1;x1<=n;x1++){
        for(int y1 = 1;y1<=m;y1++){
            for(int x2 = 1;x2<=x1;x2++){
                for(int y2 = 1;y2<=y1;y2++){
                    if(Plus(x1,y1,x2,y2)){
                        ++ans;
                    }
                }
            }
        }
    }
    cout<<ans;
    return 0;
}

G: 积木画

比赛的时候钻牛角尖了，用的dfs，太多边界条件了，调bug调了2个小时。最后的复杂度$6^n$，不知道自己花俩小时图啥。
赛后想了想，可以用DP做：L每加1，都会多出2种原子组合方法。这个思路的复杂度大约是$O(n^2)$，还是拿不到全分，不知道该怎么优化。

附上自己200行的DFS算法

#include<iostream>
#include<cstring>

using namespace std;
#define ll long long 

bool vis[3][21];
int N;
int box[7] = {0,2,2,3,3,3,3};

ll ans = 0; 



bool check(int x,int y,int n){
    if(n==1){
        if(x==1&&(y>0&&y<=N)&&vis[x][y]==0&&vis[x+1][y]==0){
            return true;
        }
        else{
            return false;
        }
    }
    else if(n==2){
        if(x<1||x>2||y<1||y>=N){
            return false;
        }
        else if(vis[x][y]==0&&vis[x][y+1]==0){
            return true;
        }
        else{
            return false;
        }
        
    }
    else if(n==3){
        if(x!=1||y<1||y>=N){
            return false;
        }
        else if(vis[x][y]==0&&vis[x+1][y+1]==0&&vis[x+1][y]==0){
            return true;
        }
        else{
            return false;
        }
        
    }
    else if(n==4){
        if(x!=1||y<1||y>=N){
            return false;
        }
        else if(vis[x][y]==0&&vis[x+1][y+1]==0&&vis[x][y+1]==0){
            return true;
        }
        else{
            return false;
        }
        
    }
    else if(n==5){
        if(x!=1||y<1||y>=N){
            return false;
        }
        else if(vis[x][y]==0&&vis[x][y+1]==0&&vis[x+1][y]==0){
            return true;
        }
        else{
            return false;
        }
        
    }
    else if(n==6){
        if(x!=1||y<=1||y>N){
            return false;
        }
        else if(vis[x][y]==0&&vis[x+1][y-1]==0&&vis[x+1][y]==0){
            return true;
        }
        else{
            return false;
        }
        
    }

    return false;
}


void setTrue(int x,int y,int n){
//    cout<<"在("<<x<<","<<y<<")加上第"<<n<<"个图形"<<endl;
    if(n==1){
        vis[x][y]=true;
        vis[x+1][y]=true;
    }
    else if(n==2){
        vis[x][y]=true;
        vis[x][y+1]=true;
        
    }
    else if(n==3){
        vis[x][y]=true;
        vis[x+1][y]=true;
        vis[x+1][y+1]=true;
    }
    else if(n==4){
        vis[x][y]=true;
        vis[x][y+1]=true;
        vis[x+1][y+1]=true;
    }
    else if(n==5){
        vis[x][y]=true;
        vis[x][y+1]=true;
        vis[x+1][y]=true;
    }
    else if(n==6){
        vis[x][y]=true;
        vis[x+1][y]=true;
        vis[x+1][y-1]=true;
    }
    

}

void setFalse(int x,int y,int n){
//    cout<<"在("<<x<<","<<y<<")减去第"<<n<<"个图形"<<endl;
    if(n==1){
        vis[x][y]=false;
        vis[x+1][y]=false;
    }
    else if(n==2){
        vis[x][y]=false;
        vis[x][y+1]=false;
        
    }
    else if(n==3){
        vis[x][y]=false;
        vis[x+1][y]=false;
        vis[x+1][y+1]=false;
    }
    else if(n==4){
        vis[x][y]=false;
        vis[x][y+1]=false;
        vis[x+1][y+1]=false;
    }
    else if(n==5){
        vis[x][y]=false;
        vis[x][y+1]=false;
        vis[x+1][y]=false;
    }
    else if(n==6){
        vis[x][y]=false;
        vis[x+1][y]=false;
        vis[x+1][y-1]=false;
    }
    

}

            
void dfs(int x,int y,int num){

    if(num==2*N){
        ++ans;

        return ;
    }
    
    //寻找下一个填充点
    int nx=0;
    int ny=0;
    bool yesflag = 0;
    for(int i = x;i<=2&&yesflag==0;i++){
        for(int j = 1;j<=N&&yesflag==0;j++){
            if(vis[i][j]==0){
                nx = i;
                ny = j;
//                cout<<"下一个点："<<nx<<"\t"<<ny<<endl;    
                yesflag=1;
            }
        }
    } 
    if(nx==0||ny==0){
        return ;   
    }        
                    
    
    for(int i = 1;i<=6;i++){
        if(check(nx,ny,i)){
            setTrue(nx,ny,i);
            dfs(nx,ny,num+box[i]);
            setFalse(nx,ny,i);
        }
    }
}

int main(){
    cin>>N;
    memset(vis,0,sizeof vis);
    for(int i = 1;i<=6;i++){
        if(check(1,1,i)){
            setTrue(1,1,i);
            dfs(1,1,box[i]);
            setFalse(1,1,i);
        }
    }
    cout<<ans%1000000007;
    return 0; 
}

H: 扫雷

比赛的时候感觉限制太多就跳过了，赛后发现这个题暴力能拿不少分，看来考试的时候还是太浮躁了。

I:李白打酒加强版

经典的反推DP，但做到这题就剩20分钟了，dfs暴力骗40%的分。

#include<iostream>
#include<string>
using namespace std;
int ap = 0;
string st[100000];
int N,M;

void dfs(int n,int m,string s){
    if(n==N&&m==M-1){
        s+="0";
        st[++ap]=s;
        return;
    }
    
    if(n>N){
        return;
    }
    if(m>M){
        return ;
    }
    dfs(n+1,m,s+"1");
    dfs(n,m+1,s+"0");
}

int main(){
    int n;
    int m;
    int ans = 0;
    cin>>N>>M;
    dfs(0,0,"");
    for(int i = 1;i<=ap;i++){
        bool fail = false;
        int jiu = 2;
        string nstr = st[i];
        for(int j = 0;j<nstr.length();j++){
            if(nstr[j]=='1'){
                jiu*=2;             
            }
            else if(nstr[j]=='0'){
                if(jiu==0){
                    fail = true;
                    break;
                }
                else{
                    jiu-=1;
                }
            }
        }
        if(jiu==0&&fail==false){
            ++ans;
        }
    }
    cout<<ans;
    return 0;
}

J:砍竹子

没时间做了，连样例都没输出。赛后发现这题简单样例很好得。可惜了我算法竞赛的最后一道题，意难平。

第13届蓝桥杯省赛C/C++ B组实况记录（赛题见附件）

第13届蓝桥杯省赛C/C++ B组实况记录（赛题见附件）

4月28日更新