[数据结构与算法]第12届蓝桥杯B组省赛真题题解与考点总结

前言

第12届蓝桥杯也是我第一次参加的蓝桥杯比赛，当时做的其实挺差的，水平有限也补不了题，时隔一年为了准备第13届蓝桥杯，打算把近几年的蓝桥杯真题给补了，但是找遍全网发现也没有一个相对完整的题解，于是就产生了自己动手写题解的想法。

试题A：空间

考点

计算机常识，计算机常识也是第一次出现在蓝桥杯的填空题当中，这在往年是没有的，往年第一题通常是一道简易的签到题。

答案：67108864

题解

1MB=1024KB 1KB=1024B 1B=8位
所以存放32位元素可以存放 256 * 1024 * 1024 * 8 / 32

试题B：卡片

考点

数位截取，数位截取可以说是基本中的基本了，蓝桥杯也多次考察属于是必须掌握的内容。这里还需要注意的是填空题与平时acm题不一样相当于没有输入的自测，所以需要把数据先处理到程序当中。

答案：3181

题解

先看数据范围，总共的牌才2e4那么暴力做即可，从1开始制作，将每个数字上的每一位提取然后减去一张相应的数字的牌如果小于0说明说制作失败。

#include<bits/stdc++.h>
using namespace std;
int num[10];//存储每张牌的数量
bool make(int x)//尝试制作值为x的牌，制作成功返回1，反之返回0
{
    while(x)
    {
        num[x%10]--;//截取最后一位数字
        if(num[x%10]<0)return 0;
        x/=10;//下取整/10
    }
    return 1;
}
int main()
{
    for(int i=0;i<10;i++)
        num[i]=2021;//初始化
    int res=0;//记录成功制作卡片的值
    for(int i=1;;i++)
    {
        if(make(i))res++;
        else break;
    }
    cout<<res;
}

试题C：直线

考点

暴力枚举、STL、精度问题、几何
第一次参赛的时候没有想出来怎么做，主要是那时候还不怎么会STL，现在看来还是挺简单的，但是有个精度问题卡了很多人。

答案：40257

题解

解法1
两点确定一条直线 当直线斜率存在时，我们记该直线为$y=kx+b$其中$k=(y2?y1)/(x2?x1)，b=y2?k?x2$这里需要注意一下b可能会因为精度问题造成答案错误（出现double除法时常常会出现一些问题），所以将b的形式转换为$b=(y2?(x2?x1)?(y2?y1)?x2)/(x2?x1)（两点式）$然后加上斜率不存在的和等于0的41条直线即可。

#include<bits/stdc++.h>
using namespace std;
set<pair<double,double> > line_set;

int main()
{
    int x1,y1,x2,y2;
    for(x1=0;x1<20;x1++){
        for(y1=0;y1<21;y1++){
            for(x2=0;x2<20;x2++){
                for(y2=0;y2<21;y2++){
                    if(x1!=x2&&y1!=y2){
                        double k=(y2-y1)*1.0/(x2-x1);
                        double b=(y2*(x2-x1)-(y2-y1)*x2)*1.0/(x2-x1);
                        //重点！这么写可以规避掉double炸精度问题
                        line_set.insert({k，b});
                    }
                }
            }
        }
    }
    printf("%d",line_set.size()+20+21);
    return 0;
}
//40257

解法2
我们可以将直线转为更一般的形式$Ax+By+C=0$这样可以避免讨论斜率存在与否，其中$由两点式可知(y?y1)/(y2?y1)=(x?x1)/(x2?x1)化简合并同类项可得（y1?y2）x+(x2?x1)y?y1(x2?x1)+x1(y2?y1)$同样用set来存储这三个系数，注意着三个系数需要同时除以他们的公约数以保证是不同的直线。

#include<iostream>
#include<cmath>
#include<set>
using namespace std;
struct node{//点
    int x,y;
}p[1000];
struct line{//直线
    int a,b,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 cnt;
set<line> se;
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 n=20,m=21;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)//将点存入
            p[++cnt]={i,j};
    for(int i=1;i<=cnt;i++){
        for(int j=i+1;j<=cnt;j++){
            int a=p[i].y-p[j].y;//系数
            int b=p[j].x-p[i].x;
            int c=p[i].y * (p[i].x-p[j].x)- p[i].x *(p[i].y-p[j].y);
            int t=gcdd(fabs(a),fabs(b),fabs(c));
            se.insert({a/t,b/t,c/t});
        }

    }
    cout<<se.size();
    return 0;
}

试题D：货物摆放

考点

约数、循环优化

答案：2430

题解

最暴力的三重循环时间复杂度为O（n³）n的大小为1e16显然会超时，进一步优化可以只枚举两个参数判断n和第三个参数的关系L==n/(W*H)，还是超时。进一步思考$L?W?H=n$那么L、W、H自然是n的约数，那么我们把所有的约数都求出来看看有多少个看看是否能降低问题的规模，由于是填空题可以选择打表出所有的约数，所以求一个数的约数使用暴力的方法O（n^1/2）你会发现只有128个，那么我们再用枚举两个参数的方法很容易就可以得到答案。

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
LL yue[101000],cnt;

int main()
{
    LL n=2021041820210418;
    for(LL i=1;i<=n/i;i++){
        if(n%i==0){
            yue[++cnt]=i;
            if(i*i!=n)
                yue[++cnt]=n/i;
        }
    }
    //sort(yue+1,yue+cnt+1);
    //for(int i=1;i<=cnt;i++)cout<<yue[i]<<" ";
    //cout<<cnt;
    int ans=0;
    for(int i=1;i<=cnt;i++){
        for(int j=1;j<=cnt;j++){
            if(n%(yue[i]*yue[j])==0)
                ans++;
        }
    }
    cout<<ans;
    return 0;
}

试题E：路径

考点

最短路径、最小公倍数、最小公约数
前面两道题都没有做出来，这道压轴居然做出来了，我觉得上面两个难度都比这一个大，不是很懂为什么会放在压轴。

答案：10266837

题解：

最短路的板子题，根据题目要求建好图，任意使用一个最短路算法即可得到答案，就算使用复杂度最大的floyd，大约10s也可以得到答案。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N=2510;
int g[N][N],dist[N],st[N];
int n=2021;
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);
}
int dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;

    for(int i=1;i<=n;i++){
        int t=-1;
        for(int j=1;j<=n;j++){
            if(!st[j] && (t==-1 || dist[j]<dist[t]))
                t=j;
        }
        st[t]=1;
        for(int j=1;j<=n;j++){
                dist[j]=min(dist[j],dist[t]+g[t][j]);
        }
    }
    return dist[n];
}
int main(){
    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;
                }
            }
        }
    cout<<dijkstra();
    //cout<<0x3f3f3f3f;
    return 0;
}

试题F：时间显示

考点

模拟，时间进制转换
时间真是蓝桥杯最爱考的考点了，平年闰年啥的需要掌握

题解

观察一下数据范围，直接进行进制转换即可

#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：砝码称重

考点

DP动态规划、DFS（骗分）
参赛时直接看傻，这道题啥也没写，现在看来dp估计还是想不出来但是骗分还是有机会的。

题解

解法1 DFS（50%）
思路就能称的重量一定是砝码重的一边减去轻的一边，一开始天平为空，每次砝码可以放左边或者放在右边，直接深度优先搜索跑一遍用set统计答案即可。

#include<bits/stdc++.h>
using namespace std;

int n;
int w[102];
int flag[102];
set<int> ans;
int ff=0;
void dfs(int sum1,int sum2){
    if(sum1<sum2)return ;//左边重和右边重情况是一样的
    else{
        if(sum1>sum2){
            ans.insert(sum1-sum2);//答案
        }
    }
    for(int i=1;i<=n;i++){
        if(!flag[i]){
            flag[i]=1;
            dfs(sum1+w[i],sum2);//砝码放左边
            dfs(sum1,sum2+w[i]);//砝码放右边
            flag[i]=0;//标记砝码已经被选中了
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&w[i]);
    }
    dfs(0,0);
    printf("%d",ans.size());
    return 0;
}

解法2
一般来说能够深搜的题且是求方案数的都可以用DP来优化，这题就是最好的例证。（引用y总的图）

#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = 2e5 + 10;
int n,m;//m记录最大重量
int a[N];//记录砝码
bool dp[N][M];//dp[i][j]表示前i个砝码，称出j的集合，值为bool值，能称出j就true
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],m+=a[i];
    dp[0][0]=true;
    for (int i = 1; i <= n;i++)//前i个
        for (int j = 0; j <=m;j++)//称出j
            dp[i][j]=dp[i-1][j]||dp[i-1][j+a[i]]||dp[i-1][abs(j-a[i])];
            //只要有一种情况为真，那么dp[i][j]就真
    int ans=0;
    for(int i=1;i<=m;i++)
        if(dp[n][i])
            ans++;
    cout<<ans;
    return 0;
}

试题H：杨辉三角形

考点

组合数学、找规律、二分

题解

暴力做相信大家都会，用二维数组模拟即可。但是要拿到所有分首先你要知道杨辉三角与组合数学的关系，然后再来找规律，具体用代码来解释吧

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

int n;
/*
    组合数和杨辉三角：第i行第j列的数都是组合数C(i, j) （i，j从0开始）
        C(n, 1) = n --> 对应从左向右看斜着的第二列！ ---> 一定有解
    由于杨辉三角左右对称（C(a, b) == C(a, a-b)），又由于找第一次出现，因此一定在左边，右边可以直接删掉！

            1  ---> C(0, 0)
          1 
        1   2  ---> C(2, 1)
      1   3                             ---> C(2n, n)
    1   4   6  ---> C(4, 2)
  1   5   10
1   6   15  20 ---> C(6, 3)

    n最大1e9，C(34, 17) > 1e9, C(32, 16) < 1e9，因此只要枚举前16个斜行即可！


    性质：
        1. 每一斜行从上到下递增
        2. 每一横行从中间到两边依次递减

    因此我们直接从中间对称轴倒序二分找起即可!

        C(r, k)对应的顺序值为：(r + 1) * r / 2 + k + 1

        二分的左右端点：l：2k，r：max(n, l)
            右端点一定不能比左端点小！
            特例：否则当n=1时，会出问题！

*/
// C(a, b) = a!/b!(a-b)! = a * (a-1) .. b个 / b!
LL C(int a, int b){
    LL res = 1;
    for(int i = a, j = 1; j <= b; i --, j ++){
        res = res * i / j;
        // 大于n已无意义，且防止爆LL
        if(res > n) return res;
    }
    return res;
}

bool check(int k){
    // 二分该斜行,找到大于等于该值的第一个数
    // 左边界2k，右边界为max(l, n)取二者最大即可！
    int l = 2 * k, r = max(n, l);
    while(l < r){
        int mid = l + r >> 1;
        if(C(mid, k) >= n) r = mid;
        else l = mid + 1;
    }
    if(C(r, k) != n) return false;
    // C(r, k)的从0开始的顺序！
    cout << 1ll * (r + 1) * r / 2 + k + 1 << endl;
    return true;
}

int main(){
    cin >> n;
    // 从第16斜行枚举即可！
    for(int k = 16; ; k --)
        if(check(k)) break;
    return 0;
}

作者：ITNXD
链接：https://www.acwing.com/solution/content/47358/
来源：AcWing。

试题I：双向排序

考点

排序（骗分）、思维、线段树、平衡树

题解

解法1
sort模拟骗分，按照题意模拟即可大概能拿50%的分数
解法2
线段树合并
解法3
思维+栈

试题J：括号序列

考点：

DP

题解：

首先先要知道括号序列的一些性质：

(1) 左、右括号的总数量相等

(2) 任意前缀的左括号数量必须大于等于右括号数量

(3) 为了尽可能添加少的括号，所以添加的左、右括号不会出现如同“()”的形式，添加一对对应括号，那么删除掉这一对括号依然是合法序列且长度变短，所以添加的左括号一定是与原序列的一个右括号对应，同理添加的右括号与原序列的左括号对应。

添加括号的最小值： 从前往后遍历，当前前缀中，若左括号的数量小于右括号的数量，则需要添加对应数量的左括号，若遍历结束后左括号数量大于右括号，则需要添加对应数量的右括号。

添加括号的方案：

(1)左括号与右括号添加的位置方案是相互独立的，不会相互影响，即使左、右括号添加在同一个间隙，因为不能存在"()“的形式，此处只能为类似”))(("的一种形式，故总的方案数等于左括号的方案数 × 右括号的方案数。

(2)单独考虑添加左括号，若以右括号为分割点， 将整个序列进行分割，因为分割后的子串中均为左括号， 添加任意数目的左括号方案数均为一种，那么此时，我们仅需考虑添加不同数量的左括号的方案数即可。

(3)右括号同理

动态规划：

f[i][j]的状态表示为：只考虑前 i 部分，左括号比右括号多 j 个的所有方案的集合
状态计算：

(1) 若str[i] == ‘(’，易推算出转移方程为f[i][j] = f[i - 1][j - 1]

(2) 若str[i] == ‘)’，则在只考虑前 i - 1部分时，此时左括号数量最多比右括号多 j + 1个，才可能在第 i 部分通过添加或者不加左括号，达到左括号的数量比右括号多 j 个，故状态转移方程为f[i][j] = f[i - 1][j + 1] + f[i - 1][j] + … + f[i - 1][0]，通过完全背包的思维优化这一段转移方程，使得该部分总复杂度由 O(n^3) 降为O(n^2)，优化的状态转移方程为f[i][j] = f[i - 1][j + 1] + f[i][j - 1] (为了防止越界，f[i][0]需要特判)。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 5010, MOD = 1e9 + 7;

int n;
char str[N];
LL f[N][N];

LL ft()
{
    memset(f, 0, sizeof f);
    f[0][0] = 1;
    for (int i = 1; i <= n; i ++ )
        if (str[i] == '(')
        {
            for (int j =1; j <= n; j ++ )
                f[i][j] = f[i - 1][j -1];
        }
        else
        {
            f[i][0] = (f[i - 1][0] + f[i - 1][1]) % MOD;
            for (int j = 1; j <= n; j ++ )
                f[i][j] = (f[i - 1][j + 1] + f[i][j - 1]) % MOD;
        }

    for (int i = 0; i <= n; i ++ )
        if (f[n][i])
            return f[n][i];
    return - 1;
}

int main()
{
    scanf("%s", str + 1);
    n = strlen(str + 1);
    LL l = ft();//预处理出添加左括号的情况
    reverse(str + 1, str + n + 1);//添加右括号是镜像的，我们可以逆置然后改变括号方向
    for (int i = 1; i <= n; i ++ )  
        if (str[i] == '(') str[i] = ')';
        else str[i] = '(';
    LL r = ft();
    printf("%lld\n", l * r % MOD);
    return 0;
} 

总结

总的来说这场题目质量我觉得还是蛮高的，考点考的也很全面，思维方面居多，算法主考DP，只考了一道复杂的数据结构但是也可以优化，填空压轴图论考了最短路径的模板题应该添加的其余信息只是增加了码量。我当时的做题情况应该是拿了50分左右就得到了省一的成绩，正常把签到写出来（填空1.2、大题1，其余模拟骗分）就可以省三了。