第十三届蓝桥杯省赛C++B组 （无讲解，只有参考代码）

第十三届蓝桥杯省赛C++B组

• A 九进制转十进制 (5分)
• B 顺子日期 (5分)
• C 刷题统计 (10分)
• D 修剪灌木 (10分)
• E X 进制减法 (15分)
• F 统计子矩阵 (15分)
• G 积木画 (20分)
• H 扫雷 (20分)
• I 李白打酒加强版 (25分)
• J 砍竹子 (25分)

只写了代码没更题解 扫雷那题没手写哈希时间复杂度很紧，建议手写哈希

A 九进制转十进制 (5分)

1478

B 顺子日期 (5分)

14

C 刷题统计 (10分)

#include
using namespace std;
typedef long long ll;
int main(){
    ll a,b,n;
    cin>>a>>b>>n;
    ll t=n/(a*5+b*2);
    n-=t*(a*5+b*2);
    if(a*5>=n)t=t*7+(ll)ceil(1.*n/a);
    else{
        n-=a*5;
        t=t*7+(ll)ceil(1.*n/b)+5;
    }
    cout<<t;
}

D 修剪灌木 (10分)

#include
using namespace std;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cout<<max(2*(i-1),2*(n-i))<<'\n';
}

E X 进制减法 (15分)

#include
using namespace std;
typedef long long ll;
const int N=1e5+3,p=1000000007;
ll a[N],b[N],c[N];
int n, m, q;
int main(){
    cin >> q >> n;
    for(int i=n;i>=1;i--)cin>>a[i];
    cin >> m;
    for(int i=m;i>=1;i--)cin>>b[i];
    for(int i=1;i<=n;i++)c[i]=max(2ll,max(a[i], b[i])+1);
    ll ans = 0;
    for(int i=1,mul=1;i<=n;i++){
        ans=(ans+mul*(a[i]-b[i])%p+p)%p;
        mul=1ll*mul*c[i]%p;
    }
    cout<<ans<<'\n';
    return 0;
}

F 统计子矩阵 (15分)

#include
using namespace std;
int a[550][550];
long long n,m,k,res;
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=m;j++)cin>>a[i][j],a[i][j]+=a[i-1][j];
    for(int H=1;H<=n;H++)
        for(int D=H;D<=n;D++)
            for(int i=1,j=1,sum=0;i<=m;i++){
                sum+=a[D][i]-a[H-1][i];
                while(sum>k)sum-=a[D][j]-a[H-1][j++];
                res+=i-j+1;
            }
    cout<<res;
}

G 积木画 (20分)

#include 
using namespace std;
const int N=1e7+10,mod=1000000007;
int g[4][4]={
    {1, 1, 1, 1},
    {0, 0, 1, 1},
    {0, 1, 0, 1},
    {1, 0, 0, 0},
};
int f[N][4];
int main(){
    int n;cin>>n;
    f[1][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<4;j++)
            for(int k=0;k<4;k++){
                f[i+1][k]=(f[i+1][k]+f[i][j]*g[j][k])%mod;
            }
    cout<<f[n+1][0];
    return 0;
}

H 扫雷 (20分)

#pragma GCC optimize(2)
#include
#include
using namespace std;
typedef long long ll;
const int N=1e5+10;
struct node{
    int x,y,r,t;
}a[N];
bool st[N];
unordered_map<ll,int> p;
inline ll calc(ll x,ll y){return x*(1000000000+1)+y;}
int cnt,res;
void dfs(int u){
    st[u]=true;
    res+=a[u].t;
    int r=a[u].r;
    for(int x=max(0,a[u].x-r);x<=min(a[u].x+r,1000000000);x++){
        for(int y=max(0,a[u].y-r);y<=min(a[u].y+r,1000000000);y++){
            if((x-a[u].x)*(x-a[u].x)+(y-a[u].y)*(y-a[u].y)<=r*r){
                ll id = calc(x, y);
                if(p.count(id)) {
                    int k = p[id];
                    if(!st[k]) {
                        dfs(k);
                    }
                }
            }
        }
    }
}
int main(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        int xi,yi,r;
        scanf("%d%d%d",&xi,&yi,&r);
        ll id=calc(xi,yi);
        if(p.find(id) == p.end()){
            p[id]=++cnt;
            a[cnt]={xi,yi,r,1};
        }
        else{
            int u=p[id];
            a[u].r=max(a[u].r,r);
            a[u].t++;
        }
    }
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        a[cnt+1]={x,y,z};
        dfs(cnt+1);
    }
    printf("%d",res);
}

I 李白打酒加强版 (25分)

#include
using namespace std;
const int p=1e9+7;
int f[220][110][110];
int main(){
    int n,m;cin>>n>>m;
    f[0][0][2]=1;
    for(int i=1;i<=n+m;i++)
    	for(int j=0;j<=n;j++)
    		for(int k=0;k<=m+1;k++)
        		if(f[i-1][j][k]){
            		if(j<n)f[i][j+1][min(k*2,m+1)]=(f[i-1][j][k]+f[i][j+1][min(k*2,m+1)])%p;
            		if(k&&i-1-j<m)f[i][j][k-1]=(f[i-1][j][k]+f[i][j][k-1])%p;
        		}
    cout<<f[n+m-1][n][1];
}

J 砍竹子 (25分)

#include
using namespace std;
typedef long long ll;
int f[200010][10];
int n,m;
int main(){
    int res=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        vector<int> p;
        ll x;cin>>x;
        while(x>1)p.push_back(x),x=sqrt(x/2+1);
        res+=p.size();
        for(int j=0;j<p.size();j++){
            f[i][j+1]=p[p.size()-j-1];
        }
    }
    for(int i=1;i<=6;i++)
        for(int j=2;j<=n;j++)
            if(f[j][i]&&f[j][i]==f[j-1][i])
                res--;
    cout<<res;
}