2021第十二届蓝桥杯国赛B组题解(C/C++)
- 全面收集题目；
- 现有的答案主要在群里处理，并如有错误可在评论区指出；
- 初步标记的大题可能获得分数，并仍需进一步确认是否完全正确。
试题 A: 带宽[5 分]
【问题描述】
假如使用小蓝家的网络，则理论上每秒最多能下载多少MB的内容？
【答案：25】
200M带宽 实际网速每秒25M 带宽 除以 8 等于 每秒网速
试题 B: 纯质数[5 分]
【问题描述】
如果一个正整数只有 1 和它本身两个约数，则称为一个质数（又称素数）。
前几个质数是：2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, · · · 。
我们称所有十进制位上的数字均为质数的质数为纯质数。
例如：2、3、5、7、23、37均为纯质数。
当然这些数字如1、4、35等也不是。
请问，在 1 到 20210605 中，有多少个纯质数？
【答案：1903】
思路：暴力模拟
#include<bits/stdc++.h>
#include<iostream>
#define ll long long
using namespace std;
// 0 1 2 3 4 5 6 7 8 9
int book[11] = {0,0,1,1,0,1,0,1,0,0};
int noprime[100000000];
void check(){
int e = 20210605;
noprime[0] = 1,noprime[1] = 1,noprime[2] = 0;
for(int i = 2; i <= e; i++){
if(!noprime[i]){
for(int j = i * 2; j <= e; j+=i){
noprime[j] = 1;
}
}
}
}
int check(int i){
if(noprime[i]) return 0;
while(i){
int n = i % 10;
if(!book[n]) return 0;
i /= 10;
}
return 1;
}
int main(){
int ans = 0;
check();
for(int i = 1; i <=20210605; i++){
ans += check(i);
}
cout << ans;
return 0;
}试题 C: 完全日期[10 分]
【问题描述】
在一个给定的日期中（年月日），如果将其各位数字相加之和所得结果为某整数的平方，则称这一天为"完全日期"（perfect day））。例如：2021年6月5日的各位数字之和为2+0+2+1+6+5=16=4²，则这一天是一个"完全日期"；同样地，在2021年6月23日中也是如此（因为其各位数字之和也为16）。那么在从2001年1月1日到2021年12月31日这段时间内共有多少个这样的"完全日期"呢？
【答案：977】
解题思路为暴力模拟配合EXCEL公式进行数据处理。由于对EXCEL日期计算不熟悉，在此选择手动计算的方式较为便捷。如果有能力编写简短的代码段落，则问题迎刃而解。
//T3
#include<bits/stdc++.h>
#include<iostream>
#define ll long long
using namespace std;
// 1 2 3 4 5 6 7 8 9 10
int month[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int month1[13] = {0,31,29,31,30,31,30,31,31,30,31,30,31};
int run(int y){
if(( y % 4 == 0 && y % 100!=0) || y % 400 == 0){
return 1;
}
return 0;
}
int check(int y,int m,int d){
int sum = 0;
while(y){
sum += (y % 10);
y /= 10;
}
while(m){
sum += (m % 10);
m /= 10;
}
while(d){
sum += (d % 10);
d /= 10;
}
for(int i = 1; i <= 20; i++){
if(i*i == sum){
return 1;
}
}
return 0;
}
int main(){
int y = 2001,m = 1,d = 1;
int ans = 0;
while(1){
int flag = check(y,m,d);
if(flag){
cout << y << m << d << endl;
}
ans += flag;
if(y == 2021 && m == 12 && d == 31)
break;
d++;
if(run(y)){
if(d > month1[m]){
m++;
d = 1;
}
}else{
if(d > month[m]){
m++;
d = 1;
}
}
if(m > 12){
y++;
m = 1;
}
}
cout << ans;
return 0;
}试题 D: 最小权值[10 分]
【问题描述】
对于一棵以节点v为根的二叉树_T_（其中_T_是一个具有明确父-子关系的数据结构），计算机科学家小蓝提出了该棵树中各节点计算方式如下：若子树为空，则其权值W(T)为零。
【答案: 有人说全为左子树也有人说dp】
解题思路：在解题过程中发现如果全部都是左子树的话
计算量实在过于庞大以至于难以继续下去，
时间也几乎所剩无几，
但若知早些年就能熟练掌握Python编程技巧，则问题迎刃而解。
# py语法有点忘了，忽略，大致就下面这样
ans = 0;
for num in range(1,2021):
ans = 2*ans + 1
print(ans)另一种说法：
W[V] = 1 + 2W(L) + 3W® + (C(L))2 C®
dp(n)=1+2dp(i)+3dp(n-i-1)+i i(n-i-1)
用dp去推算
试题 E: 大写[15 分]
时间限制: 1.0s 内存限制: 256.0MB
【问题描述】
假设有一个由大写字母与小写字母组成的字符串S，请对其中的所有小写字母进行转译为大写字母的操作，并输出处理后的结果。
【输入格式】
输入一行包含一个字符串。
【输出格式】
输出转换成大写后的字符串。
【样例输入 1 】
LanQiao
【样例输出 1 】
LANQIAO
【评测用例规模与约定】
对于所有评测用例，字符串的长度不超过 100。
【解题思路：有手就行 100%】
这题我甚至以为我在打省赛签到题
我好像忘记cout输出了。。尴尬
#include<bits/stdc++.h>
#include<iostream>
#define ll long long
using namespace std;
int main(){
string str;
cin >> str;
for(int i = 0; i < str.length(); i++){
if(str[i] >= 'a' && str[i] <= 'z'){
str[i] -= ('a'-'A');
}
}
cout << str;
return 0;
}试题 F: 123[15 分]
时间限制: 1.0s 内存限制: 256.0MB
【问题描述】
小蓝发现了具有规律性的整数序列。前十项依次为：
1, 1, 2, 1, 2, 3, 1, 2, 3, 4,...
观察发现，在该序列中：
- 前面一项仅包含数字1；
- 接下来的两项分别是1和2；
- 接着三项依次为1、2、3；
- 然后四项分别为1、2、3、4；依此类推。
为了便于研究，小蓝首先关注该序列中任意连续若干项的总和。
【输入格式】
程序的第一行为用户提供了一个整数值 T ，该值表示后续问题的数量。
随后的 T 行将依次给出这些查询问题的具体内容。
每一行为一组特定的询问信息提供详细说明。
其中 li 和 ri 分别代表该区间内的起始索引与结束索引。
【输出格式】
输出 _T _行，每行包含一个整数表示对应询问的答案。
【样例输入】
3
1 1
1 3
5 8
【样例输出】
1
4
8
【评测用例规模与约定】
在 10% 的测试场景中（占总情形的十分之一），T值介于31至30之间，并且每个区间内的参数范围满足_li_ ≤ ri ≤ 100的要求）。针对约20%的测试情况（约占总测试量的二成），T值控制在31至100之间，并要求参数区间满足_li_ ≤ ri ≤ 1, 值不超过1, 符合条件的情况）。当测试难度进一步提升时（达到4/7的比例），T值范围扩展至31至一千之间，并维持参数区间限制为_li_ ≤ ri ≤ 一千零六的要求）。对于接近满分水平的测试案例（占7/8的比例），T值设定为3, 值以上到一万零九之间的范围，并要求参数区间依旧满足_li_ ≤ ri ≤ 千一十二）。在最高难度级别（即满分要求）下（占全部测试案例的比例为9/8），T值必须严格控制在3, 值以上到一万零九之间的范围内；而对于所有测试场景（无论难易程度如何），都必须满足_T_值不超过一万零五十二这一硬性指标；同时参数区间仍需满足_li_ ≤ ri ≤ 千一十二的要求）。
解题思路：类比金字塔+前缀和 <= 100%
解题方法论：借鉴金字塔结构进行前缀计算 ，确保不超过100%
解题方法论：借鉴金字塔结构进行前缀计算 ，确保不超过100%
将数列看成金字塔，转换成求第na层第ca个数到nb层cb个数中间
1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
思路举例：
例题中的5 8 ==> 8
[第3层第2个数值] --[第4层第2个数值] :（2 + 3）后部+0间层+(1 + 2)前部=8
再举一个直观的例子：4 15 ==>21
[第3层第一个数值] – [第5层第五个数值]:6后部+10间层+15前部=21
然后讲上述思路转换为编程思路：
采用层次化的方式进行问题拆解，并逐步解决每个模块即可完成任务。
首先计算所需层数：满足(1+x)x/2 ≥ 1e12的最小整数x约为一百五十万层。
因此，在一百五十万层的情况下，总数据量达到十亿级可使用数组轻松存储。
关键在于以下公式：总和等于前缀和中位于中间两层的数据之和加上当前上层部分的数量与下层层部分的数量之和。
对于任意给定的n值，在其所属层级中找到对应的索引位置。
通过上述步骤可快速确定任意给定索引对应的数值范围及其具体位置。
#include<bits/stdc++.h>
#include<iostream>
#define ll long long
using namespace std;
ll dp[1500000]; // 每一层的和
ll dpSum[1500000]; // 层的前缀和
/*int dp[30] = {0,1,1,2,1,2,3,1,2,3,4,1,2,3,4,5,1,2,3,4,5,6};
1 1
2 1 2
3 1 2 3
4 1 2 3 4
5 1 2 3 4 5
*/
//函数思路是找到a和b是第几层的第几个
//sum = 前缀和求ab中间层数的和 + a当前层后面几个数量 + b当前层前面几个数量
ll check(ll a,ll b){
ll temp = 1;
ll flag = 1;
while((temp+1)*(temp)/2 < a){
temp++;
}
ll aDeep = temp,aCnt = aDeep - (((aDeep+1)*(aDeep)/2) - a);
temp = 1;
flag = 1;
while((temp+1)*(temp)/2 < b){
temp++;
}
ll bDeep = temp,bCnt = bDeep - (((bDeep+1)*(bDeep)/2) - b);
ll sum = 0;
//cout << aDeep << ' ' << aCnt << ' ' << bDeep << ' ' << bCnt << endl;
if(bDeep > aDeep)
sum = dpSum[bDeep-1] - dpSum[aDeep];
if(bDeep > aDeep){
sum += (aDeep+aCnt)*(aDeep+1-aCnt)/2;
sum += (1+bCnt)*(bCnt+1-1)/2;
}else{
sum += (aCnt + bCnt)*(bCnt + 1 - aCnt)/2;
}
return sum;
}
int main(){
dp[0] = 0;
dpSum[0] = 0;
//推算到 1500000层正好大约1e12次方个数
//处理1500000层的数据
for(int i = 1; i <= 1500000; i++){
dp[i] = dp[i-1] + i;
dpSum[i] = dpSum[i-1] + dp[i];
}
//输入数据
ll n;
cin >> n;
for(ll i = 0; i < n; i++){
ll a, b;
cin >> a >> b;
cout << check(a,b) << endl;
}
return 0;
}试题 G: 异或变换[20 分]
时间限制: 1.0s 内存限制: 256.0MB
【问题描述】
小蓝拥有一串二进制序列s = s₁, s₂, s₃,…,sₙ。
每次变换遵循以下规则：
新序列的第一个元素与原序列相同；
其余元素为前一个元素与当前元素的异或运算结果。
其中a⊕b表示两个二进制位的异或运算：
若a和b相同，则结果为0；
若不同，则结果为1。
经过t次变换后的新序列为多少？
【输入格式】
第一行提供两个整数_n_和_t_作为参数值，在算法运行中分别用于计算二进制字符串的长度以及执行必要的转换操作次数。接下来的一行则包含了该二进制字符串的具体内容。
【输出格式】
输出一行包含一个 01 串，为变换后的串。
【样例输入】
5 3
10110
【样例输出】
11010
【样例说明】
初始时为 10110，变换 1 次后变为 11101，变换 2 次后变为 10011，变换 3
次后变为 11010。
【评测用例规模与约定】
对于 40% 的评测用例，1 ≤ _n _≤ 100, 1 ≤ _t _≤ 1000。
对于 80% 的评测用例，1 ≤ _n _≤ 1000, 1 ≤ _t _≤ 109。
对于所有评测用例，1 ≤ _n _≤ 10000, 1 ≤ _t _≤ 1018。
【解题思路：set去重找规律 40%+】
map记录第几个是那种样子
set标记，第二次遇上就退出循环
//变异
#include<bits/stdc++.h>
#include<iostream>
#define ll long long
using namespace std;
map<ll,string> m;
set<string> s;
int main(){
ll len,cnt,cntTemp;
cin >> len >> cnt;
cntTemp = cnt;
string str;
cin >> str;
ll flag = 0;
while(cnt--){
string temp = str;
for(int i = 1; i < len; i++){
temp[i] = (str[i-1]-'0')^(str[i]-'0') + '0';
}
//cout << temp << endl;
if(s.count(temp) == 1){
//cout<< "提前循环";
break;
}
s.insert(temp);
flag += 1;
m[flag] = temp;
str = temp;
}
if(cnt < 0){
cout << str;
}else{
ll index = cntTemp % flag;
if(index == 0) index = flag;
cout<< m[index];
}
return 0;
}试题 H: 二进制问题[20 分]
时间限制: 1.0s 内存限制: 256.0MB
【问题描述】
最近，小蓝正在进行二进制的学习。他希望了解，在数字范围从1到_N_时，有多少个数字的二进制形式恰好包含_K_个1？能否为他提供帮助？
【输入格式】
输入一行包含两个整数 _N _和 K 。
【输出格式】
输出一个整数表示答案。
【样例输入】
7 2
【样例输出】
3
【评测用例规模与约定】
对于 30% 的评测用例，1 ≤ _N _≤ 106, 1 ≤ _K _≤ 10。
对于 60% 的评测用例，1 ≤ _N _≤ 2 × 109, 1 ≤ _K _≤ 30。对于所有评测用例，1 ≤ _N _≤ 1018, 1 ≤ _K _≤ 50。
【解题思路：dfs混 <60%的分】
暴力循环遍历能够稳定获取三分之一左右的成绩。
利用深度优先搜索策略可以轻松获取60%的分数。
然而，在考试时间有限的情况下难以完成其他情况的分析。
#include<bits/stdc++.h>
#include<iostream>
#define ll long long
using namespace std;
// 60位数可以表示1e18
// dp / 搜索
int temp[60] = {0},maxNum[60] = {0};
int pos[60] = {0}; //第几个i在哪个位置
string str;
ll N,K;
ll ans = 1;
int haveOne = 0,Cnt;
//第n个1
int find(int n){
for(int i = 0; i < Cnt; i++){
}
}
void dfs(int n){
if(n < 0) return;
int nowIndex = pos[n];
int tIndex = nowIndex + 1;
while(tIndex < Cnt && maxNum[tIndex] == 0){
swap(maxNum[tIndex],maxNum[nowIndex]);
ans++;
dfs(n-1);
swap(maxNum[tIndex],maxNum[nowIndex]);
tIndex++;
}
dfs(n-1);
}
int main(){
cin >> N >> K;
Cnt = 0;
while(N){
temp[Cnt++] = N % 2;
N/=2;
}
for(int i = 0; i < Cnt; i++){
maxNum[i] = temp[Cnt - 1 - i];
if(maxNum[i] == 1){
pos[haveOne++] = i;
}
//cout << maxNum[i] << endl;
}
//已有的大于需要的就舍去后面的1
if(haveOne > K){
int flag = haveOne - K;
while(flag--){
for(int i = Cnt - 1; i >= 0; i--){
if(maxNum[i] == 1){
maxNum[i] = 0;
break;
}
}
}
}
else if(haveOne < K){ //已有的小于需要的就从前面补
int flag = K - haveOne;
while(flag--){
for(int i = 0; i < Cnt; i++){
if(maxNum[i] == 0){
maxNum[i] = 1;
pos[haveOne++] = i;
break;
}
}
}
}
haveOne = K;
/*for(int i = 0; i < haveOne; i++){
cout << pos[i];
}*/
dfs(haveOne-1);
cout << ans;
return 0;
}试题 I: 翻转括号序列[25 分]
时间限制: 2.0s 内存限制: 512.0MB
【问题描述】
给定一个长度为 n 的括号序列 S，请完成以下功能：
- 对位于 [Li, Ri] 区间的字符进行翻转（左括号变右括号、右括号变左括号）。
- 求出以 Li 为左端点时最长的合法括号序列所对应的右端点 Ri（即从该左端点出发向右扩展尽可能多的有效配对区间的最远位置）。
- 输出该区间内满足条件的有效配对区间的最右端点 Rj。
Ri 使 [Li, Ri] 是一个合法括号序列）。
【输入格式】
输入的第一行由两个整数n, m构成，请注意它们分别代表以下内容：
- 括号序列的总长度
- 操作的总次数
第二行给出具体的括号序列。
这些括号仅包含左半边括弧和右半边括弧两种类型。
接下来的m条指令将按照以下两种形式给出：
- 如果是第一类指令（标记为'1'），则会指定一个区间[Li, Ri]
- 如果是第二类指令（标记为'2'），则只需指定左端点的位置Li
关于输出部分：
对于每一种第二类的操作，请您将对应的Ri值输出在新的一行上。
若找不到对应的匹配对象，则请输出数值0。
【样例输入】
7 5
((())()
2 3
2 2
1 3 5
2 3
2 1
【样例输出】
4
7
0
0
评测用例规模与约定
评测用例规模与约定
解题思路: 压缩并查集+提前标记 <=100%
解题思路: 使用并查集进行操作，并在标记时控制比例至多为100%
因为每次查找都会耗费时间，并且案例规模较大，在执行调转操作后需要记录每个点对应的匹配点位置。
在此过程中存在一种情况：当前状态下的多个候选匹配点（此处未明确具体数量）均截止于同一个位置（此处未明确具体位置），但根据最远匹配原则应将它们划分为连续的区间（如1-2位、3-4位、5-6位等），然而由于最远匹配策略的影响，在这种情况下需要对后续的匹配过程进行延展。
具体而言，在初始状态中我们有：
fa[1]=2, fa[2]=0, fa[3]=4, fa[4]=6；
随后在处理到fa[1]时，则检查其右侧是否有继续匹配的可能性。
若fa[f_a+1]不为空，则继续延展匹配区间；反之则需回退至最后一个有效位置。
具体操作如下：
首先处理fa^{}=2；
接着处理f_a+1=3的位置：
因为f_a[f_a+1]\neq0所以继续延展；
接着处理f_a=4的位置：
同样满足f_a[f_a+1]\neq0条件；
随后处理f_a=5的位置：
由于f_a[f_a+1]=0无法继续延展；
最终确定最终位置为6并返回。
最后将所有相关变量值更新为新的结果即可完成整个过程。
#include<bits/stdc++.h>
#include<iostream>
#define ll long long
using namespace std;
map<int ,int > mp;
string str;
int num[1000005];
int n,m;
//初始化
void init(){
mp.clear();
stack<int> sta;
for(int i = 1; i <=n ; i++){
if(num[i] == 1){
sta.push(i);
}else if(num[i] == 0 && sta.size()){
int index = sta.top();
if(index != 0){
sta.pop();
mp[index] = i;
}
}else if(num[i] == 0 && !sta.size()){
sta.push(0);
}
}
}
//改造的压缩并查集
int findFa(int a,int deep){
if(mp[a] == 0 && deep == 0){
return 0;
}
if(mp[a] == 0){
return a - 1;
}
mp[a] =findFa(mp[a]+1,deep+1);
return mp[a];
}
int main(){
cin >> n >> m;
cin >> str;
//处理输入变成01串，方便倒置 ！str[i]就行
for(int i = 0;i < n; i++){
if(str[i] == '('){
num[i+1] = 1;
}else{
num[i+1] = 0;
}
}
init();
for(int i = 0; i < m; i++){
int flag;
cin >> flag;
//倒置
if(flag == 1){
int a,b;
cin >> a >> b;
for(int j = a; j <= b; j++){
num[j] = !num[j];
}
init();
}else{
//直接查询
int a;
cin >> a;
cout << findFa(a,0) << endl;
}
}
return 0;
}试题 J: 异或三角[25 分]
时间限制: 1.0s 内存限制: 256.0MB
【问题描述】
给定 T 个数 n1, n2, · · · , nT ，对每个 ni 请求出有多少组 a, b, c 满足：
- 1 ≤ a, b, c ≤ ni；
a ⊕ b ⊕ c = 0，其中 ⊕ 表示二进制按位异或；
长度为 a, b, c 的三条边能组成一个三角形。
【输入格式】
输入的第一行包含一个整数 T 。
接下来 T 行每行一个整数，分别表示 n1, n2, · · · , nT 。
【输出格式】
输出 T 行，每行包含一个整数，表示对应的答案。
【样例输入】
2
6
114514
【样例输出】
6
11223848130
【评测用例规模与约定】
对于 10% 的评测用例，T = 1, 1 ≤ ni ≤ 200；
对于 20% 的评测用例，T = 1, 1 ≤ ni ≤ 2000；对于 50% 的评测用例，T = 1, 1 ≤ ni ≤ 220；
对于 60% 的评测用例，1 ≤ T ≤ 100000, 1 ≤ ni ≤ 220；
对于所有评测用例，1 ≤ T ≤ 100000
【解题思路[暴力遍历2000] <= 20%】
没啥说的，能力不够，感觉蓝桥杯今年突然爱上了二进制和一些异或操作
i <= j <= k <= 2000三层遍历。
感觉应该先判断下T再预处理。。怕2000超时10%都拿不到。。失算了
#include<bits/stdc++.h>
#include<iostream>
#define ll long long
using namespace std;
int check(int a,int b,int c){
if(a == 0 || b == 0 || c == 0) return 0;
if(a + b <= c) return 0;
if(b + c <= a) return 0;
if(a + c <= b) return 0;
return 1;
}
int dp[300] = {0};
int main(){
int n = 100;
ll ans = 1;
for(int i = 1; i <= n; i++){
for(int j = i; j <=n; j++){
for(int k = j; k <= n; k++){
int ji = i ^ j ^ k;
if(ji == 0 && check(i,j,k)){
//printf("%d %d %d %d\n",i,j,k,i^j^k);
dp[k]++;
}
}
}
}
for(int i = 1; i <= n; i++){
dp[i] = dp[i] + dp[i-1];
}
int T;
cin >> T;
while(T--){
int temp;
cin >> temp;
cout << dp[temp] * 6 << endl;
}
return 0;
}总结：暴力杯变了~
这次蓝桥杯的体验略显平淡，并非完全没有收获。虽然打完后没什么特别的遗憾感，但整体而言，在能力提升方面仍有提升空间。对于已掌握的知识点如二进制运算等较为熟练掌握，而对于难度较高的内容如大规模数据处理则仍有一定困难。仅在填空题部分未能完成相关问题解答，并因时间限制未能完成后续模块的编程练习。其他模块的完成情况较为理想。回顾去年下半年的比赛经历确实收获颇丰，在此基础上本次比赛再获佳绩实属不易。