第十三届蓝桥杯省赛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=162月：0222  4*1*4=163月——9月：0 日最大不会超过31日，也不能出现00日的情况。10月：1011 4*1*4=1611月：1101 1110 1112 1113 1114 1115 1116 1117 1118 1119 11214*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=13212月：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;}

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/xuetang/2024-03-24/147850.html，文章来源：网络cs，作者：欧阳逸，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！