第十三届蓝桥杯省赛C++ C组《全题目+题解》

填空题一般都是找规律题目，耐下心来慢慢分析即可。

第一题《排列字母》

【问题描述】

小蓝要把一个字符串中的字母按其在字母表中的顺序排列。
例如，LANQIAO 排列后为AAILNOQ。
又如，GOODGOODSTUDYDAYDAYUP 排列后为AADDDDDGGOOOOPSTUUYYY。
请问对于以下字符串，排列之后字符串是什么?
WHERETHEREISAWILLTHEREISAWAY

【答案提交】

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

【思路】简单模拟

【代码】

#include <iostream>
#include<algorithm>
using namespace std;
int main()
{string s;cin >> s;sort(s.begin(),s.end());cout << s;return 0;
}

【答案】

AAAEEEEEEHHHIIILLRRRSSTTWWWY

第二题《特殊时间》

【问题描述】

2022年2月22日22:20是一个很有意义的时间,年份为2022,由3个2和1个0组成,如果将月和日写成    
4位,为0222,也是由3个2和1个0组成,如果将时间中的时和分写成4位,还是由3个2和1个0组成。    
小蓝对这样的时间很感兴趣,他还找到了其它类似的例子,比如 111年10月11日01:11,2202年2月22日
22:02等等.    
请问,总共有多少个时间是这种年份写成4位、月日写成4位、时间写成4位后由3个一种数字和1个另一种数字组成。注意 1111 年11月11日11:11不算，因为它里面没有两种数字。

【答案提交】

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

【思路】模拟

【代码】

1月：0111  4*1*4=16
2月：0222  4*1*4=16
3月——9月：0 日最大不会超过31日，也不能出现00日的情况。
10月：1011 4*1*4=16
11月：1101 1110 1112 1113 1114 1115 1116 1117 1118 1119 1121
4*1*4 4*1*4 4*1*4 4*1*3 4*1*3 4*1*3 4*1*2 4*1*2 4*1*2 4*1*2 4*1*4 =16+16+16+12+12+12+8+8+8+8+16=64+36+32=132
12月：1211 1222   4*1*4 + 4*1*4 =32
总 ： 16+16+16+132+32 = 212;

【答案】

212

程序设计题尽可能打暴力

第三题《纸张尺寸》

【问题描述】

在 ISO 国际标准中定义了 A0 纸张的大小为 1189mm×841mm，将 A0 纸沿长边对折后为 A1纸，大小为 841mm×594mm，在对折的过程中长度直接取下整（实际裁剪时可能有损耗）。

将 A1 纸沿长边对折后为 A2 纸，依此类推。

输入纸张的名称，请输出纸张的大小。

【输入格式】

输入一行包含一个字符串表示纸张的名称，该名称一定是 A0、A1、A2、A3、A4、A5、A6、A7、A8、A9 之一。

【输出格式】

输出两行，每行包含一个整数，依次表示长边和短边的长度。

【输入样例1】

A0

【输出样例1】

1189

841

【输入样例2】

A1

【输出样例2】

841

594

【思路】简单模拟

【代码】

#include<iostream>
using namespace std;
int main(){string str;cin >> str;int length = 1189,width=841;int n = str[1] - '0';while(n--){if(length > width) length /= 2;else width /= 2;}if(length > width){printf("%d\n%d",length,width);}else{printf("%d\n%d",width,length);}return 0;
}

第四题《求和》

【问题描述】

给定 n 个整数 a1,a2,⋅⋅⋅,an，求它们两两相乘再相加的和，即

S=a1⋅a2+a1⋅a3+⋅⋅⋅+a1⋅an+a2⋅a3+⋅⋅⋅+an−2⋅an−1+an−2⋅an+an−1⋅an

【输入格式】

输入的第一行包含一个整数 n。

第二行包含 n 个整数 a1,a2,⋅⋅⋅,an。

【输出格式】

输出一个整数 S，表示所求的和。

请使用合适的数据类型进行运算。

【数据范围】

对于 30% 的数据，1≤n≤1000，1≤ai≤100。
对于所有评测用例，1≤n≤200000，1≤ai≤1000。

【输入样例】

4
1 3 6 9

 【输出样例】

117

【思路】简单模拟 / 前缀和

【代码】

#include<iostream>
using namespace std;
const int N = 200010;
int a[N],n;
long long res;
int main(){long long  s = 0;scanf("%d",&n);for(int i = 1;i<=n;i++) {scanf("%d",&a[i]);s += a[i];}for(int i = 1;i<n;i++){s -= a[i];res += a[i] * s;}printf("%lld",res);return 0;
}

第五题《数位排序》

【问题描述】

小蓝对一个数的数位之和很感兴趣，今天他要按照数位之和给数排序。

当两个数各个数位之和不同时，将数位和较小的排在前面，当数位之和相等时，将数值小的排在前面。

例如，2022 排在 409 前面，因为 2022 的数位之和是 6，小于 409 的数位之和 13。

又如，6 排在 2022 前面，因为它们的数位之和相同，而 6 小于 2022。

给定正整数 n，m，请问对 1 到 n 采用这种方法排序时，排在第 m 个的元素是多少？

【输入格式】

输入第一行包含一个正整数 n。

第二行包含一个正整数 m。

【输出格式】

输出一行包含一个整数，表示答案。

【数据范围】

对于 30% 的评测用例，1≤m≤n≤300。
对于 50% 的评测用例，1≤m≤n≤1000。
对于所有评测用例，1≤m≤n≤10的6次方。

【输入样例】

13

5

【输出样例】

3

【样例解释】

1 到 13 的排序为：1,10,2,11,3,12,4,13,5,6,7,8,9。

第 5 个数为 3。

【思路】自定义排序规则 + 提取每一位数字。

对如何提取每一位数字不熟悉的可以参考AcWing. 466 / NOIP2016普及组《回文日期》（C++）。

【代码】

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1000010;
int n,m;
int w[N],s[N];
bool cmp(int a,int b){if(s[a] != s[b]) return s[a]<s[b];return a < b;
}
int main(){scanf("%d%d",&n,&m);for(int i = 1;i<=n;i++){w[i] = i;for(int j = i;j;j /= 10){s[i] += j % 10;}}sort(w+1,w+n+1,cmp);printf("%d",w[m]);return 0;
}

第六题《选数异或》

【问题描述】

给定一个长度为 n 的数列 A1,A2,⋅⋅⋅,An 和一个非负整数 x，给定 m 次查询，每次询问能否从某个区间 [l,r] 中选择两个下标不同的数使得他们的异或等于 x。

【输入格式】

输入的第一行包含三个整数 n,m,x。

第二行包含 n 个整数 A1,A2,⋅⋅⋅,An。

接下来 m 行，每行包含两个整数 li,ri 表示询问区间 [li,ri]。

【输出格式】

对于每个询问，如果该区间内存在两个数的异或为 x 则输出 yes，否则输出 no。

【数据范围】

对于 20% 的评测用例，1≤n,m≤100；
对于 40% 的评测用例，1≤n,m≤1000；
对于所有评测用例，1≤n,m≤100000，0≤x<2的20次方，1≤li≤ri≤n，0≤Ai<2的20次方

【输入样例】

4 4 1
1 2 3 4
1 4
1 2
2 3
3 3

【输出样例】

yes
no
yes
no

【样例解释】

显然整个数列中只有 2,3 的异或为 1。

【思路】

状态表示：last[i] ： a[i] 左侧与 a[i] 配对的最近一个数的下标 ，g[i] : f[i]前缀的最大值 

状态转移：g[i]  = max(f[1],f[2] ..... f[i]);

补充 ：a ^ b = x 等价于 b = a ^ x 。

【代码】

#include<iostream>
using namespace std;
int n,m,x;
const int N = 100010,M = (1 << 20) + 10;
int last[M],g[N];
int main(){scanf("%d%d%d",&n,&m,&x);for(int i = 1;i<=n;i++){int a;scanf("%d",&a);g[i] = max(g[i-1],last[a^x]);last[a] = i;}while(m--){int l,r;scanf("%d%d",&l,&r);if(g[r] >= l) puts("yes");else puts("no");}return 0;
}

第七题《消除游戏》

【问题描述】

在一个字符串 S 中，如果 Si=Si−1 且 Si≠Si+1，则称 Si 和 Si+1 为边缘字符。

如果 Si≠Si−1且 Si=Si+1，则 Si−1 和 Si 也称为边缘字符。

其它的字符都不是边缘字符。

对于一个给定的串 S，一次操作可以一次性删除该串中的所有边缘字符（操作后可能产生新的边缘字符）。

请问经过 2的64次方 次操作后，字符串 S 变成了怎样的字符串，如果结果为空则输出 EMPTY。

【输入格式】

输入一行包含一个字符串 S。

【输出格式】

输出一行包含一个字符串表示答案，如果结果为空则输出 EMPTY。

【数据范围】

对于 25% 的评测用例，|S|≤10的3次方，其中 |S| 表示 S 的长度；
对于 50% 的评测用例，|S|≤10的4次方；
对于 75% 的评测用例，|S|≤10的5次方；
对于所有评测用例，|S|≤10的6次方，S 中仅含小写字母。

【输入样例1】

edda

【输出样例1】

EMPTY

【输入样例2】

sdfhhhhcvhhxcxnnnnshh

【输出样例2】

s

【思路】链表

【代码】

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;const int N = 1000010;int n;
char s[N];
int l[N], r[N];
vector<int> q, w;
bool st[N];void insert(int k)
{if (!st[k]){st[k] = true;w.push_back(k);}
}void filter_dels()
{w.clear();for (int k: q){int a = l[k], b = k, c = r[k];if (s[a] == s[b] && s[b] != s[c] && s[c] != '#'){insert(b);insert(c);}else if (s[a] != s[b] && s[b] == s[c] && s[a] != '#'){insert(a);insert(b);}}
}int main()
{scanf("%s", s + 1);n = strlen(s + 1);s[0] = s[n + 1] = '#';for (int i = 1; i <= n; i ++ ){l[i] = i - 1, r[i] = i + 1;q.push_back(i);}r[0] = 1, l[n + 1] = n;while (true){filter_dels();if (w.empty()) break;q.clear();for (int k: w){int a = l[k], b = k, c = r[k];if (!st[a] && a && (q.empty() || a != q.back())) q.push_back(a);if (!st[c] && c != n + 1) q.push_back(c);r[a] = c, l[c] = a;}}if (r[0] == n + 1) puts("EMPTY");else{for (int i = r[0]; i != n + 1; i = r[i])printf("%c", s[i]);}return 0;
}

第八题《重新排序》

【问题描述】

给定一个数组 A 和一些查询 Li,Ri，求数组中第 Li 至第 Ri 个元素之和。

小蓝觉得这个问题很无聊，于是他想重新排列一下数组，使得最终每个查询结果的和尽可能地大。

小蓝想知道相比原数组，所有查询结果的总和最多可以增加多少?

【输入格式】

输入第一行包含一个整数 n。

第二行包含 n 个整数 A1,A2,⋅⋅⋅,An，相邻两个整数之间用一个空格分隔。

第三行包含一个整数 m 表示查询的数目。

接下来 m 行，每行包含两个整数 Li、Ri，相邻两个整数之间用一个空格分隔。

【输出格式】

输出一行包含一个整数表示答案。

【数据范围】

对于 30% 的评测用例，n,m≤50；
对于 50% 的评测用例，n,m≤500；
对于 70% 的评测用例，n,m≤5000；
对于所有评测用例，1≤n,m≤10的5次方，1≤Ai≤10的6次方，1≤Li≤Ri≤n。

【输入样例】

5
1 2 3 4 5
2
1 3
2 5

【输出样例】

 4

 【样例解释】

原来的和为 6+14=20，重新排列为 (1,4,5,2,3) 后和为 10+14=24，增加了 4。

【思路】差分 + 贪心 + 排序不等式

不了解差分的可以参考【模板】AcWing797.《差分》(C++)

不了解排序不等式的可以参考模板：排序不等式】AcWing913.《排队打水》(C++)

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;typedef long long LL;const int N = 100010;int n, m;
int w[N], s[N];int main()
{scanf("%d", &n);for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);scanf("%d", &m);while (m -- ){int l, r;scanf("%d%d", &l, &r);s[l] ++, s[r + 1] -- ;}for (int i = 1; i <= n; i ++ )s[i] += s[i - 1];LL sum1 = 0;for (int i = 1; i <= n; i ++ )sum1 += (LL)s[i] * w[i];LL sum2 = 0;sort(s + 1, s + n + 1);sort(w + 1, w + n + 1);for (int i = 1; i <= n; i ++ )sum2 += (LL)s[i] * w[i];printf("%lld\n", sum2 - sum1);return 0;
}

第九题《技能升级》

【问题描述】

小蓝最近正在玩一款 RPG游戏。

他的角色一共有 N 个可以加攻击力的技能。

其中第 i 个技能首次升级可以提升 Ai 点攻击力，以后每次升级增加的点数都会减少 Bi。

⌈Ai/Bi⌉（上取整）次之后，再升级该技能将不会改变攻击力。

现在小蓝可以总计升级 M 次技能，他可以任意选择升级的技能和次数。

请你计算小蓝最多可以提高多少点攻击力？

【输入格式】

输入第一行包含两个整数 N 和 M。

以下 N 行每行包含两个整数 Ai 和 Bi。

【输出格式】

输出一行包含一个整数表示答案。

【数据范围】

对于 40% 的评测用例，1≤N,M≤1000；
对于 60% 的评测用例，1≤N≤10的4次方，1≤M≤10的7次方；
对于所有评测用例，1≤N≤10的5次方，1≤M≤2×10的9次方，1≤Ai,Bi≤10的6次方。

【输入样例】

3 6
10 5
9 2
8 1

【输出样例】

47

【思路】贪心 + 多路归并 + 二分

【代码】

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;typedef long long LL;const int N = 100010;int n, m;
int a[N], b[N];bool check(int mid)
{LL res = 0;for (int i = 0; i < n; i ++ )if (a[i] >= mid)res += (a[i] - mid) / b[i] + 1;return res >= m;
}int main()
{scanf("%d%d", &n, &m);for (int i = 0; i < n; i ++ ) scanf("%d%d", &a[i], &b[i]);int l = 0, r = 1e6;while (l < r){int mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;}LL res = 0, count = 0;for (int i = 0; i < n; i ++ )if (a[i] >= r){int cnt = (a[i] - r) / b[i] + 1;count += cnt;int end = a[i] - (cnt - 1) * b[i];res += (LL)(a[i] + end) * cnt / 2;}printf("%lld\n", res - (count - m) * r);return 0;
}

第十题《重复的数》

【问题描述】

给定一个数列 A=(a1,a2,⋅⋅⋅,an)，给出若干询问，每次询问某个区间 [li,ri] 内恰好出现 ki 次的数有多少个。

【输入格式】

输入第一行包含一个整数 n 表示数列长度。

第二行包含 n 个整数 a1,a2,⋅⋅⋅,an，表示数列中的数。

第三行包含一个整数 m 表示询问次数。

接下来 m 行描述询问，其中第 i 行包含三个整数 li,ri,ki 表示询问 [li,ri] 区间内有多少数出现了 ki次。

【输出格式】

输出 m 行，分别对应每个询问的答案。

【数据范围】

对于 20% 的评测用例，n,m≤500，1≤a1,a2,⋅⋅⋅,an≤1000；
对于 40% 的评测用例，n,m≤5000；
对于所有评测用例，1≤n,m≤100000，1≤a1,a2,⋅⋅⋅,an≤100000，1≤li≤ri≤n，1≤ki≤n。

【输入样例】

3
1 2 2
5
1 1 1
1 1 2
1 2 1
1 2 2
1 3 2

【输出样例】

1
0
2
0
1

【思路】莫队

【代码】

#include<bits/stdc++.h>
using namespace std;
const int N = 101000;int sq;
struct query {int l, r, id, cnt;bool operator<(const query& t)const{if (l / sq != t.l / sq)return l < t.l;if (l / sq & 1)return r < t.r;return r > t.r;}
}q[N];
int cur, cnt[N], a[N], ans[N], s[N];
int l = 1, r, n, m;void add(int p)
{cnt[s[p]]--;cnt[++s[p]]++;
}void del(int p)
{cnt[s[p]]--;cnt[--s[p]]++;
}int main()
{scanf("%d", &n);sq = sqrt(n);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);scanf("%d", &m);for (int i = 0; i < m; i++){int l, r, k;scanf("%d%d%d", &l, &r, &k);q[i] = { l, r, i, k };}sort(q, q + m);for (int i = 0; i < m; i++){while (l > q[i].l)add(a[--l]);while (r < q[i].r)add(a[++r]);while (l < q[i].l)del(a[l++]);while (r > q[i].r)del(a[r--]);ans[q[i].id] = cnt[q[i].cnt];}for (int i = 0; i < m; i++)printf("%d\n", ans[i]);return 0;
}