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

第十三届蓝桥杯省赛C++ C组《全题目+题解》
填空题一般都是找规律题目，耐下心来慢慢分析即可。

第一题《排列字母》

【问题描述】

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

【答案提交】

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

【思路】简单模拟

【代码】
```
#include 
#include
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
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
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
        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
#include
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]
    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
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 
#include 
#include 
#include 
 
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 
#include 
#include 
 
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 
#include 
#include 
 
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
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;
}
```
相关阅读:
文件管理系统-----文件的逻辑结构
 程序员凭本事赚钱被没收所得，是否体现了“重刑主义”？
pytorch-gpu（Anaconda3+cuda+cudnn）
未来电商怎么走，是腾讯视频号，还是抖音小店？你更看好谁？
【kubernetes】使用virtual-kubelet扩展k8s
赶紧进来看看!!!你一定要会做的八道经典指针笔试题!!!
最全分布式面试题整理
 12.1 使用键盘鼠标监控钩子
 网页JS自动化脚本(七)使用在线jQuery来操作元素
 Windows10 子系统 (WSL) 或 docker wsl 模式修改虚拟磁盘目录
原文地址：https://blog.csdn.net/m0_74172965/article/details/136683620

第一题《排列字母》

【问题描述】

【答案提交】

【思路】简单模拟

【代码】

【答案】

第二题《特殊时间》

【问题描述】

【答案提交】

【思路】模拟

【代码】

【答案】

第三题《纸张尺寸》

【问题描述】

【输入格式】

【输出格式】

【输入样例1】

【输出样例1】

【输入样例2】

【输出样例2】

【思路】简单模拟

【代码】

第四题《求和》

【问题描述】

【输入格式】

【输出格式】

【数据范围】

【输入样例】

【输出样例】

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

【代码】

第五题《数位排序》

【问题描述】

【输入格式】

【输出格式】

【数据范围】

【输入样例】

【输出样例】

【样例解释】

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

【代码】

第六题《选数异或》

【问题描述】

【输入格式】

【输出格式】

【数据范围】

【输入样例】

【输出样例】

【思路】

【代码】

第七题《消除游戏》

【问题描述】

【输入格式】

【输出格式】

【数据范围】

【输入样例1】

【输出样例1】

【输入样例2】

【输出样例2】

【思路】链表

【代码】

第八题《重新排序》

【问题描述】

【输入格式】

【输出格式】

【数据范围】

【输入样例】

【输出样例】

【样例解释】

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

第九题《技能升级》

【问题描述】

【输入格式】

【输出格式】

【数据范围】

【输入样例】

【输出样例】

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

【代码】