第十三届蓝桥杯省赛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;
}

标签：蓝桥杯 c++ 算法

本文转载自: https://blog.csdn.net/m0_74172965/article/details/136683620
版权归原作者 北洋的霞洛 所有，如有侵权，请联系我们删除。