2021 第十二届蓝桥杯大赛软件赛省赛，C/C++ 大学B组题解

序

比赛时长： 四个小时
比赛规则：
蓝桥杯比赛跟天梯赛、ACM还不太一样，比赛中提交的答案并没有反馈机制，也就是说你提交了答案以后，自己并不知道是对是错，就像考试一样，只有交了卷，成绩下来以后才能知道自己的奖项。

满分150
T1-T5答案提交共45分，分值分别是5，5，10，10，15
T6-T10为程序提交共105分，分值分别是15，20，20，25，25

T6-T10开放补题
提交链接：https://lx.lanqiao.cn/problemset.page
搜索【第十二届】【省赛】【B组】

一般来说，蓝桥杯=暴力杯
前六题都做对共60分，后面四题嫖一半45分，105以上感觉一般能合格。
T1，T2很裸的暴力
T3，T4需要set优化或者思考一下枚举方案的暴力
T5，T6很裸的暴力，但是要能写一点点基本的代码，题目细节看仔细
T7，T8背包dp与找规律递推。很裸的暴力可以打一半。
T9，T10一般是思维题或dp。稍微思考一下的很裸的暴力可以打一半。

T1-T5

T1 空间

• 小蓝准备用256MB 的内存空间开一个数组，数组的每个元素都是32 位

二进制整数，如果不考虑程序占用的空间和维护内存需要的辅助空间，请问
256MB 的空间可以存储多少个32 位二进制整数？

• 已知1MB=1024KB，1KB=1024B，1B=8b
• 所以答案 67108864

T2 卡片

• 小蓝有很多数字卡片，每张卡片上都是数字 0 到 9。 小蓝准备用这些卡片来拼一些数，他想从 1 开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了。 小蓝想知道自己能从 1 拼到多少。

例如，当小蓝有 30 张卡片，其中 0 到 9 各 3张，则小蓝可以拼出 1 到 10， 但是拼 11 时卡片 1 已经只有一张了，不够拼出 11。
现在小蓝手里有 0 到 9 的卡片各2021 张，共 20210 张，请问小蓝可以从 1 拼到多少？ 提示：建议使用计算机编程解决问题。

• 创个数组表示卡片张数，枚举一下就行
• 3181

T3 直线

• 在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上，那么这些点中任意两点确定的直线是同一条。

给定平面上 2 × 3 个整点> {(x, y)|0 ≤ x < 2, 0 ≤ y < 3, x ∈ Z, y ∈ Z}，即横坐标是 0 到 1 (包含 0 和 1) 之间的整数、纵坐标是 0 到 2 (包含 0 和 2) 之间的整数的点。这些点一共确定了 11 条不同的直线。
给定平面上 20 × 21个整点 {(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z}，即横坐标是 0 到 19 (包含 0 和> 19) 之间的整数、纵坐标是 0 到 20 (包含 0 和 20) 之间的整数的点。请问这些点一共确定了多少条不同的直线。

• 四层for循环枚举(x1,y1)(x2,y2)，根据y=kx+b和k=(y1-y2)/(x1-x2)分别得出k和b的值，注意斜率不存在的情况。依次遍历每个点，用set储存k、b的值用于查重，如果k、b不在map中，则结果加一。注意所有变量都要设为double值，不然计算就会出错。
• 47753

T4 货物摆放

• 小蓝有一个超大的仓库，可以摆放很多货物。 现在，小蓝有 n 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。

小蓝希望所有的货物最终摆成一个大的立方体。即在长、宽、高的方向上 分别堆 L、W、H 的货物，满足 n = L × W × H。给定n，请问有多少种堆放货物的方案满足要求。 例如，当 n = 4 时，有以下 6 种方案：1×1×4、1×2×2、1×4×1、2×1×2、 2× 2 × 1、4 × 1 × 1。
请问，当 n = 2021041820210418 （注意有 16 位数字）时，总共有多少种方案？

• 求n=三个数相乘有多少种方案，16位不超过ll，可以暴力。

考虑优化，长宽高和面积显然是n的因数。对于该性质，那么枚举长宽高的时候只需要枚举n的因数即可（虽然枚举n的所有因数也会超时），但是可以set一下，n/a也是n的因数，那么复杂度就降低了。
再遍历这个集合（作为一条边a），可以用n/a计算出另外两条边相乘的面积S，另外两条边显然也在初始集合之内，且是S的因数，所以再枚举S的因数（即第二条边），就可以计算出第三条边，统计答案，就不会超时了。

• 2430

  #include<bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  int main(){
      LL n = 2021041820210418;
      set<LL>se;
      for(LL a = 1; a <= n; a++){//枚举n的因数
          if(n%a==0){
              if(se.find(a)!=se.end())break; //存在重复值就结束
              se.insert(a);  se.insert(n/a); //n/a优化
          }
      }
      LL res = 0;
      for(LL a : se){//枚举所有可行的第一条边
          LL s = n/a;
          set<LL>se2;
          for(LL b = 1; b <= s; b++){//枚举S的因数(枚举第二条边)
              if(s%b==0){
                  //可以计算出第三条边h=s/b
                  if(se2.find(b)!=se2.end())break;
                  se2.insert(b);  se2.insert(s/b);
                  if(b==s/b)res++;    //b和h相同
                  else res+=2;        //212,221是不同方案
              }
          }
      }
      cout<<res<<"\n";
      return 0;
  }

T5 路径

• 小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图 中的最短路径。

小蓝的图由 2021 个结点组成，依次编号 1 至2021。 对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；如果 a 和 b的差的绝对值小于等于 21，则两个点之间有一条长度为 a 和 b 的最小公倍数的无向边相连。
例如：结点 1 和结点 23之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。
请计算，结点 1 和结点 2021 之间的最短路径长度是多少。 提示：建议使用计算机编程解决问题。

• 暴力建图跑Dijkstra即可，板子题毫无思维含量，仔细点别写错了就行

• 10266837

  #include<bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  int gcd(int a, int b){
      return !b ? a: gcd(b,a%b);
  }
  const int maxn = 2050;
  int e[maxn][maxn];
  int dist[maxn], vis[maxn];
  int main(){
      //建图
      memset(e,0x3f,sizeof(e));
      for(int i = 1; i <= 2021; i++)e[i][i]= 0;
      int n = 2021;
      for(int i = 1; i <= 2021; i++){
          for(int j = 1; j <= 2021; j++){
              if(abs(i-j)<=21){
                  e[i][j] = e[j][i] = i/gcd(i,j)*j;
              }
          }
      }
      //Dijkstra
      memset(dist,0x3f,sizeof(dist));
      dist[1] = 0;
      for(int i = 1; i <= n; i++){
          int v=-1, t = e[0][0];
          for(int j = 1; j <= n; j++){
              if(!vis[j] && dist[j]<t){
                  t = dist[j];
                  v = j;
              }
          }
          if(v==-1)break;
          vis[v] = 1;
          //dist[v] = t;
          for(int j = 1; j <= n; j++){
              if(dist[j]>dist[v]+e[v][j]){
                  dist[j] = dist[v]+e[v][j];
              }
          }
      }
      //cout<<e[0][0]<<"\n";
      cout<<dist[2021];
      return 0;
  }
  
  

T6-T10

T6 时间显示

• 小蓝要和朋友合作开发一个时间显示的网站。在服务器上，朋友已经获取了当前的时间，用一个整数表示，值为从 1970 年 1 月 1 日00:00:00 到当前时刻经过的毫秒数。

现在，小蓝要在客户端显示出这个时间。小蓝不用显示出年月日，只需要显示出时分秒即可，毫秒也不用显示，直接舍去即可。
给定一个用整数表示的时间，请将这个时间对应的时分秒输出。

• 不用显示年月日，只要时分秒，所以不难想到很傻比的做法是对获得的时间戳每次减去60累加即可，注意开longlong，非常简单。（暴力也能过哦）

然后优化一下很显然的做法是，直接取模。
需要注意题目给的是毫秒，不是秒！！！。

```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
    LL ms;  cin>>ms;
    LL h= 0, m=0, s=ms/1000;
    while(s >= 60){
        s -= 60;
        m++;
        if(m==60){
            m = 0;
            h++;
            if(h==24)h = 0;
        }
    }
    printf("%02d:%02d:%02d",h,m,s);
    return 0;
}


#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
    LL ms;  cin>>ms;
    LL s = ms/1000;
    LL h = (s/3600)%24;
    LL m = (s/60)%60;
    s %= 60;
    printf("%02d:%02d:%02d",h,m,s);
    return 0;
}



```

T7 砝码称重

• 你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1, W2, · · · , WN。 请你计算一共可以称出多少种不同的重量？注意砝码可以放在天平两边。
• 放左边为正数，放右边为负数，不放为0，每种砝码三种选择。本质为有限制选择的背包问题。

记fi表示，只从前i个物品中选，总重量为j的所有方案的是否存在。
转移的时候，对于第i个物品，可以放左边+w[i]，放右边-w[i]，以及不放。
最后答案就是遍历总重量m，累加fn即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2e5+10,maxx=1e5;
int w[maxn];
int f[110][maxn];
int main(){
    int n, m=0;  cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>w[i];  m+=w[i];
    }
    f[0][0+maxx] = 1; //前0个物品中选，重量为0的方案数
    for(int i = 1; i <= n; i++){
        for(int j = -m; j <= m; j++){
            f[i][j+maxx] = f[i-1][j+maxx];//不放
            if(j-w[i]>=-m)f[i][j+maxx] |= f[i-1][j-w[i]+maxx];//放左边
            if(j+w[i]<=m)f[i][j+maxx] |= f[i-1][j+w[i]+maxx];//放右边
        }
    }
    int res = 0;
    for(int i = 1; i <= m; i++){
        if(f[n][i+maxx])res++;
    }
    cout<<res<<"\n";
    return 0;
}

T8 杨辉三角形

• 如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列： 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, …

给定一个正整数 N，请你输出数列中第一次出现 N 是在第几个数？

• 滚动数组暴力出杨辉三角，特判第几个数出现，对于前面的部分可以打表.

  //TLE-30分
  #include<bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  const int maxn = 1010;
  LL f[maxn][maxn];
  int main(){
      LL n;  cin>>n;
      f[1][1] = 1;
      f[2][1] = f[2][2] = 1;
      LL cnt = 3;
      for(int i = 3; ; i++){
          for(int j = 1; j <= i; j++){
              f[i][j] = f[i-1][j-1]+f[i-1][j];
              cnt++;
              if(f[i][j]==n){
                  cout<<cnt<<"\n";
                  return 0;
              }
          }
      }
      return 0;
  }
  
  //TLE-40分
  #include<bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  const int maxn = 1e7+10;
  LL f[2][maxn];
  int main(){
      LL n;  cin>>n;
      f[1][1] = 1;
      f[0][1] = f[0][2] = 1;//2%2==0
      LL cnt = 3;
      for(int i = 3; ; i++){
          for(int j = 1; j <= i; j++){
              f[(i+2)%2][j] = f[(i-1+2)%2][j-1]+f[(i-1+2)%2][j];
              cnt++;
              if(f[i%2][j]==n){
                  cout<<cnt<<"\n";
                  return 0;
              }
          }
      }
      return 0;
  }
  
  
  
  

T9 双向排序

• 给定序列 (a1, a2, · · · , an) = (1, 2, · · · , n)，即 ai = i。

小蓝将对这个序列进行 m次操作，每次可能是将 a1, a2, · · · , aqi 降序排列，或者将 aqi, aqi+1, · · · , an升序排列。
请求出操作完成后的序列

• 来个简单粗暴的写法，就是对于每个输入均以sort处理，垃圾数据表示可以给你60分hhh。

  //TLE-60分
  #include<bits/stdc++.h>
  using namespace std;
  typedef long long LL;
  const int maxn = 1e5+10;
  int a[maxn];
  bool cmp(int x, int y){
      return x>y;
  }
  int main(){
      int n, m;  cin>>n>>m;
      for(int i = 1; i <= n; i++)a[i] = i;
      for(int i = 1; i <= m; i++){
          int p, q;  cin>>p>>q;
          if(p==0)sort(a+1,a+q+1,cmp);
          else sort(a+q,a+n+1);
      }
      for(int i = 1; i <= n; i++){
          cout<<a[i]<<" ";
      }
      return 0;
  }
  
  

• 一共两个操作（1-n）的排列，将某前缀降序排列，将某后缀升序。共m个操作。

（1）我们本来输入的序列就是升序的，第一个有效操作必然是降序操作
（2）对于连续的降序或升序操作，我们保留最长的一个操作即可。有效操作必然是左右交替的
（3）当左侧区间长度大于上一个对左端操作时，含重复操作的区间了，我们只需要操作后一个（长度范围更大的）左区间操作即可。

//RE-60分
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
int a[maxn];
int main(){
    int n, m;  cin>>n>>m;
    //化简操作
    stack<pair<int,int> >st;
    for(int i = 1; i <= m; i++){
        int p, q;  cin>>p>>q;
        if(p==0){//左边前缀降序
            //删除前面比当前操作小的左操作
            while(!st.empty() && st.top().first==0){
                q = max(q, st.top().second); st.pop();
            }
            //删掉前边比当前操作小的左端操作及其对应的右端操作
            if(st.size()>=2){
                pair<int,int> t = st.top();  st.pop();
                if(st.top().second>q)st.push(t);
                else{
                    while(st.size()>=1 && st.top().second<=q){
                        st.pop();  t=st.top();
                        if(st.size()>=1)st.pop();
                    }
                    st.push(t);
                }
                
                
            }
            st.push(make_pair(0,q));
        }
        else if(!st.empty()){   //右边后缀升序(不需要操作第一个右操作)
            while(!st.empty() && st.top().first==1){
                q = min(q,st.top().second); st.pop();
            }
            if(st.size()>=2){
                pair<int,int> t = st.top();  st.pop();
                if(st.top().second<q)st.push(t);
                else{
                    while(st.size()>=1 && st.top().second>=q){
                        st.pop();  t=st.top();
                        if(st.size()>=1)st.pop();
                    }
                    st.push(t);
                }
            }
            st.push(make_pair(1,q));
        }
    }
    //处理操作
    vector<pair<int,int> >vc;
    while(st.size()){vc.push_back(st.top()); st.pop(); }
    reverse(vc.begin(),vc.end());
    int k = n, l = 1, r = n;
    for(int i = 0; i < vc.size(); i++){
        if(vc[i].first==0){
            while(r>vc[i].second && l<=r)a[r--]=k--;
        }else{
            while(l<vc[i].second && l<=r)a[l++]=k--;
        }
        if(l>r)break;
    }
    if(vc.size()%2==1){
        while(l<=r)a[l++]=k--;
    }else{
        while(l<=r)a[r--]=k--;
    }
    for(int i = 1; i <= n; i++){
        cout<<a[i]<<" ";
    }
    return 0;
}

T10 括号序列

• 给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。

两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。
例如，对于括号序列((()，只需要添加两个括号就能让其合法，有以下几 种不同的添加结果：()()()、()(())、(())()、(()()) 和((()))。

• 暴力dfs大约可以打40分，正解是类似于完全背包的dp

一个合法括号序列满足2个条件：左右括号数量相同。任何一个前缀中，左括号数量不小于右括号数。
记fi 表示只考虑前i个括号，左括号比右括号多j个的方案数。
对于转移，遇到左括号时显然有fi = fi - 1。遇到有括号时，可以考虑往这个右括号前面加左括号，可以是0-j+1个（因为左括号比右括号多j个，且当前位置是右括号所以需要+1），所以fi = fi + fi - 1。

//100分
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 5050, mod = 1e9+7;

string s;
int f[maxn][maxn], n;
LL dp(){
    memset(f,0,sizeof(f));
    f[0][0] = 1;
    for(int i = 1; i <= n; i++){
        if(s[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(){
    cin>>s;  s="0"+s;
    n = s.size()-1;
    LL l = dp();//左括号的做法
    reverse(s.begin()+1,s.end());//右括号的做法，将整个序列反转,调用函数即可
    for(int i = 1; i <= n; i++){
        if(s[i]=='(')s[i]=')';
        else s[i]='(';
    }
    LL r = dp();
    //cout<<l<<" "<<r<<"\n";
    cout<<(l*r%mod)<<"\n";
    return 0;
}