2022年蓝桥杯C++b组省赛题解暨赛后补题

蓝桥杯省赛用的devc++，编译器不太熟悉，赛中的代码基本上没管理好，直接重新写一遍吧。赛中也不知道具体多少分，出结果省一，补下题准备下国赛，本文贴赛后整理的思路和代码。

C：刷题统计
思路：简单模拟。

#include 
using namespace std;
long long a,b,n;
long long get(long long num)
{
    int i;
    if(num<=0) return 0;
    for(i=1;i<=7;i++)
    {
        if(i<=5)//周内
        {
            num-=a;
        }
        else//周末
        {
            num-=b;
        }
        if(num<=0) return i;
    }
    return 7;
}
int main()
{
    scanf("%lld%lld%lld",&a,&b,&n);
    long long yizhou=5*a+2*b;
    long long week;
    long long last;
    long long day;
    if(n>=yizhou)
    {
        week=n/yizhou;
        last=n%yizhou;
        day=week*7+get(last);
    }
    else
    {
        day=get(n);
    }
    printf("%lld\n",day);
}

D：修剪灌木
思路：想几个例子来回手动模拟一下，找出规律每个位置的最大值就是其左边和右边树木个数最大值的两倍，并且注意特判n==1的情况就好了。

#include 
using namespace std;
int a[10010];
int main()
{
    int n;
    scanf("%d",&n);
    if(n==1)
    {
        printf("1\n");
    }
    else
    {
        for(int i=1;i<=n;i++)
        {
            a[i]=max(i-1,n-i)*2;
        }
        for(int i=1;i<=n;i++)
        {
            printf("%d\n",a[i]);
        }
    }
    return 0;
}

E：X进制减法
思路：这个题目题目意思表述的很不清楚，赛中一直读错题意，貌似最后仓促交了个部分分过去。这道题思路就是贪心，由于A肯定大于B，所以要作差最小，只需要每个位的进制数均取最小就行了，已知每个进制位都要大于A和B，所以从中取最大值加上1，就是进制位的大小。

//A>=B

#include 
using namespace std;
const int N=100100;
#define int long long
int a[N],b[N];
const int mod=1000000007;
signed main()
{
    int n;
    scanf("%lld",&n);
    int ma,mb; scanf("%lld",&ma);
    for(int i=ma;i>=1;i--) scanf("%lld",&a[i]);
    scanf("%lld",&mb);
    for(int i=mb;i>=1;i--) scanf("%lld",&b[i]);
    int val=1;
    int ans=0;
    for(int i=1;i<=mb;i++)
    {
        ans=(ans+(a[i]-b[i])*val)%mod;
        val=(val*max(2ll,1+max(a[i],b[i])))%mod;//贪心取进制数
    }
    for(int i=mb+1;i<=ma;i++)
    {
        ans=(ans+a[i]*val)%mod;
        val=(val*max(2ll,a[i]+1))%mod;
    }
    printf("%lld\n",ans%mod);
    return 0;
}

F：统计子矩阵
思路：赛中用二维前缀和，O(n4)复杂度可以拿到10分左右。赛后看了一维前缀和+双指针的思路。对每一列求一维前缀和，然后用双指针控制左右边界，由于每个数均不为负数，所以滑动窗口中的序列是单调递增的，满足双指针算法的条件。如果没有每个数均不为负数的条件，那么需要用线段树或平衡树来优化时间复杂度。

#include 
using namespace std;
const int N=505;
int n,m,K;
int sum[N][N];
int main()
{
    scanf("%d%d%d",&n,&m,&K);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int tmp;
            scanf("%d",&tmp);
            sum[i][j]=sum[i-1][j]+tmp;//列前缀和 
        }
    }
    //全部搞闭区间 
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            for(int l=1,r=1,tot=0;l<=m&&r<=m;r++)
            {
                tot+=sum[j][r]-sum[i-1][r];
                while(tot>K)//超过约束 就搞下来 左指针右移 
                {
                    tot-=sum[j][l]-sum[i-1][l];
                    l++;
                }
                ans+=r-l+1;
            }
        }
    }
    printf("%lld\n",ans);
}

G：积木画
思路：状态压缩dp，讨论当前列是否被占用的四个状态，用二进制数来表示，通过题设条件得出状态转移方程，然后用滚动数组来优化空间复杂度。

#include 
using namespace std;
const int mod=1000000007;
int g[4][4]=
{
    {1,1,1,1},
    {0,0,1,1},
    {0,1,0,1},
    {1,0,0,0}
};
int f[2][4];
int main()
{
    int n;
    scanf("%d",&n);
    f[1][0]=1;
    for(int i=1;i<=n;i++)
    {
        memset(f[i+1&1],0,sizeof(f[0]));
        for(int j=0;j<4;j++)
        {
            for(int k=0;k<4;k++)
            {
                if(g[j][k])
                    f[i+1&1][k]=(f[i+1&1][k]+f[i&1][j])%mod;
            }
        }
    }
    printf("%d\n",f[n+1&1][0]);
    return 0;
}

未完待续~