2020年蓝桥杯第十一届CC++大学B组（第二次）真题及代码

1A：门牌制作（填空5分_拆分数字）

2B：既约分数（填空5分_gcd）

3C：蛇形填数（填空10分_找规律）

4D：跑步锻炼（填空10分_模拟）

5E：七段码（填空15分_图论+并查集+dfs）

6F：成绩统计（编程题15分）

解析代码（格式化输出）

7G：回文日期（编程题20分）

解析代码（模拟）

8H：子串分值和（编程题20分）

解析代码1（暴力_过50%）

解析代码2（小优化_过60%）

解析代码3（乘法原理_过100%）

9I：平面切分（编程题25分）

解析代码（数学）

10J：字串排序（编程题25分）

解析代码（dp）

1A：门牌制作（填空5分_拆分数字）

题目解析：

简单模拟，答案624

#include<iostream>
using namespace std;
int main()
{int sum = 0;for (int i = 1; i <= 2020; ++i){int tmp = i;while (tmp){if (tmp % 10 == 2){sum++;}tmp /= 10;}}cout << sum << endl; // 答案624return 0;
}

2B：既约分数（填空5分_gcd）

题目分析：

其实就是求分子，分母 [ 1,2020 ] 中的最大公约数为一的个数
可以考虑使用STL的__gcd()函数

答案2481215

#include<iostream>
using namespace std;
int gcd(int a, int b)
{return b ? gcd(b, a % b) : a;
}
int main()
{int res = 0;for (int i = 1;i <= 2020;i++){for (int j = 1;j <= 2020;j++){//if (__gcd(i, j) == 1)//	res++;if (gcd(i, j) == 1)res++;}}cout << res << endl; // 答案2481215return 0;
}

3C：蛇形填数（填空10分_找规律）

题目解析：

这道题目可以观察，可以写代码。
观察发现每次对角线值的差是4的倍数，可以通过递推的方式计算。

答案761


#include<iostream>
using namespace std;
int a[100][100];
int main()
{int cnt = 1;int x, y;for (int i = 1;i <= 40;i++){if (i % 2 == 1){for (x = i, y = 1;x >= 1 && y <= i; --x, ++y){a[x][y] = cnt++;}}else{for (x = 1, y = i;x <= i && y >= 1; ++x, --y){a[x][y] = cnt++;}}}cout << a[20][20]; // 答案761return 0;
}

4D：跑步锻炼（填空10分_模拟）

题目解析：这个问题简单暴力的解决方法可以直接遍历每一天，算出每一天的日期，并使用一个计数器计数。

答案8879

#include<iostream>
using namespace std;
int	get_month_day[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
int main()
{int year, month, day, week = 6, sum = 0;for (year = 2000;year <= 2020;year++){if ((year % 400 == 0) || (year % 4 == 0 && year % 100 != 0)){get_month_day[2] = 29;}for (month = 1;month <= 12;month++){for (day = 1;day <= get_month_day[month]; ++day){if (day == 1 || week == 1)sum += 2;elsesum += 1;week = (week + 1) % 7;if (year == 2020 && month == 10 && day == 1){cout << sum << endl; // 到时间就退出来， 答案8879return 0;}}}get_month_day[2] = 28;}return 0;
}

5E：七段码（填空15分_图论+并查集+dfs）

题目解析：必须要相邻才能发光，也就是所有开着的灯必须是连通的，才能算是一种合法方案，求合法的方案数。

把每条边相连，建立一个无向图。如果在一个状态之后遍历这个图，用并查集的方式，看是否是一个父节点，如果是一个父节点的话，就是相连的
大佬解法是利用二进制。因为每一个灯仅仅对应着开或者关，正好对应二进制的0和1，用二进制优化，但是我这菜鸡只能理解到这里，还是建图能理解
实在不行，蓝桥杯比赛现场，用数学办法推理也行。暴力出奇迹

答案80

#include<iostream>
using namespace std;
int use[10];
int ans, e[10][10], father[10];
void init() // 连边建图
{// a b c d e f g// 1 2 3 4 5 6 7e[1][2] = e[1][6] = 1;e[2][1] = e[2][7] = e[2][3] = 1;e[3][2] = e[3][4] = e[3][7] = 1;e[4][3] = e[4][5] = 1;e[5][4] = e[5][6] = e[5][7] = 1;e[6][1] = e[6][5] = e[6][7] = 1;
}
int Find(int a) // 简易并查集
{return (a == father[a]) ? a : father[a] = Find(father[a]);}
void dfs(int d)
{if (d > 7)//一个七段管的所有灯的状态已经列举完了{for (int i = 1; i <= 7; ++i){father[i] = i;//初始化}for (int i = 1; i <= 7; ++i){for (int j = 1; j <= 7; ++j){//如果存在这条边 且 开i节点 且 开j节点if (e[i][j] && use[i] && use[j]){int fa = Find(i), fb = Find(j);//寻找i，j对于的祖宗节点if (fa != fb)//如果祖宗节点不同，证明未连通father[fa] = fb;//连通 a b}}}int k = 0;for (int i = 1; i <= 7; ++i){if (use[i] && i == father[i]) // 如果它被用过 且 它等于它的祖宗节点k++;}if (k == 1) // 只有一个父节点，就说明他们是相连的ans++;return;}use[d] = 0; // 不选dfs(d + 1);use[d] = 1; // 选dfs(d + 1);use[d] = 0; // 归位
}
int main()
{init();dfs(1);cout << ans << endl;return 0;
}

6F：成绩统计（编程题15分）

解析代码（格式化输出）

注意要输入%%才表示输出%

#include <iostream>
using namespace std;int main()
{int n = 0;cin >> n;int cnt1 = 0, cnt2 = 0;for (int i = 0; i < n; ++i){int x = 0;cin >> x;if (x >= 60)++cnt1;if (x >= 85)++cnt2;}printf("%.0f%%\n", cnt1 / (n / 100.0));printf("%.0f%%\n", cnt2 / (n / 100.0));return 0;
}

7G：回文日期（编程题20分）

题目解析：

遍历前四位数，然后进行回文构造，然后再判断构造出来的回文串是否满足日期的标准，即判断它是否是合法的日期即可。

输入是一个合法的八位数的日期。

第一个输出是，这个日期之后的第一个合法的回文日期

第二个输出是，这个日期之后的第一个符合ABABBABA的日期

#include<iostream>
#include<cstdio>
using namespace std;int get_month_day[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };bool check(int date) // 判断是否位合法日期
{int year = date / 10000;int month = date % 10000 / 100;int day = date % 100;if (!month || month >= 13 || day == 0)return false;if (month != 2 && day > get_month_day[month])return false;if (month == 2){bool leap = (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);if (day > 28 + leap)return false; // 如果二月的天数>大于原本的二月天数+（可能的闰年+1的天数）}return true;
}bool checkAB(int s) // 判断AB
{bool flag = false;int y = s / 10000; // 得到年份 int m = (s / 100) % 100; // 得到月份(BA)int d = s % 100; // 得到日(BA)int k = y / 100; // AB int n = y % 100; // AB if (k == n && m == d)  // 判断是否为ABABBABA flag = true;return flag;
}int main()
{int date;cin >> date;int flag = 0;for (int i = (date / 10000) + 1; i <= 9999; i++) // 枚举四位数的年份{	// 举例 i=1234int left = i;int right = i; // 构造出来的回文串，构造出来的回文串即：12344321for (int j = 0; j < 4; ++j){right = right * 10 + left % 10; // 1234*10+1234%10left = left / 10; // 得到left的下一位} // 因为是按顺序进行的枚举，所以先符合条件的第一个必然是顺序最小的那一个if (check(right)){++flag; // 保证第一个符合的回文串只有一个输出if (flag == 1)cout << right << endl;if (checkAB(right)){cout << right << endl;return 0;}}}return 0;
}

解析代码（模拟）

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
int get_month_day[13] = { -1 , 31 , 28 , 31 , 30 , 31 , 30 , 31 , 31 , 30 , 31 , 30 , 31 };//每个月的天数
bool checkLeapYear(int y) // 判断闰年
{if (y % 400 == 0 || (y % 4 == 0 && y % 100 != 0))return true;return false;
}
bool checkABABBABAstyle(string s) // 判断是否为ABABBABA型
{if (s[0] == s[2] && s[0] == s[5] && s[0] == s[7] && s[1] == s[3] && s[1] == s[4] && s[1] == s[6])return true;return false;
}
int main()
{string S, ans1, ans2;string s, t, year;int y, m, d, i;cin >> S;year = S.substr(0, 4);for (i = stoi(year); ans1 == "" || ans2 == ""; ++i) // i 初值为输入数据的年{// 找到了ans1和ans2，循环结束，有任何一个没有找到 就要继续循环寻找        s = to_string(i); // s为当前枚举的年t = to_string(i);reverse(t.begin(), t.end()); // 求i的逆s += t; // 构造拼接出 s+s'  年月日if (s <= S) // 构造出的s 小于起始日期，不计，continue; // 考察下一年，下面的语句不执行y = stoi(s.substr(0, 4));m = stoi(s.substr(4, 2)); // 从回文串中获得年月日：y、m、d。d = stoi(s.substr(6, 2));if (checkLeapYear(y)) // 如果是闰年，2月的天数为29，get_month_day[2] = 29;if (m < 1 || m > 12)continue;if (d < 1 || d > get_month_day[m])continue;if (ans1 == "") // s是合法日期的回文串，记录在ans1中ans1 = s;if (checkABABBABAstyle(s) && ans2 == "")ans2 = s; // s还符合ABABBABA型，记录在ans2中。}cout << ans1 << '\n' << ans2 << '\n';return 0;
}

8H：子串分值和（编程题20分）

解析代码1（暴力_过50%）

暴力思路解析：哈希表存储字母出现的次数，查看哈希表中是否有多个字母即可

最外层循环枚举一次走的步长
第二层循环枚举左端点
第三层循环将左端点~~~左端点+步长的这一段距离赋值
查找哈希表中是否存在元素，如果存在即 res++
memset：重新初始化哈希表
cout<<res<<endl;

时间O（N^3）

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
int main()
{string s;cin >> s;int n = s.size();int cnt[27] = { 0 };int res = 0;for (int len = 1; len <= n; ++len)//枚举长度{for (int i = 0; i + len <= n; ++i)//枚举左端点{for (int j = i; j < i + len; ++j)//将该段进行填充{cnt[s[j] - 'a']++;}for (int k = 0; k < 26; k++)//查找{if (cnt[k] != 0)res++;}memset(cnt, 0, sizeof(cnt));//重新赋值为：0}}cout << res << endl;return 0;
}

解析代码2（小优化_过60%）

时间优化成O（N^2）

//}
#include <iostream>
#include <unordered_set>
using namespace std;
int main()
{string s;cin >> s;int ans = 0;for (int l = 0; l < s.size(); l++){unordered_set<char> S;for (int r = l; r < s.size(); r++){S.insert(s[r]);ans += S.size();}}cout << ans << endl;return 0;
}

解析代码3（乘法原理_过100%）

乘法原理，时间O ( N ) ：解题思路：

每个字母只有在第一次出现时才有贡献度，因此可以统计每个字母在第一次出现的情况下，能被多少子串所包含；
用 last[s[i]] 记录字母 s[i] 上一次出现的位置；
那么往左最多能延伸到 last[s[i]] + 1，其到第 i 个字母一共有 i - last[s[i]] 个字母；
同理往右最多能延伸到 n，其到第 i 个字母一共有 n - i + 1 个字母；
二者相乘，就是该字母被不同子串所包含的总次数；

样例解释的排列就是这个思路，5 + 8 + 6 + 4 + 5 = 28

#include <iostream>
using namespace std;
typedef long long LL;
int last[200];
int main()
{string s;cin >> s;int n = s.size();s = ' ' + s;LL ans = 0;for (int i = 1; i <= n; i++){ans += (LL)(i - last[s[i]]) * (n - i + 1);last[s[i]] = i;}cout << ans << endl;return 0;
}

9I：平面切分（编程题25分）

解析代码（数学）

题目解析：在同一个平面内，如果添加的每一条直线互不相交，则每添加一条直线，就会增加一个平面；当添加一条直线时，这条直线与当前平面内已有直线每产生一个不同位置的交点时，这条直线对平面总数量的贡献会额外增多一个。

结合图理解一下：

需要注意的是给的边可能会有重复。

如果用两个set集合，一个存边，一个存点，因为set集合会自动去重，所以不用再一个一个判断是否重边，但是set没有下标，不方便与之前的边进行比较。所以采取边输入边计算的方式，一旦获取一条边的信息后就存储到数组中，再和之前已经加入的边进行匹配，判断不重边后再计算交点个数。

#include <iostream>
#include <set>
using namespace std;
const int N = 1010;
long double L[N][2]; // 存储A，B 
long long ans = 1;
int main()
{int N;cin >> N;for (int i = 0; i < N; ++i){cin >> L[i][0] >> L[i][1];bool flag = false;for (int j = 0 ;j < i; ++j) // 判断是否重边{if ((L[j][0] == L[i][0]) && (L[j][1] == L[i][1])){flag = true;break;}}if (!flag) // 若不重边,再判断交点数{// 记录每一条边加进来后与已有直线相交的不同位置的点 set<pair<long double, long double>> points;for (int k = 0;k < i;k++){if (L[k][0] == L[i][0])continue;long double x = (L[i][1] - L[k][1]) / (L[k][0] - L[i][0]);long double y = L[i][0] * x + L[i][1];points.insert(make_pair(x, y)); // set自动去重 }ans += points.size() + 1;}}cout << ans;return 0;
}

10J：字串排序（编程题25分）

解析代码（dp）

蓝桥云课的思路：

蓝桥杯真题：字串排序_蓝桥杯字串排序-CSDN博客

//#include <bits/stdc++.h> // 字串切分
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int V, len, now, cnt[27], sum[27];
int get_max(int len)
{return ((len - (len / 26 + 1)) * (len / 26 + 1) * (len % 26) + (26 - len % 26) * (len / 26) * (len - len / 26)) / 2;
}
bool check(int x, int n)
{memset(cnt, 0, sizeof(cnt)); // cnt记录后面n个位置放置的对应字符数量int add1 = 0, add2 = 0;for (int j = 26; j >= x + 1; --j){add1 += sum[j]; // 1~pos-1里边比当前插入字符大的字符数量}sum[x]++; // 当前字符数量增加1for (int L = 1; L <= n; L++){// ma保存最大逆序对个数 L-1-cnt[j]+num// L-1-cnt[j]是当前字符之后的比当前字符小的字符数量的最大值// num是1~pos+L-1前的比当前放置字符字典序大的字符数量int ma = -1, pos = 0, num = 0;for (int j = 26; j >= 1; j--){if (L - 1 - cnt[j] + num > ma){ma = L - 1 - cnt[j] + num;pos = j;}num += sum[j];}add2 += ma, cnt[pos]++;}if (now + add1 + add2 >= V){now += add1;return true;}else{sum[x]--;return false;}
}
signed main()
{string ans = "";cin >> V;for (int i = 1; ; i++){if (get_max(i) >= V){len = i;break;}}for (int i = 1; i <= len; i++){for (int j = 1; j <= 26; j++){if (check(j, len - i)){ans += char(j + 'a' - 1);break;}}}cout << ans << '\n';return 0;
}