2022年蓝桥杯省赛C/C++大学A组代码

发表于 更新于 分类于 阅读次数： 本文字数： 5.6k 阅读时长 ≈ 21 分钟

2023的题还需要烧烤一下/(ㄒoㄒ)/~~
所以先做2022的题
暂未完成：最长上升子序列

P8770 [蓝桥杯 2022 省 A] 填空问题

题目描述

试题 A ：裁纸刀

【问题描述】

小蓝有一个裁纸刃，每次可以将一张纸沿一条直线裁成两半。

小蓝用一张纸打印出两行三列共 个二维码，至少使用九次裁出来，下图给出了一种裁法。

在上面的例子中，小蓝的打印机没办法打印到边缘，所以边缘至少要裁 次。另外，小蓝每次只能裁一张纸，不能重叠或者拼起来裁。

如果小蓝要用一张纸打印出 行 列共 个二维码，他至少需要裁多少次?

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

试题 B：灭鼠先锋

【问题描述】

灭鼠先锋是一个老少咸宜的棋盘小游戏，由两人参与，轮流操作。

灭鼠先锋的棋盘有各种规格，本题中游戏在两行四列的棋盘上进行。游戏的规则为：两人轮流操作，每次可选择在棋盘的一个空位上放置一个棋子，或在同一行的连续两个空位上各放置一个棋子，放下棋子后使棋盘放满的一方输掉游戏。

小蓝和小乔一起玩游戏，小蓝先手，小乔后手。小蓝可以放置棋子的方法很多，通过旋转和翻转可以对应如下四种情况:

1
2
X000 XX00 OXOO OXXO
0000 0000 0000 0000

其中 O 表示棋盘上的一个方格为空，X 表示该方格已经放置了棋子。

请问，对于以上四种情况，如果小蓝和小乔都是按照对自己最优的策略来玩游戏，小蓝是否能获胜。如果获胜，请用 V 表示，否则用 L 表示。请将四种情况的胜负结果按顺序连接在一起提交。

解法

裁纸刀

灭鼠先锋

博弈论

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits\stdc++.h>
using namespace std;
char board[5];
bool dfs()
{
    if (strcmp(board, "XXXX") == 0)
    {
        return false;
    }
    for (int i = 0; i < 4; i++)
    {
        if (board[i] == 'O')
        {
            board[i] = 'X';
            if (!dfs())
            {
                board[i] = 'O';
                return true;
            }
            if (board[i + 1] == 'O')
            {
                board[i + 1] = 'X';
                if (!dfs())
                {
                    board[i] = 'O';
                    board[i + 1] = 'O';
                    return true;
                }
                board[i + 1] = 'O';
            }
            board[i] = 'O';
        }
    }
}
int main()
{
    char con[][5] = {"XOOO", "XXOO", "OXOO", "OXXO"};
    for (int i = 0; i < 4; i++)
    {
        strcpy(board, con[i]);
        if (!dfs())//you fail
            putchar('V');
        else
            putchar('L');
    }
    return 0;
}

[蓝桥杯 2022 省 A] 求和

题目描述

给定 个整数 , 求它们两两相乘再相加的和，即

输入格式

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

第二行包含 个整数 。

输出格式

输出一个整数 ，表示所求的和。请使用合适的数据类型进行运算。

样例 #1

样例输入 #1

1
2
4
1 3 6 9

样例输出 #1

1
117

提示

对于 的数据, 。

对于所有评测用例, 。

蓝桥杯 2022 省赛 A 组 C 题。

解法

后缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using ll=unsigned long long;
const int N=(2e5)+5;
using namespace std;
int n;
int a[N];
ll sum=0;
ll ans=0;
int main() {
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=n-1;i>=0;i--){
        ans+=a[i]*sum;
        sum+=a[i];
    }
    printf("%lld",ans);
    return 0;
}

[蓝桥杯 2022 省 A] 选数异或

题目描述

给定一个长度为 的数列 和一个非负整数 , 给定 次查询, 每次询问能否从某个区间 中选择两个数使得他们的异或等于 。

输入格式

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

第二行包含 个整数 。

接下来 行，每行包含两个整数 表示询问区间 。

输出格式

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

样例 #1

样例输入 #1

1
2
3
4
5
6
4 4 1
1 2 3 4
1 4
1 2
2 3
3 3

样例输出 #1

1
2
3
4
yes
no
yes
no

提示

【样例说明】

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

【评测用例规模与约定】

对于 的评测用例, ;

对于 的评测用例, ;

对于所有评测用例, ， 。

蓝桥杯 2022 省赛 A 组 D 题。

解法

异或：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
const int N=(1e5)+5;
using namespace std;
int n,m,x;
unordered_map<int,int> mp;//数值，对应位置
int f[N];//对于查询[l,r]，f[r]表示[l,r]要有相配答案，l的最右
int main() {
    scanf("%d%d%d",&n,&m,&x);
    int a;
    for(int i=1;i<=n;i++){
        scanf("%d",&a);
        f[i]=max(f[i-1],mp[a^x]);//找到达到要求的最左边界
        mp[a]=i;
    }
    int l,r;
    while(m--){
        scanf("%d%d",&l,&r);
        if(l<=f[r])
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}

[蓝桥杯 2022 省 A] 爬树的甲壳虫

题目描述

有一只甲壳虫想要爬上一颗高度为 的树，它一开始位于树根, 高度为 ，当它尝试从高度 爬到高度为 的位置时有 的概率会掉回树根, 求它从树根爬到树顶时, 经过的时间的期望值是多少。

输入格式

输入第一行包含一个整数 表示树的高度。

接下来 行每行包含两个整数 , 用一个空格分隔，表示 。

输出格式

输出一行包含一个整数表示答案，答案是一个有理数，请输出答案对质数 取模的结果。其中有理数 对质数 取模的结果是整数 满足 且 。

样例 #1

样例输入 #1

1
2
1
1 2

样例输出 #1

1
2

样例 #2

样例输入 #2

1
2
3
4
3
1 2
3 5
7 11

样例输出 #2

1
623902744

提示

对于 的评测用例, ;

对于 的评测用例, ;

对于所有评测用例, 。

蓝桥杯 2022 省赛 A 组 E 题。

bgm🐌🎵

是🐞不是🐌喂

解法

状态转移

设从高度爬到高度的期望时间是.
从爬到的期望时间当然为从爬到时爬到的期望时间的概率掉回，秒掉下去，时间再爬回，期望：的概率成功向上，期望：
即
转移方程：
求

费马小定理的一种表述：对于任意整数和质数，有

模运算和逆元

在模运算中，使用逆元将除法转换为乘法，避免了直接计算分数。
快速幂模板
乘法逆元模板

逆元的定义：如果存在一个整数 ，使得 ，那么 就是 在模 下的逆元

费马小定理的一种表述：如果是一个质数，且 与 互质，那么：
另一种表述：对于任意整数和质数，有

计算 在模下的值。根据费马小定理得到：

对于模数，它是一个质数，所以可以直接用 来计算。

快速幂函数

函数quick_pow用于计算 。它利用了快速幂算法，时间复杂度为 。
通过不断将指数右移（相当于除以2），并根据当前指数的奇偶性决定是否将当前的乘到结果中。
将分数转换为模运算下的乘法。

总代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using ll=unsigned long long;
const int p=998244353;//取模
using namespace std;
int n;
ll x,y,f;
ll quick_pow(ll a){
    ll res=1;
    ll b=p-2;
    while(b){
        if(b&1){
            res=res*a%p;
        }
        a=a*a%p;
        b>>=1;
    }
    return res;
}
int main() {
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%lld%lld",&x,&y);
        f=((f+1)*y%p)*quick_pow(y-x)%p;
    }
    cout<<f<<endl;
    return 0;
}

时间复杂度
每次计算逆元的时间复杂度为 。
总时间复杂度为 ，其中 n 是树的高度。

[蓝桥杯 2022 省 A] 青蛙过河

题目描述

小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。

河里的石头排成了一条直线，小青蛙每次跳跃必须落在一块石头或者岸上。不过，每块石头有一个高度，每次小青蛙从一块石头起跳，这块石头的高度就会下降 ，当石头的高度下降到 时小青蛙不能再跳到这块石头上（某次跳跃后使石头高度下降到 是允许的)。

小青蛙一共需要去学校上 天课，所以它需要往返 次。当小青蛙具有一个跳跃能力 时，它能跳不超过 的距离。

请问小青蛙的跳跃能力至少是多少才能用这些石头上完 次课。

输入格式

输入的第一行包含两个整数 , 分别表示河的宽度和小青蛙需要去学校的天数。请注意 才是实际过河的次数。

第二行包含 个非负整数 , 其中 表示在河中与 小青蛙的家相距 的地方有一块高度为 的石头， 表示这个位置没有石头。

输出格式

输出一行, 包含一个整数, 表示小青蛙需要的最低跳跃能力。

样例 #1

样例输入 #1

1
2
5 1
1 0 1 0

样例输出 #1

1
4

提示

【样例解释】

由于只有两块高度为 的石头，所以往返只能各用一块。第 块石头和对岸的距离为 ，如果小青蛙的跳跃能力为 则无法满足要求。所以小青蛙最少需要 的跳跃能力。

【评测用例规模与约定】

对于 的评测用例，;

对于 的评测用例，;

对于所有评测用例， 。

蓝桥杯 2022 省赛 A 组 F 题。

bgm🐸🎵

解法

贪心+前缀和
对于每个起点，检查区间 内的石头总高度是否足够支持 次跳跃。
如果某个区间的石头总高度不足，则增加，扩大区间范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
using ll=unsigned long long;
const int N=(1e5)+5;
int n,x;//宽度和小青蛙需要去学校的天数。
ll sum[N];//石头总数前缀和
int main() {
    scanf("%d%d",&n,&x);
    x<<=1;//实际上让青蛙2x次过岸
    int h;//石头高度
    for(int i=1;i<n;i++)
    {
        scanf("%d",&h);
        sum[i]=sum[i-1]+h;//[l,r]区间的石头总高度为sum[r]-sum[l-1]
    }
    int y=1;//跳跃能力
    sum[n]=INT_MAX;//到对岸相当于有无数的石头
    for(int i=0;i<n-y;i++)
        while(sum[i+y]-sum[i]<x)//[i+1,i+y]区间不够2x只青蛙落脚
            y++;
    printf("%d",y);
    return 0;
}

[蓝桥杯 2022 省 A] 最长不下降子序列

题目描述

给定一个长度为 的整数序列：。现在你有一次机会，将其中连续的 个数修改成任意一个相同值。请你计算如何修改可以使修改后的数列的最长不下降子序列最长，请输出这个最长的长度。

最长不下降子序列是指序列中的一个子序列，子序列中的每个数不小于在它之前的数。

输入格式

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

第二行包含 个整数 。

输出格式

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

样例 #1

样例输入 #1

1
2
5 1
1 4 2 8 5

样例输出 #1

1
4

提示

对于 的评测用例, ;

对于 的评测用例, ;

对于 的评测用例, ;

对于所有评测用例, 。

蓝桥杯 2022 省赛 A 组 G 题。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
```

---

# [蓝桥杯 2022 省 A] 扫描游戏

## 题目描述

有一根围绕原点 $O$ 顺时针旋转的棒 $OA$，初始时指向正上方（Y 轴正向）。平面中有若干物件，第 $i$ 个物件的坐标为 $\left(x_{i}, y_{i}\right)$，价值为 $z_{i}$。当棒扫到某个物件时，棒的长度会瞬间增长 $z_{i}$，且物件瞬间消失（棒的顶端恰好碰到物件也视为扫到)，如果此时增长完的棒又额外碰到了其他物件，也按上述方式消去（它和上述那个点视为同时消失）。

如果将物件按照消失的时间排序，则每个物件有一个排名，同时消失的物件排名相同，请输出每个物件的排名，如果物件永远不会消失则输出 $-1$。

## 输入格式

输入第一行包含两个整数 $n$、$L$，用一个空格分隔，分别表示物件数量和棒的初始长度。

接下来 $n$ 行每行包含第三个整数 $x_{i}, y_{i}, z_{i}$。

注意存在 $(x_{i}, y_{i})=(0,0)$ 的情况，这些点视为一开始就立刻被碰到。

## 输出格式

输出一行包含 $n$ 整数，相邻两个整数间用一个空格分隔，依次表示每个物件的排名。

## 样例 #1

### 样例输入 #1

5 2
0 1 1
0 3 2
4 3 5
6 8 1
-51 -33 2

1
2
3

### 样例输出 #1


1 1 3 4 -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

## 提示

对于 $30 \%$ 的评测用例，$1 \leq n \leq 500$ ；

对于 $60 \%$ 的评测用例，$1 \leq n \leq 5000$;

对于所有评测用例，$1 \leq n \leq 2\times10^5,-10^{9} \leq x_{i}, y_{i} \leq 10^{9}, 1 \leq L, z_{i} \leq 10^{9}$ 。 

样蓝桥杯 2022 省赛 A 组 H 题。

## 题解

为什么不试试优先队列呢？
此处建议用斜率代替角度，角度每个网站的数据要求精度不一样。但我过了洛谷和蓝桥杯官网就懒得改了```(*ꈍ◡ꈍ*)```

```cpp
#include <bits/stdc++.h>
using ll = long long;
using ull = unsigned long long;
const int N = (2e5) + 5;
const double pi2 = 2 * M_PI; // 2*圆周率pi
using namespace std;

struct point {
    int id;       // 序号
    int z;        // 碰到增加的值
    ull r;        // 半径的平方
    double angle; // 角度（以从y轴正方向开始的顺时针角度表示）
    bool operator>(const point &other) const {
        return angle > other.angle; // 优先队列按角度排序
    }
} p[N];

int main() {
    int n;//棒的个数
    ull l;//棒的长度
    __int128 l2;//棒的长度的平方，棒的长度的平方。__int128防止超过数据范围
    scanf("%d%lld", &n, &l);
    l2 = l * l;
    ll x, y;
    for (int i = 0; i < n; i++) {
        scanf("%lld%lld%d", &x, &y, &p[i].z);
        p[i].id = i;
        p[i].r = x * x + y * y;//半径的平方
        p[i].angle = atan2(x, y);//算角度。atan2可以处理为0的情况，注意是顺时针从y轴正方向开始
        if (p[i].angle < 0)//把第二、三象限的角度转过来
            p[i].angle = pi2 + p[i].angle;
    }
    sort(p, p + n, [](const point &a, const point &b) -> bool {
        return a.r < b.r;
    });//按半径排序
    priority_queue<point, vector<point>, greater<>> q; // 按角度排序的优先队列
    int pos;
    for (pos = 0; pos < n && p[pos].r <= l2; pos++) {
        q.push(p[pos]);
    }

    int cnt = 1, last_cnt = 1;//排名，并列排名
    int ans[N];//答案
    double rounds = pi2, angle = 0; // rounds 表示本轮结束的角度，angle 保存上一个被扫到的点的角度
    memset(ans, -1, sizeof(ans));//初始化为-1
    const double eps = 1e-11; // 浮点数比较阈值。1e-9官网过不了

    while (!q.empty()) {
        point u = q.top();
        q.pop();
        if (u.angle > rounds + eps) // 如果当前点的角度超过本轮结束的角度
            rounds += pi2;
        if (fabs(u.angle - angle) < eps) {  // 判断两角度是否“相等”，用并列排名
            ans[u.id] = last_cnt;
        } else {
            last_cnt=ans[u.id]=cnt;//更新并列的排名
            angle=u.angle;//角度
        }
        ++cnt;//更新排名

        l += u.z;
        l2 = l * l;
        while (pos < n && p[pos].r <= l2) {
            // 新点的角度转换到绝对角度，先加上当前轮次的偏移量
            p[pos].angle += (rounds - pi2);
            if (p[pos].angle < angle - eps) {
                p[pos].angle += pi2;
            }
            q.push(p[pos]);
            ++pos;
        }
    }
    printf("%d", ans[0]);
    for (int i = 1; i < n; i++)
        printf(" %d", ans[i]);
    return 0;
}

[蓝桥杯 2022 省 A] 数的拆分

题目描述

给定 个正整数 ，分别问每个 能否表示为 的形式，其中 为正整数， 为大于等于 的正整数。

输入格式

输入第一行包含一个整数 表示询问次数。

接下来 行，每行包含一个正整数 。

输出格式

对于每次询问，如果 能够表示为题目描述的形式则输出 yes，否则输出 no。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
7
2
6
12
4
8
24
72

样例输出 #1

1
2
3
4
5
6
7
no
no
no
yes
yes
no
yes

提示

【样例说明】

第 个数分别可以表示为:

【评测用例规模与约定】

对于 的评测用例，;

对于 的评测用例，;

对于 的评测用例，;

对于所有评测用例， 。

蓝桥杯 2022 省赛 A 组 I 题。

解法

设已知即原式范围 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using ll=long long;
const int N=4000;
using namespace std;
int n;
int not_prime[N+4];
vector<int> primes;
inline void init_primes(){
    for(int i=2;i<=N;i++){
        if(!not_prime[i]){
            primes.push_back(i);
        }
        for(int j:primes){
            if(i*j>N)
                break;
            not_prime[i*j]=true;
            if(i%j==0)
                break;
        }
    }
}
inline bool check(ll x){
    ll y=pow(x,0.5);
    if(y*y==x)
        return true;
    y=pow(x,1.0/3);
    if(y*y*y==x||(y+1)*(y+1)*(y+1)==x)//?
        return true;
    return false;
}
int main() {
    init_primes();
    int t;
    ll n;
    scanf("%d",&t);
    while(t--){
        scanf("%lld",&n);
        if(check(n)){
            printf("yes\n");
            continue;
        }
        bool flag=true;
        for(int i:primes){
            int cnt=0;
            while(n%i==0){
                n/=i;
                cnt++;
            }
            if(cnt==1){
                flag=false;
                break;
            }
        }
        if(flag&&check(n)){
            printf("yes\n");
        }
        else{
            printf("no\n");
        }

    }
    return 0;
}

[蓝桥杯 2022 省 A] 推导部分和

题目描述

对于一个长度为 的整数数列 ，小蓝想知道下标 到 的部分和 是多少?

然而，小蓝并不知道数列中每个数的值是多少，他只知道它的 个部分和的值。其中第 个部分和是下标 到 的部分和 , 值是 。

输入格式

第一行包含 3 个整数 、 和 。分别代表数组长度、已知的部分和数量 和询问的部分和数量。

接下来 行，每行包含 个整数 。

接下来 行，每行包含 个整数 和 ，代表一个小蓝想知道的部分和。

输出格式

对于每个询问, 输出一行包含一个整数表示答案。如果答案无法确定, 输出 UNKNOWN。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
5 3 3
1 5 15
4 5 9
2 3 5
1 5
1 3
1 2

样例输出 #1

1
2
3
15
6
UNKNOWN

提示

对于 的评测用例, 。

对于 的评测用例, 。

对于 的评测用例, 。

对于 的评测用例, 。

对于 的评测用例, 。

对于所有评测用例, , 。数据保证没有矛盾。

蓝桥杯 2022 省赛 A 组 J 题。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
vector<int> pa;
vector<ll> sum;

int find(int x) {
    if (x != pa[x]) {
        int root = find(pa[x]);
        sum[x] += sum[pa[x]];
        pa[x] = root;
    }
    return pa[x];
}

int main() {
    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);

    pa.resize(n + 1);
    sum.resize(n + 1, 0);
    iota(pa.begin(), pa.end(), 0);
    int l, r;
    ll s;
    while (m--) {
        scanf("%d%d%lld", &l, &r, &s);
        int root_l = find(l - 1);
        int root_r = find(r);
        if (root_l != root_r) {
            pa[root_r] = root_l;
            sum[root_r] = s + sum[l - 1] - sum[r];
        }
    }
    while (q--) {
        scanf("%d%d", &l, &r);
        if (find(l - 1) == find(r)) {
            printf("%lld\n", sum[r] - sum[l - 1]);
        } else {
            printf("UNKNOWN\n");
        }
    }
    return 0;
}