2021年第十二届蓝桥杯省赛B组C/C++

前言：

​        回味一下去年第一次参加蓝桥杯比赛，当时大一，满怀热情，尽管只学了C语言，c++只接触了一点点，在学长的建议下还是报名参加了比赛。他们都说这暴力杯，混个省奖很简单的。赛场上我直呼好家伙，给的Dev是英文的，单词不认识咋搞？这是人干的事，程序跑了半个多小时还没跑出结果，太暴力了……我也只配体验一下这最贵的牛奶和面包了😭

试题A：空间

• 【问题描述】
  ​​       小蓝准备用256 MB的内存空间开一个数组，数组的每个元素都是32位二进制整数，如果不考虑程序占用的空间和维护内存需要的辅助空间，请问256 MB的空间可以存储多少个32位二进制整数?

• 【答案提交】
  ​       这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

解答

1 B = 8 bit

1 KB = 1024 B

1 MB = 1024 KB

1 GB = 1024 MB

1 TB = 1024 GB

字节，Byte，B，这几个词是等价的，1 Byte=8 bit；

位,比特,bit，b，这几个词是等价的，1个比特(也就是1位)就是一个二进制数

一个32位二进制整数占4个字节。

答案为：

256 * 1024 * 1024 / 4 = 67,108,864

或者 256 * 1024 * 1024 * 8 / 32 = 67,108,864

答案

67108864

试题B：卡片

• 【问题描述】

  ​​       小蓝有很多数字卡片，每张卡片上都是数字0到9。
  ​       小蓝准备用这些卡片来拼一些数，他想从1开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了。
  ​       小蓝想知道自己能从1拼到多少。
  ​​       例如，当小蓝有30张卡片，其中0到9各3张，则小蓝可以拼出1到10，但是拼11时卡片1已经只有一张了，不够拼出11。
  ​​       现在小蓝手里有0到9的卡片各2021张，共20210张，请问小蓝可以从1拼到多少?
  ​        提示:建议使用计算机编程解决问题。

• 【答案提交】
  ​​       这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

解答

暴力就完事了！

#include <bits/stdc++.h>
using namespace std;
int main() {vector<int> array(10, 2021);for (int i = 1; ; i++) {int t = i;while (t) {int a = t % 10;if (array[a] > 0) {array[a]--;} else {break;}t /= 10;}if (t) {cout<<i<<endl;break;}}return 0;
}

此处的运行结果是3182；

注意：此处是刚好3182这个数无法拼成。因此结果要减一。

答案

3181

注意审题！ 注意审题！！ 注意审题！！！ 我就是掉进了这个坑😭

试题C：直线

• 【问题描述】
  ​​       在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上，那么这些点中任意两点确定的直线是同一条。
  ​​       给定平面上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}，即横坐标是О到19(包含О和 19)之间的整数、纵坐标是О到20(包含О和20)之间的整数的点。请问这些点一共确定了多少条不同的直线。
• 【答案提交】
  ​        这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

解答

从样例：2×3个整点{(x, y) | 0 ≤ x < 2, 0 ≤ y < 3, x ∈ Z, y ∈ Z)}，可以确定11条不同的直线。

（点数较少，可以画图求证）

20×21个整点{(x,y)0 ≤ x <20,0 ≤y <21,x ∈ Z,y ∈Z}这里借助编程实现。

思路：

两点确定一条直线，对于多条直线，对截距和斜率去重，就能得到最终的直线数目。

坑！！！😶

斜率和截距的计算结果为小数，由于精度不够可能会对去重产生影响。

Solution

将斜率和截距均用分数进行表示，就可以避免精度带来的影响！

#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) { //计算两个数的最大公约数int t;if (a < b) {t = b;b = a;a = t;}while (b) {t = a % b;a = b;b = t;}return a;
}
int main(){vector<pair<int,int>> array; // 存放20 * 21个点set<pair<pair<int, int>, pair<int, int>>> line; // 存放每一条线的斜率和截距（自带去重效果）for (int i = 0; i < 20; i++) {for (int j = 0; j < 21; j++) {array.push_back(make_pair(i,j));}}int n = array.size();for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {int x1 = array[i].first, y1 = array[i].second;int x2 = array[j].first, y2 = array[j].second;if (x1 == x2 || y1 == y2) { //与坐标轴平行的线单独考虑continue;} else {int t;double k1 = y2 - y1; //斜率的分子double k2 = x2 - x1; //斜率的分母t = gcd(abs(k1), abs(k2));if (k1 * k2 > 0) { //约分化简k1 /= t;k2 /= t;} else{ //若斜率为负，负号存到分子上k1 = -abs(k1 / t);k2 = abs(k2 / t);}double b1 = y1 * x2 - x1 * y2; //截距的分子double b2 = x2 - x1; //截距的分母t = gcd(abs(b1), abs(b2));if (b1 * b2 > 0) { //约分化简b1 /= t;b2 /= t;} else{ //若截距为负，负号存到分子上b1 = -abs(b1 / t);b2 = abs(b2 / t);}pair<int, int>p1 = make_pair(k1, k2);pair<int, int>p2 = make_pair(b1, b2);pair<pair<int, int>, pair<int, int>> p = make_pair(p1, p2); //存入set去重line.insert(p);}}}//结果加上与x轴平行的21条线和与y轴平行的20条线cout<<line.size() + 20 + 21;return 0;
}

答案

40257

试题D：货物摆放

• 【问题描述】

  ​​       小蓝有一个超大的仓库，可以摆放很多货物。
  ​​       现在，小蓝有n箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。
  ​​       小蓝希望所有的货物最终摆成一个大的立方体。即在长、宽、高的方向上分别堆L、W、H的货物，满足n = L x 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进行因数分解。

因此最直接想到的就是这种暴力解法。

#include <bits/stdc++.h>
using namespace std;
int main(){long long n = 2021041820210418;long long ans = 0;for (long long i = 1; i <= n; i++) {if (n % i == 0) {for (long long j = 1; j <= n / i; j++) {if (n / i % j == 0) {ans++;}}}}cout<<ans<<endl;return 0;
}

结果就是数据量太大，算了半天算不出结果！🤣

简单优化一下：

找出一组分解方式，直接根据排列组合算出其余结果，这样可以降低分解因数的维度。

#include <bits/stdc++.h>
using namespace std;
int main(){long long n = 2021041820210418;long long ans = 0;for (long long i = 1; i * i * i <= n; i++) {if (n % i == 0) {for (long long j = i; i * j * j <= n; j++) {if (n / i % j == 0) {long long t = n / i / j;if (i == j && j == t) { //三个数都相同ans++;} else if (i == j || i == t || j == t) { //三个数有两个相同ans += 3;} else { //三个数各不相同ans += 6;}}}}}cout<<ans<<endl;return 0;
}

答案

2430

另外一种思路：

先求出n的所有因数（因数个数比较少，方便枚举），然后再枚举出三个因数之积等于n的情况。

试题E：路径

• 【问题描述】

  ​​       小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。
  ​       小蓝的图由2021个结点组成，依次编号1至2021。
  ​       对于两个不同的结点a, b，如果a和 b的差的绝对值大于21，则两个结点之间没有边相连;如果a和b的差的绝对值小于等于21，则两个点之间有一条长度为a和b的最小公倍数的无向边相连。
  ​       例如:结点1和结点23之间没有边相连;结点3和结点24之间有一条无向边，长度为24;结点15和结点25之间有一条无向边，长度为75。
  ​       请计算，结点1和结点2021之间的最短路径长度是多少。
  ​       提示:建议使用计算机编程解决问题。

• 【答案提交】

  ​       这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

解答

动态规划的思想 + 暴力的解法

#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { //计算两个数的最大公约数int t;if (a < b) {t = b;b = a;a = t;}while (b) {t = a % b;a = b;b = t;}return a;
}
int main(){vector<vector<long long>> array(2022, vector<long long>(2022, INT_MAX));for (long long i = 1; i <= 2021; i++) { //计算有边直接相连的点的距离for (long long j = i + 1; j <= i + 21; j++) {array[i][j] = i * j / gcd(i, j);}}for (long long i = 1; i <= 2021; i++) {for (long long j = i + 1; j <= 2021; j++) {for (long long k = i + 1; k < j; k++) { //计算两点之间的最短距离array[i][j] = fmin(array[i][j], (array[i][k] + array[k][j]));}}}cout<<array[1][2021]<<endl;return 0;
}

答案

10266837

试题F：时间显示

时间限制: 1.0 s内存限制:256.0 MB

• 【问题描述】

  ​​       小蓝要和朋友合作开发一个时间显示的网站。在服务器上，朋友已经获取了当前的时间，用一个整数表示，值为从1970年1月1日00:00:00到当前时刻经过的毫秒数。
  ​​       现在，小蓝要在客户端显示出这个时间。小蓝不用显示出年月日，只需要显示出时分秒即可，毫秒也不用显示，直接舍去即可。
  ​​       给定一个用整数表示的时间，请将这个时间对应的时分秒输出。

• 【输入格式】

  ​​       输入一行包含一个整数，表示时间。

• 【输出格式】

​       输出时分秒表示的当前时间，格式形如HH:MM:SS，其中 HH表示时，值为0到23，MM表示分，值为0到 59，SS表示秒，值为0到59。时、分、秒不足两位时补前导0。

• 【样例输入 1】

  46800999
  

• 【样例输出 1】

  13:00:00
  

• 【样例输入 2】

  1618708103123
  

• 【样例输出 2】

  01:08:23
  

• 【评测用例规模与约定】

  ​ 对于所有评测用例，给定的时间为不超过10¹⁸的正整数。

解答

简单模拟！

#include <bits/stdc++.h>
using namespace std;
int main(){long long time;int hh, mm, ss;cin>>time;time /= 1000; //毫秒转化为秒time %= 86400; //转化为一天内的时间hh = time / 3600;time -= hh * 3600;mm = time / 60;ss = time - mm * 60;printf("%02d:%02d:%02d",hh, mm, ss);return 0;
}

试题G：砝码称重

时间限制: 1.0 s内存限制:256.0 MB

• 【问题描述】

​       你有一架天平和N个砝码，这N个砝码重量依次是W₁ , W₂ , ……，W_N 。

​​       请你计算一共可以称出多少种不同的重量?
​​       注意砝码可以放在天平两边。

• 【输入格式】

  ​       输入的第一行包含一个整数N。
  ​       第二行包含N个整数:W₁ , W₂ , ……，W_N 。

• 【输出格式】

  ​​       输出一个整数代表答案。

• 【样例输入】

  3
  1 4 6
  

• 【样例输出】

  10
  

• 【样例说明】

  能称出的10种重量是:1、2、3、4、5、6、7、9、10、11。

  1 = 1

  2 = 6 - 4 (天平一边放6,另一边放4);

  3 = 4 - 1:

  4 = 4

  5 = 6 - 1

  6 = 6

  7 = 1 + 6

  9 = 4 + 6 - 1

  10 = 4 + 6

  11 = 1 + 4 + 6

• 【评测用例规模与约定】

​       对于50%的评测用例，1 < N ≤ 15。
​       对于所有评测用例，1 ≤ N ≤ 100，N个砝码总重不超过100000。

解答

01背包的思想，动态规划的解法。

思路：

• 由题可知，砝码称出的重量为正整数。
• 对于每一个砝码，我们有三种选择：

• ①不选
• ②取负数（放到砝码盘左边）
• ③取正数（放到砝码盘右边）。

• 这里用dp[i][j] ，i表示从前i个砝码中进行选择，j表示称量的重物重量为j。

• 当dp[i][j]为true时，表示从前i个砝码中进行选择，可以称量出j的重量；

• 当dp[i][j]为false时，表示从前i个砝码中进行选择，不可以称量出j的重量。

• 由于N个砝码总重不超过100000。最终只用遍历dp[i][sum] ，（i∈[1,n], n表示砝码的个数；sum表示n个砝码的总重量），true的个数即为可以称量出来的重量总数。

#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = 200010;
int main() {int n;int sum = 0; //所有砝码总重 vector<int>w(N); //记录每个砝码的重量 vector<vector<bool> > dp(N, vector<bool>(M,false)); //记录砝码重量表示的状态 scanf("%d", &n); //读入砝码数 for (int i = 1; i <= n; i++) {scanf("%d", &w[i]); //读入每个砝码的重量 sum += w[i];}dp[0][0] = true; //初态设定，表示重量为0，状态为true for (int i = 1; i <= n; i++) { //从前i个砝码中选择 for (int j = 0; j <= sum; j++) { //需要表示的重量为j//三个状态，有一个状态为true，则当前状态为true；否则为false//称量打的重量均为正数（需要转化） dp[i][j] = dp[i - 1][j] || dp[i - 1][fabs(j - w[i])] || dp[i - 1][j + w[i]];}}long long ans = 0;for (int i = 1; i <= sum; i++) {if (dp[n][i]) { //从n个砝码中进行选择，判断能否称量出重量i，并计数。 ans++;}}cout<<ans<<endl;return 0;
} 

试题H：杨辉三角形

时间限制: 1.0 s内存限制:256.0 MB

• 【问题描述】

  ​​       下面的图形是著名的杨辉三角形:

  

​       如果我们按从上到下、从左到右的顺序把所有数排成一列,可以得到如下数列:

​       1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,…
​       给定一个正整数N,请你输出数列中第一次出现N是在第几个数?

• 【输入格式】

  ​       输入一个整数N。

• 【输出格式】

  ​​       输出一个整数代表答案。

• 【样例输入】

6

• 【样例输出】

13

• 【评测用例规模与约定】

​       对于20%的评测用例，1 ≤ N ≤ 10;
​​       对于所有评测用例,1 ≤ N ≤ 1000000000。

解答

初读题目时，想着是暴力来做的。But，看到N的范围之后，就知道暴力要凉凉~

暴力思路：

#include<bits/stdc++.h>
using namespace std;
const int N = 8000;
int main() {int n;cin>>n;vector<vector<int> > array(N,vector<int>(N));for (int i = 0; i < N; i++) {array[i][i] = array[i][0] = 1;}for (int i = 2; i < N; i++) {for (int j = 1; j <= i; j++) {array[i][j] = array[i - 1][j] + array[i - 1][j - 1];}}cout<<array[N - 1][N / 2]<<endl;long long ans = 1;for (int i = 0; i < N; i++) {for (int j = 0; j <= i; j++) {if (array[i][j] == n) {cout<<ans<<endl;return 0;}else {ans++;}}}return 0;
} 

问题：

• 开的容量小了，达不到N的数据范围；
• 开的容量大了，又内存超限了；

优化一下：

大概能过半数样例吧。

#include<bits/stdc++.h>
using namespace std;
int main(){long long ans = 1;long long a[200000];long long count = 1;long long n;cin>>n;if (n == 1) {cout<<"1"<<endl;return 0;}for (int i = 1; i < 1000000; i++) { //遍历行数a[0] = a[i] = 1;ans++;for (count = i - 1; count > 0; count--) { //当前行数据，利用了对称性ans++;a[count] = a[count] + a[count-1];if (a[count] == n) { //找到n，直接输出并结束cout<<ans<<endl;return 0;}}ans++;}return 0;
}

问题：

• 数组a用来存储每一行的数据，实现了空间的重复利用，然而却超时了。😣😫

正解：找规律 + 二分

思路：

• 杨辉三角的每一个值与排列组合的值是相对应的。
• 用C(r,k)表示，r为行数，k为当前行的个数。（从0开始编号）

• 杨辉三角形具有对称性
• （C(a, b) == C(a, a-b)），而题目要求找第一次出现，因此一定在左边，右边可以直接删掉！
• 只看其半边，其每一斜行是单调不减的（除最外层斜行外都是单调递增的）
• 每一斜行从上到下递增
• 每一横行从中间到两边依次递减

由N <= 10⁹ ,可知，杨辉三角最多取到16斜行。

#include<bits/stdc++.h>
using namespace std;
int n;
long long C(int a, int b) { //求排列组合数 long long res = 1;for (int i = a, j = 1; j <= b; i--, j++) {res = res * i / j;// 大于n已无意义，防止爆long longif (res > n) {return res;}}return res;
} bool check(int k) {// 二分该斜行,找到大于等于n的第一个数long long l = k * 2;long long r = fmax(l,n); // 右端点一定比左端点大 while (l < r) {long long mid = l + r >> 1;if (C(mid, k) >= n) {r = mid;} else {l = mid + 1;}}if (C(r, k) != n) {return false;}// 找到输出第几个数 cout<<r * (r + 1) / 2 + k + 1<<endl;return true;
} int main(){cin>>n;for (int k = 16; ; k--) { //16个斜行中寻找，一定含解。 if (check(k)) { //寻找结果 break;} }return 0;
}

试题I：双向排序

时间限制: 1.0 s内存限制:256.0 MB

• 【问题描述】

  ​​       给定序列(a₁,a₂,……,a_n) = (1,2,… ,n)，即a_i = i。
  ​​       小蓝将对这个序列进行m次操作，每次可能是将a₁, a₂, … , a_qi降序排列，或者将a_qi, a_qi+1, …, a_n升序排列。
  ​​       请求出操作完成后的序列。

• 【输入格式】

  ​​       输入的第一行包含两个整数n, m，分别表示序列的长度和操作次数。

​       接下来m 行描述对序列的操作，其中第i行包含两个整数p_i, q_i表示操作类型和参数。当p_i = 0时，表示将a₁, a₂, … , a_qi降序排列；当p_i = 1时，表示将a_qi, a_qi+1, …, a_n升序排列；

• 【输出格式】

  ​​       输出一行，包含n个整数，相邻的整数之间使用一个空格分隔，表示操作完成后的序列。

• 【样例输入】

  3 3
  0 3
  1 2
  0 2
  

• 【样例输出】

  3 1 2
  

• 【样例说明】

  ​       原数列为(1,2.3)。

  ​       第1步后为(3,2,1)。

  ​       第2步后为(3,1,2)。
  ​       第3步后为(3,1,2)。与第2步操作后相同，因为前两个数已经是降序了。

• 【评测用例规模与约定】

  ​       对于30%的评测用例，n,m ≤ 1000;

  ​       对于60%的评测用例，n,m ≤ 5000;
  ​       对于所有评测用例，1 ≤ n,m ≤ 100000, 0 ≤ a_i ≤ 1, 1 ≤ b_i ≤ n。

解答

这个首先容易想到的就是使用c++STL中的sort函数

#include<bits/stdc++.h>
using namespace std;
bool cmp1(int a, int b) { //升序 return a < b;
}
bool cmp2(int a, int b) { //降序 return a > b;
}
int main(){vector<int>array;int n, m;int p, q;cin>>n>>m;for (int i = 1; i <= n; i++) {array.push_back(i);}for (int i = 0; i < m; i++) {cin>>p>>q;if (p) {sort(array.begin() + q - 1, array.end(), cmp1);} else {sort(array.begin(), array.begin() + q, cmp2);}}for (int i = 0; i < n; i++) {cout<<array[i]<<" ";}return 0;
}

用这个方法来做几乎可以通过半数样例，用来混分不错。

问题：

• 操作次数过多，数据量过大，超时！！！

正解：

思路：

• 要进行m次操作，每次要么是对前缀进行降序排列，要么是对后缀进行升序排列。
• 当p_i = 0时，表示将a₁, a₂, … , a_qi降序排列；
• 当p_i = 1时，表示将a_qi, a_qi+1, …, a_n升序排列；
• 起初给定的序列默认是升序的，因此最开始的升序操作均为多余操作。
• 对于连续的p_i = 0时，即进行连续的前缀降序排列，只需排序一次即可，a₁, a₂, … , a_qi（qi记录最大值）
• 同理，对于连续的p_i = 1时，即进行连续的后缀_n升序排列，只需排序一次即可，a_qi, a_qi+1, …, a_n（qi记录最小值）
• 经过上述简化之后，操作序列就变成了p_i = 0和p_i = 1的交替操作，第一个操作从p_i = 0开始。

进一步分析：

• 对于第一次有效操作，是将[1,x]进行降序排列，起初数列是升序的，则∀a_i ∈[x+1, n] > ∀b_i ∈[0, x]
• 此时[1,x]部分是降序排序，[x+1, n]部分是升序排序。
• 此后对[y, n]进行升序排序，当y > x时相当于没有操作，当y <= x时，[x + 1, n]其实时没有发生变化的，即[x + 1, n]被固定下来。
• 此后对[1, z]进行降序排序，当z < y时相当于没有操作，当z >= y时，[1, y - 1]其实时没有发生变化的，即[1, y - 1]被固定下来。
• 然后不停地从两边向中间固定元素，最后处理边界。

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
vector<pair<int, int> > act(N); //记录每次操作
vector<int> ans(N);
int main(){int n, m;int count = 0;cin >> n >> m;while (m--) {int p, q;cin >> p >> q;if (!p) {while (count && act[count].first == 0) { //压缩连续的 p = 0的操作q = max(q, act[count--].second);}while (count >= 2 && act[count - 1].second <= q) {//若当前操作比上一次相同操作范围大，那么此次操作前两次操作均被无效化count -= 2;}act[++count] = {0, q};} else if (count) {while (count && act[count].first) { //压缩连续的 p = 1的操作q = min(q, act[count--].second);}while (count >= 2 && act[count - 1].second >= q) {//若当前操作比上一次相同操作范围大，那么此次操作前两次操作均被无效化count -= 2;}act[++count] = {1, q};}}int left = 1;int right = n;int k = n;for (int i = 1; i <= count; i++) { //赋值if (act[i].first == 0) {while (right > act[i].second && left < right + 1) {ans[right--] = k--;}} else {while (left < act[i].second && left < right + 1) {ans[left++] = k--;}}if (left > right) {break;}}if (count % 2) { //边界处理while (left < right + 1) {ans[left++] = k--;}} else {while (left < right + 1) {ans[right--] = k--;}}for (int i = 1; i <= n; i++) {cout<<ans[i]<<" ";}return 0;
}

试题J：括号序列

时间限制: 1.0 s内存限制:256.0 MB

• 【问题描述】

  ​​       给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。
  ​​       例如，对于括号序列（ (()，只需要添加两个括号就能让其合法，有以下几种不同的添加结果: ()()()、() (())、(())()、(()())和（(() ))。

• 【输入格式】

  ​​       输入一行包含一个字符串s，表示给定的括号序列，序列中只有左括号和右括号。

• 【输出格式】

  ​​       输出一个整数表示答案，答案可能很大，请输出答案除以1000000007(即10⁹+7)的余数。

• 【样例输入】

  ((()
  

• 【样例输出】

  5
  

• 【评测用例规模与约定】

  ​       对于40%的评测用例，|s| ≤ 200。

  ​       对于所有评测用例，1 ≤ |s| ≤ 5000。

解答

思路：动态规划

• 合法的括号序列满足两个条件：

• 左括号数一定等于右括号数
• 任意位置左括号的数量一定大于等于右括号的数量

• 题目给定序列需要我们添加左括号和右括号，添加的括号只能在括号序列的间隙之间。

• 加入左括号和右括号是否相互干扰呢？(答案是不干扰的)

• 若左括号和右括号加入的是不同的空隙，那么它们必然是互不影响的。

• 若加入的是相同的间隙：

  • 以 “( )” 的方式加入，则两者形成配对，与题目中尽可能少地添加若干括号违背。
  • 那么只能是右括号在左边，左括号在右边。即") (" 的形式。

• 因此添加左右括号可以分开单独计算。答案为单独添加左括号的方案数乘以单独添加右括号的方案数。
• 单独计算左括号：

• 以每个右括号为界限进行分割：XXX ）XXX ） XXX，XXX为若干左括号。
• 我们只需要考虑在右括号前添加若干左括号，保证序列为合法序列即可。
• 右括号前均为左括号，因此添加左括号的方案数只对应于添加左括号的数量。

• 设计状态dp[i][j] :表示只考虑前i个括号，左括号比右括号多j个的所有方案数。
• 最终只需从dp[n][0]到dp[n][n] 进行枚举，返回第一个合理的方案数即可。（n为初始括号数量，此时满足添加括号数最少）

• 当前括号为左括号时， dp[i][j] = dp[i - 1][j - 1]

• 当前括号为右括号时:

  • 在此之前添加的左括号数的范围为[0, j + 1]
  • 其对应的方案数分别为dp[i - 1][j + 1], dp[i - ][j], dp[i - 1][j - 1], ……dp[i - 1][0]
  • 因此，dp[i][j] = dp[i - 1][j + 1] + dp[i - ][j] + dp[i - 1][j - 1] + …… + dp[i - 1][0]
  • 由于：dp[i][j - 1] = dp[i - 1][j] + dp[i - 1][j - 1] + …… + dp[i - 1][0]
  • 所以： dp[i][j] = dp[i - 1][j + 1] + dp[i][j - 1]

• 单独计算右括号：

  根据对称性，将原括号序列反转，再将所有的左括号变为右括号，右括号变为左括号，最后单独计算左括号即为单独计算右括号的结果。

#include<bits/stdc++.h>
using namespace std;
const int N = 5010;
const int mod = 1e9 + 7;
int n;
char str[N];
long long dp[N][N];long long compute() {memset(dp, 0, sizeof(dp));dp[0][0] = 1;for (int i = 1; i <= n; i++) {if (str[i] == '(') {for (int j = 1; j <= n; j++) {dp[i][j] = dp[i - 1][j - 1];}} else {dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % mod; //边界单独处理for (int j = 1; j <= n; j++) {dp[i][j] = (dp[i - 1][j + 1] + dp[i][j - 1]) % mod;}}}for (int i = 0; i <= n; i++) { //寻找最短合法序列方案数if (dp[n][i]) {return dp[n][i];}}return -1;
}int main(){scanf("%s", str + 1); //下标从1开始读入n = strlen(str + 1); //括号序列长度long long l = compute();reverse(str + 1, str + n + 1); //反转括号序列for (int i = 1; i <= n; i++) { //变换左右括号if (str[i] == '(') {str[i] = ')';} else {str[i] = '(';}}long long r = compute();cout << l * r % mod << endl;return 0;
}

总结：

结果还行吧，省二。蓝桥杯，你是真的变了呀。说白了还是自己太菜😅下次蓝桥杯继续努力，争取进国赛！(╯▔皿▔)╯