第12届蓝桥杯省赛C/C++ B组纪实

又是一年蓝桥杯备赛季。时隔太久了，已经记不清那4个小时做题过程了，但答案还保留着。这届的考题应该是蓝桥杯最难的一次省赛题，写一篇文章给自己复个盘，也算方便自己的学弟学妹了。

试题A：空间

计算机编程基础知识

• $1MB=1024KB=1024*1024B=1024*1024*8bit$

所以答案是$256\times1024\times1024\times8\div32=67108864$

A题延伸：蓝桥杯大题的程序能开多大的数组？

打算法竞赛的人都知道，一般大题的内存限制是$256MB$，而一般能开辟的最大内存空间为$8000\times8000$的二维int数组。简单计算我们就可以得知原因：

一个int变量占4字节，$8000\times8000$的数组占用内存空间为：

$$ 4Byte\times8000\times8000\div1024\div1024=244MB $$

刚好满足256MB的内存限制。

试题B：卡片

不得不说他作为一道签到题，难度的确有点大了，以往的第2题用Excel甚至笔算可破，今年这道题应该只能老老实实编程了。

#include<iostream>
using namespace std;
int main()
{
    int a[10]={0};
    int num = 1;
    int num_a = num;
        int Max = 2021;
    while(true){
        num_a = num;
        while(num_a){
            int i = num_a%10;
            ++a[i];
            num_a/=10;
        }
        for(int m = 0;m < 10; ++m){
            if(a[m]>Max){
                cout<<num-1;
                return 0;
            }
        } 
        ++num;
    }
}

答案：3181

试题C：直线

这道题题意很清楚，但主要有两个难点：

• 对于垂直于$x$轴的直线，怎么用直线方程$ax+by+c=0$表示？
• 如何判断两点的连线是否重合？换言之：如何唯一的表征一条直线？

对于难点1：
垂直于$x$轴的直线没法用一般方程$ax+by+c=0$表示，有两种思路：

1. 循环遍历时不考虑竖线，等到最后再把竖线条数（20）条加上。
   这种思路是最简单直接且清晰的。
2. 用两点式方程推导直线一般式方程。

$$ \frac{y-y_1}{y_2-y_1}=\frac{x-x_1}{x_2-x_1} $$

$$ (y_1-y_2)x+(x_2-x_1)y+(y_2-y_1)x_1-(y_2-y_1)x_1=0 $$

解得：

$$ A=y_1-y_2 $$

$$ B=x_2-x_1 $$

$$ C=(y_2-y_1)x_1-(x_2-x_1)y_1 $$

这样就不用考虑斜率是否存在的问题了。

对于难点2：
对于每条线，我们算出A, B, C的公约数，并分别对A, B, C做除，使得他们互质，这样每组互质的{A,B,C}就能表征唯一的直线了，然后再利用set去重即可。

#include<iostream>
#include<set>
#include<cmath>
using namespace std;

struct point{
    int x;
    int y;
}p[421];

struct line{
    int a;
    int b;
    int c;
    bool operator<(const line &p) const{
        if(a==p.a)
            return b==p.b ? c<p.c : b<p.b;
        return a<p.a;
    }
    bool operator==(const line &p) const{
        return (a==p.a && b==p.b && c==p.c);
    }
};

int gcd(int a, int b){
    return b==0 ? a : gcd(b, a%b);
} 

int gcdd(int a, int b, int c){
    return gcd( gcd(a, b), gcd(b, c) );
}



int main(){
    int m = 20;    //20列 
    int n = 21;    //21行
    int pnum = 0;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            p[++pnum]={j,i};
        }
    }

    set<line> se;
    int a = 0;
    int b = 0;
    int c = 0;
    int t = 0;
    for(int i = 1;i<=pnum;i++){
        for(int j = i+1;j<=pnum;j++){
            a = p[i].x-p[j].x;
            b = p[j].y-p[i].y;
            c = p[j].x*p[i].y-p[i].x*p[j].y;
            t = gcdd(fabs(a),fabs(b),fabs(c));
            a/=t;
            b/=t;
            c/=t;
            se.insert({a,b,c});
        }
    }
    cout<<se.size();
    return 0;
}

答案：40257

试题D：货物摆放

在比赛的时候自己考找规律做出来的，好像是质数每+1，方案数多一倍，但现在反而找不到规律了，只能退而求其次的用编程做了。

不要被他16位数吓到，其实他的约数一共也没多少，把所有的约数求出来，然后暴力枚举就好了。

#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
typedef long long LL;
LL n = 2021041820210418;
LL yue[1000] = {0};

int ynum = 0;
int cnt = 0;
int main(){
    for(LL i = 1;i*i<=n;i++){
        if(n%i==0){
            yue[++ynum]=i;
            if(i*i!=n){
                yue[++ynum]=n/i;
            }
        }
    }
    
    for(int i = 1;i<=ynum;i++){
        for(int j = 1;j<=ynum;j++){
            if((n/yue[i])%yue[j]==0){
                ++cnt;
            }
        } 
    }
    cout<<cnt<<endl; 
}

答案：2403

试题E：路径

经典Dijkstra最短路径算法模板题，可惜自己没背过，在考场上用DP做的。
附上两种方法的代码：

法一：Dijkstra最短路径

/* 思路：
  1. 初始化图
    1.1 一开始都置0
    1.2 双重for循环通过lcm赋值。
    
  2. dijkstra算法
    2.1    声明表示从1到当前点的数组dist[], 判断当前结点是否已讨论的flag, flag[]
    2.2 dist[]一开始置0x3f3f3f3f, flag[]一开始置0
    2.3 for:从1~n 
    2.4        for:找到当前结点最近的结点编号t 
    2.5     for:考虑路线经过结点t的情况, 重新计算所有结点的dist[]。
    2.6 输出dist[n]
*/
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const int N = 2050;
int g[N][N];        //图表示
bool flag[N];        //表示当前结点是否讨论的flag 
int dist[N];         //从1到当前结点的距离

int gcd(int a, int b){
    return b ? gcd(b,a%b) : a;
}

int lcm(int a, int b){
    return a*b/gcd(a,b);
}

void init(int n){
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            if(i!=j){
                if(fabs(i-j)<=21){
                    g[i][j]=lcm(i,j);
                    g[j][i]=lcm(i,j);
                }
                else{
                    g[i][j]=0x3f3f3f3f;
                    g[j][i]=0x3f3f3f3f;
                }
            }
            else{
                g[i][i]=0; 
            }
        }
    }
}

int dijkstra(int n){
    dist[1]=0;
    
    for(int i = 1;i<=n;i++){
        int t = -1;
        for(int j = 1;j <= n;j++){
            if(!flag[j]&&(t==-1||dist[j]<dist[t])){
                t = j;
            }
        }
        flag[t]=true;
        
        for(int j = 1;j <=n;j++){
            dist[j]=min(dist[j],dist[t]+g[t][j]);
        }
    }
    return dist[n];
}

int main(){
    memset(g, 0, sizeof g);
    memset(flag, false, sizeof flag);
    memset(dist, 0x3f, sizeof dist);
    
    int n = 2021;
    init(n);
    cout<<dijkstra(n);
}

法二：动态规划做法，复杂度比Dijkstra要低

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std; 
#define ll long long
const int N = 2022;
ll w[N][N];
ll dp[N];
ll gcd(ll a,ll b){
    return b==0?a:gcd(b,a%b);
}

ll lcm(ll a,ll b){
    return a*b/gcd(a,b);
}

int main(){
    memset(w,0x3f,sizeof  w);

    for(int i = 2;i<N;i++){
        for(int j = 1;j<i;j++){
            if(fabs(i-j)<=21){
                w[i][j]=lcm(i,j);
                w[j][i]=w[i][j];
            }
        }
    }
    
    for(int i = 1;i<N;i++){
        w[i][i]=0;
    }
    
    dp[1]=0;
    
    
    for(int i = 2;i<N;i++){
        if(i<22){
            for(int j = 1;j<i;j++){
                dp[i]=min(w[1][i],dp[j]+w[i][j]);
            }
        }    
        else{
            dp[i] = 0x3f3f3f3f;
            for(int j = i-21;j<i;j++){
                dp[i]=min(dp[i],dp[j]+w[i][j]);
            }
        }    
    }
    
    cout<<dp[2021]; 
} 

答案：10266837

试题F：时间显示

【样例输入 1】
46800999
【样例输出 1】
13:00:00
【样例输入 2】
1618708103123
【样例输出 2】
01:08:23
【评测用例规模与约定】
对于所有评测用例，给定的时间为不超过 $10^{18}$ 的正整数。

签到题，注意数据类型用longlong

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long LL;

int main()
{
    LL n;
    cin>>n;
    n/=1000;
    
    int h=n/3600%24;
    n=n%3600;
    int m=n/60%60;
    n=n%60;
    int s=n%60;
    printf("%02d:%02d:%02d",h,m,s);
    return 0;
}

试题G：砝码称重

【评测用例规模与约定】
对于 50% 的评测用例，1 ≤ N ≤ 15。
对于所有评测用例，1 ≤ N ≤ 100，N 个砝码总重不超过 100000。

不会做，用dfs跑出来一个复杂度巨高的算法，不放代码了惨不忍睹

试题H：杨辉三角形

【样例输入】
6
【样例输出】
13
【评测用例规模与约定】
对于 20% 的评测用例，1 ≤ N ≤ 10；
对于所有评测用例，1 ≤ N ≤ 1000000000。

暴力骗分了，用评测系统试了下，竟然骗了40%的分

#include<iostream>
#include<cstring>
using namespace std;
const int N = 8000; 


int main(){
    int dp[N][N];
    memset(dp,0,sizeof dp);
    for(int i = 0;i<N;i++){
        dp[i][0]=1;
        dp[i][i]=1;
    }
    int n;
    cin>>n;
    if(n==1){
        cout<<1;
        return 0;
    } 
    
    int cnt = 0;
    for(int i = 0;i<N;i++){
        for(int j = 0;j<=i;j++){
            ++cnt;
            if(dp[i][j]==1){
                continue;
            }
            else{
                dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
                if(dp[i][j]==n){
                    cout<<cnt;
                    return 0; 
                }
            }
        }
    }
}

试题I：双向排序

【样例输入】
6
【样例输出】
13
【评测用例规模与约定】
对于 20% 的评测用例，1 ≤ N ≤ 10；
对于所有评测用例，1 ≤ N ≤ 1000000000。

快排骗分,这题竟然能过60%的样例！

#include<iostream>
#include<algorithm>
using namespace std;
int n;
int m;
int a[5005];
int act;
int num;

bool cmp1(int a,int b){
    return a<b;
}

bool cmp2(int a,int b){
    return a>b;
}

int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        a[i]=i;
    }
    
    for(int i = 0;i<m;i++){
        cin>>act>>num; 
        if(act==1){
            sort(a+num,a+n+1,cmp1);
        }
        else{
            sort(a+1,a+num+1,cmp2);
        }
    }
    for(int i = 1;i<=n;i++){
        cout<<a[i]<<" ";
    }

        return 0;
} 

试题J：括号序列

【样例输入】
((()
【样例输出】
5
【评测用例规模与约定】
对于 40% 的评测用例，|s| ≤ 200。
对于所有评测用例，1 ≤ |s| ≤ 5000。

不会做！（理直气壮）