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; // 答案624
return 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; // 答案2481215
return 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]; // 答案761
return 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;
else
sum += 1;
week = (week + 1) % 7;
if (year == 2020 && month == 10 && day == 1)
{
cout << sum << endl; // 到时间就退出来, 答案8879
return 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 7
e[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分)
题目描述:
输入测试:
7
80
92
56
74
88
100
0
解析代码(格式化输出)
注意要输入%%才表示输出%
#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=1234
int left = i;
int right = i; // 构造出来的回文串,构造出来的回文串即:12344321
for (int j = 0; j < 4; ++j)
{
right = right * 10 + left % 10; // 1234*10+1234%10
left = 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]++; // 当前字符数量增加1
for (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;
}