2019年第十届蓝桥杯省赛A组（C/C++组）题目分析+赛后总结+题解答案

试题 A: 平方和

思路：

只需要简单枚举就好。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long qq;
bool f(int x){
    while(x>0){
        int t=x%10;
        if(t==2||t==0||t==1||t==9)return 1;
        x/=10;
    }
    return 0;
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        qq ans=0;
        for(int i=1;i<=n;i++){
            if(f(i)==true) ans+=(qq)i*i;
        }
        printf("ans=%lld\n",ans);
    }
    return 0;
}

结果：

2658417853

试题 B: 数列求值

思路：

类似于斐波那契数列的递推，也可以转成矩阵递推形式，用矩阵快速幂加速。

emmmmmmm… 可以，但没有必要~

至于只要求最后四位数字的问题，相当于求答案对10000取模。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long qq;
int n;
int main(){
    while(scanf("%d",&n)!=EOF){
        int a=1, b=1, c=1;
        for(int i=4;i<=n;i++){
            int temp= (a+b+c)%10000;
            a=b;
            b=c;
            c=temp;
        }
        printf("f(%d)=%d\n",n,c);
    }
    return 0;
}

结果：

4659

试题 C: 最大降雨量

思路：

这个题是留到了最后才做，纯口头分析了一下下，没写代码验证（也没太想好怎么写能比较快）。

（1）首先分成7组，每组7个数，那其中肯定有3个组的降雨量不管多小都对答案没影响，那肯定把最小的3*7=21个数字放到其中。

（2）剩下的四组，肯定每组的前3个数尽量平均，即：将剩下的最小的3*4个数字放进四个组。

（3）剩下的最小的数字肯定为中位数。

如图所示：

结果：

试题 D: 迷宫

思路：

（1）首先01地图中找最短路，肯定选择广度优先级搜索（BFS）。

（2）然后需要路径，只需要在搜索过程中记录下每个节点由什么操作转换（或者记录前一个节点的二维坐标），之后再反向沿着路径找回去就知道了走法。

（3）最后还需要字典序最小，那么我们可以考虑方向数组的4个方向向量的顺序。想到的方法是，从右下角节点 T(n,m) 开始，向左上角S(1,1) 搜索找路径。同时维护好每个坐标点是如何由上一坐标点到达。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long qq;
const int maxn = 105;
const int mov[4][2]= { {1,0}, {0,-1}, {0,1}, {-1,0} };
const int inv_mov[4][2]= { {-1,0}, {0,1}, {0,-1}, {1,0} };
const char S[4]= {'U','R','L','D'};
struct state{
    int x,y,step;
    state(){};
    state(int x_, int y_, int step_){
        step= step_;
        x= x_;
        y= y_;
    }
};
int n, m, op[maxn][maxn], dis[maxn][maxn];
bool mp[maxn][maxn], vis[maxn][maxn];
void input(int nn, int mm){
    n=nn;   m=mm;
    char c[maxn]={0};
    for(int i=1;i<=n;i++){
        scanf("%s",c+1);
        for(int j=1;j<=m;j++){
            mp[i][j]=c[j]-'0';
        }
    }
}
void bfs(){
    memset(op,-1,sizeof(op));
    memset(vis,0,sizeof(vis));
    queue<state> q;
    q.push( state(n,m,0) );
    op[n][m]=-1;
    vis[n][m]=1;
    while(!q.empty()){
        state now= q.front();
        q.pop();
        for(int i=0;i<4;i++){
            state net= now;
            net.x+= mov[i][0];
            net.y+= mov[i][1];
            net.step++;
            if(net.x<=0||net.x>n||net.y<=0||net.y>m||mp[net.x][net.y]==true)continue;
            if(vis[net.x][net.y]==false || (dis[net.x][net.y]==net.step && op[net.x][net.y]>i) ){
                op[net.x][net.y]= i;
            }
            if(vis[net.x][net.y]==false){
                q.push(net);
                vis[net.x][net.y]=1;
            }
        }
    }
    /* for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ printf("%3d ",op[i][j]); } printf("\n"); }*/
}
void output(){
    int x=1, y=1;
    while(op[x][y]!=-1){
        printf("%c",S[op[x][y]]);
        int temp= op[x][y];
        x+= inv_mov[temp][0];
        y+= inv_mov[temp][1];
    }
}
int main(){
    input(30,50);
    bfs();
    output();
    return 0;
}

结果：

DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR

试题 E: RSA 解密

思路：

（1）对 $n$ 因数分解可得到 $p, q$ 的值。

（2）设： $k = (p - 1) * (q - 1)$ 。

因为： $d * e = 1 (m o d k)$ ，所以： $e = \frac{1}{d} (m o d k)$ 。

相当于求 $d$ 关于 $k$ 的逆元。即： $e = d^{ϕ (k) - 1} (m o d k)$

（3）然后根据公式即可得到： $X = C^{e} (m o d n)$

（4）另外需要一些快速乘，快速幂 等优化技巧。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long qq;
qq fast_mul(qq x, qq y, qq p){
    qq ret=0;
    x%=p, y%=p;
    while(y>0){
        if(y&1){
            ret= (ret+x)%p;
        }
        y>>=1;
        x= (x+x)%p;
    }
    return ret;
}
qq fast_pow(qq x, qq k, qq p){
    qq ret=1;
    x%=p;
    while(k>0){
        if(k&1){
            ret= fast_mul(ret, x, p);
        }
        k>>=1;
        x= fast_mul(x, x, p);
    }
    return ret;
}
qq phi(qq n){
    qq ret= n;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            ret= ret/i*(i-1);
            while(n%i==0) n/=i;
        }
    }
    if(n!=1){
        ret= ret/n*(n-1);
    }
    return ret;
}
qq get_p(qq n){
    for(qq i=2;i<=n;i++){
        if(n%i==0){
            return i;
        }
    }
}
int main(){
    qq n = (qq)1001733993063167141;
    qq d = 212353;
    qq C = 20190324;
    qq p,q,e,k;
    printf("n=%lld\n",n);
    p=get_p(n);
    q=n/p;
    printf("p=%lld, q=%lld\n",p,q);
    k=(p-1)*(q-1);
    printf("k=(p-1)*(q-1)=%lld\n",k);
    printf("phi(k)=%lld\n",phi(k));
    e=fast_pow(d,phi(k)-1,k);
    printf("e=d^(phi(k)-1)=%lld (mod k)\n",e);
    printf("d*e=%lld (mod k)\n",fast_mul(d,e,k));
    qq X=fast_pow(C,e,n);
    printf("X=C^e (mod n)= %lld\n",X);
    while(1)getchar();
    return 0;
}

运行截图：

结果：

579706994112328949

试题 F: 完全二叉树的权值

思路：

从根节点 DFS ，搜到每个节点就将它的值加到对应的层上，记录每层的数值和即可。

注意一个坑点，有可能最大权值也为负数。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100052;
typedef long long int qq;
qq a[maxn], s[maxn];
int n;
void dfs(int x, int dep){
    if(x>n) return;
    s[dep]+=a[x];
    dfs(x<<1, dep+1);
    dfs(x<<1+1, dep+1);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    dfs(1,1);
    int ans=1;
    for(int i=2;i<maxn;i++){
        if(s[ans]<s[i])ans=i;
    }
    printf("%d\n",ans);
    return 0;
}

试题 G: 外卖店优先级

思路：

对于每个商店，分别记录其操作，再依次进行判断即可。可以用 vector 存储。

注意对于每个商店，其操作一定要小心，有可能添加到优先缓存之后，虽然接下来优先级下降，但是只有优先级小于等于3之后才会被移出。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100052;
typedef long long int qq;
vector<int>a[maxn];
int n,m,t;
bool f(int x){
    if(a[x].size()==0)return 0;
    bool ret=0;
    int now=2;
    for(int i=1;i<a[x].size();i++){
        now= max(0, now -(a[x][i]-a[x][i-1]-1) );
        if(now<=3) ret=0;
        now+=2;
        if(now>5) ret=1;
    }
    now= max(0, now -(t-a[x][a[x].size()-1]));
    if(now<=3) ret=0;
    return ret;
}
int main(){
    scanf("%d%d%d",&n,&m,&t);
    while(m--){
        int ts,id;
        scanf("%d%d",&ts,&id);
        a[id].push_back(ts);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(f(i)==true)ans++;
    }
    printf("%d\n",ans);
    return 0;
}

试题 H: 修改数组

思路：

本来现场想的是二分+树状数组维护，时间复杂度： $O (n * \log n * \log n)$ 。

（1）设置 $v i s$ 数组， $v i s [i]$ 表示数字 $i$ 是否在之前出现过。

（2）用树状数组维护 $v i s$ 数组的前缀和，记： $s [x] = \sum_{i = 1}^{i < = x} v i s [i]$ 。

（3）对于每个数字，查询其是否出现过，如果未曾出现，则不改变其值，并且标记 $v i s$ 数组。否则进行下面操作。

（4）目标找到最右没填的位置，那么我们发现，对于 $f (x) = x - s [x]$ ，是单调递增的，我们只需要找到最靠左边位置 $x ’$ 满足 $f (x^{'})$ 严格大于 $f(x) $ ，那么x‘就是第一个没有出现的数字。

（5）添加之后要记得在对应位置修改 $v i s$ 数组，维护好树状数组。

当时顺手还写了个暴力，用于解决小范围数据，省得写错了分都没了。

ps：然后队友出来后和我说可以用并查集，果然图论相关还是不熟。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100052;
const int maxm = 1000052;
typedef long long int qq;
int a[maxn], tr[maxm], n;
bool vis[maxn];
int lowbit(int x){
    return x&(-x);
}
void add(int x){
    while(x<maxm){
        tr[x]++;
        x+=lowbit(x);
    }
}
int ask(int x){
    int ret=0;
    while(x>0){
        ret+=tr[x];
        x-=lowbit(x);
    }
    return ret;
}
void input(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
}
void output(){
    for(int i=1;i<=n;i++){
        if(i!=1)printf(" ");
        printf("%d",a[i]);
    }
    printf("\n");
}
void work1(){
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
        while(vis[a[i]]==true) a[i]++;
        vis[a[i]]=true;
    }
}
void work2(){
    memset(vis,0,sizeof(vis));
    memset(tr,0,sizeof(tr));
    int now_max=0;
    for(int i=1;i<=n;i++){
        if(vis[a[i]]==true){
            int x=a[i]-ask(a[i]);
            int l=1, r=now_max+10;
            while(l<=r){
                int mid=(l+r)/2;
                if(mid-ask(mid)>x){
                    r=mid-1;
                }
                else{
                    l=mid+1;
                }
            }
            a[i]= r+1;
        }
        add(a[i]);
        vis[a[i]]=1;
        now_max= max(now_max, a[i]);
    }
}
int main(){
    input();
    if(n<=6000){
        work1();
    }
    else {
        work2();
    }
    output();
    return 0;
}

试题 I: 糖果

思路：

显然的状压dp ，顺便压缩一下空间。

$d p (i, j)$ 表示前 $i$ 个数字组成j状态需要选择的最少糖果集合数。

$d p (i, j ∣ a [i]) = m i n (d p (i - 1, j ∣ a [i]), d p (i - 1, j) + 1)$

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = (1<<20) +52;
const int inf = 9;
int a[505], n, m, k, dp[2][maxn];
int min(int a, int b, int c){
    return min( min(a,b), c );
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    int e=1<<m;
    //输入
    for(int i=1;i<=n;i++){
        a[i]=0;
        for(int j=0;j<k;j++){
            int temp;
            scanf("%d",&temp);
            a[i]= a[i]| 1<<(temp-1);
        }
    }
    //初始化
    for(int i=0;i<maxn;i++){
        dp[0][i]=dp[1][i]=inf;
    }
    dp[0][0]=0;
    //递推dp
    bool pos=1;
    for(int i=1;i<=n;i++,pos=!pos){
        for(int j=0;j<e;j++){
            dp[pos][j]=dp[!pos][j];
        }
        for(int j=0;j<e;j++){
            dp[pos][j|a[i]]= min(dp[pos][j|a[i]], dp[!pos][j|a[i]], dp[!pos][j]+1);
        }
    }
    //输出答案
    if(dp[!pos][e-1]==inf){
        printf("-1\n");
    }
    else  printf("%d\n",dp[!pos][e-1]);
    return 0;
}

试题 J: 组合数问题

思路：

不会，简单递推+维护区域前缀和，可以过前4组数据。

代码：

#include<bits/stdc++.h>
using namespace std;
#define modk(x) (((x)>=k)?((x)-k):(x))
const int maxn = 2005;
int c[maxn][maxn], n, m, k, T;
void init(){
    ///预处理C(i,j)
    c[0][0]=1;
    for(int i=1;i<maxn;i++){
        c[i][0]=1%k;
        for(int j=1;j<=i;j++){
            c[i][j]=modk(c[i-1][j]+c[i-1][j-1]);
        }
    }
    ///处理C(i,j)是否为k 的倍数
    for(int i=0;i<maxn;i++){
        for(int j=0;j<=i;j++){
            if(c[i][j]==0) c[i][j]=1;
            else c[i][j]=0;
        }
    }
    ///将二维数组C处理成区域前缀和
    for(int i=1;i<maxn;i++){
        int s=0;
        for(int j=0;j<maxn;j++){
            s+=c[i][j];
            c[i][j]=c[i-1][j]+s;
        }
    }
}
int main(){
    scanf("%d%d",&T,&k);
    init();
    while(T--){
        scanf("%d%d",&n,&m);
        printf("%d\n",c[n][m]);
    }
    return 0;
}