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

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

好几道题还没做。
算了，寒假里做几道放几道呗

[蓝桥杯 2023 省 A] 填空问题

题目描述

A. 幸运数

小蓝认为如果一个数含有偶数个数位，并且前面一半的数位之和等于后面一半的数位之和，则这个数是他的幸运数字。例如 是一个幸运数字，因为它有 个数位，并且 。现在请你帮他计算从 至 之间共有多少个不同的幸运数字。

B. 有奖问答

小蓝正在参与一个现场问答的节目。活动中一共有 道题目，每题只有答对和答错两种情况，每答对一题得 分，答错一题分数归零。

小蓝可以在任意时刻结束答题并获得目前分数对应的奖项，之后不能再答任何题目。最高奖项需要 分，所以到达 分时小蓝会直接停止答题。

已知小蓝最终实际获得了 分对应的奖项，请问小蓝所有可能的答题情况有多少种？

提示

第十四届蓝桥杯大赛软件赛省赛 C/C++ 大学 A 组 A-B

解法

填空题，暴！

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
long long ans1,ans2;//4430091，8335366
// 11~99999999
void solve1(){
    int cnt[40][5]={0};//和为几（1~36），几位数（1~4）
    for(int i=1;i<=9999;i++){
        int w=0,s=0,a=i;
        while(a){
            w++;
            s+=a%10;
            a/=10;
        }
        cnt[s][w]++;
    }
    for(int i=1;i<=36;i++){
        for(int j=1;j<=4;j++){
            int s=0;
            for(int k=1;k<=j;k++){
                s+=cnt[i][k];
            }
            ans1+=cnt[i][j]*s;
        }
    }
}
//答对，答错或者结束比赛
//300题拿了7分，答对1题加10分，答错分数归零。其中分数不可能>=100
void dfs(int t,int s){//题号，分数
    if(s==100)//到达100分时小蓝会直接停止答题
        return;
    if(s==70){
        ans2++;}
    if(t==31)//比赛结束
        return;
    dfs(t+1,s+10);//答对+1
    dfs(t+1,0);//答错分数归0
}
void solve2(){
    dfs(1,0);
}

[蓝桥杯 2023 省 A] 平方差

题目描述

给定 ，问 中有多少个数 满足存在整数 使得 。

输入格式

输入一行包含两个整数 ，用一个空格分隔。

输出格式

输出一行包含一个整数满足题目给定条件的 的数量。

样例 #1

样例输入 #1

1
1 5

样例输出 #1

1
4

提示

【样例说明】

【评测用例规模与约定】

对于 的评测用例，；

对于所有评测用例，。

第十四届蓝桥杯大赛软件赛省赛 C/C++ 大学 A 组 C

解法

$令奇数和为奇数偶数和为偶数或$

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;
signed main()
{
    int l, r;
    cin >> l >> r;
    cout << (r >> 1) + (r & 1) - (l >> 1) + (r >> 2) - (l >> 2) + !(l & 3) << endl;
    return 0;
}

[蓝桥杯 2023 省 A] 更小的数

题目描述

image

小蓝有一个长度均为 且仅由数字字符 组成的字符串，下标从 到 ，你可以将其视作是一个具有 位的十进制数字 ，小蓝可以从 中选出一段连续的子串并将子串进行反转，最多反转一次。小蓝想要将选出的子串进行反转后再放入原位置处得到的新的数字 满足条件 ，请你帮他计算下一共有多少种不同的子串选择方案，只要两个子串在 中的位置不完全相同我们就视作是不同的方案。

注意，我们允许前导零的存在，即数字的最高位可以是 ，这是合法的。

输入格式

输入一行包含一个长度为 的字符串表示 （仅包含数字字符 ），从左至右下标依次为 。

输出格式

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

样例 #1

样例输入 #1

1
210102

样例输出 #1

1
8

提示

【样例说明】

一共有 种不同的方案：

  1. 所选择的子串下标为 ，反转后的 ；
  2. 所选择的子串下标为 ，反转后的 ；
  3. 所选择的子串下标为 ，反转后的 ；
  4. 所选择的子串下标为 ，反转后的 ；
  5. 所选择的子串下标为 ，反转后的 ；
  6. 所选择的子串下标为 ，反转后的 ；
  7. 所选择的子串下标为 ，反转后的 ；
  8. 所选择的子串下标为 ，反转后的 。

【评测用例规模与约定】

对于 的评测用例，；

对于 的评测用例，；

对于所有评测用例，。

解法

1
2
3
4
5
6
对于区间[l,r]
if l!=r:
	if num[l]>num[r]:
		可以翻转
elif [l+1,r-1]in [l,r] and [_l,_r]可以翻转:
	可以翻转

动态规划，根据对称性，优化成一维数组

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
#include <bits/stdc++.h>
using namespace std;
#define N 5005
char num[N];
int n;
long long res;
bool f[N * 2];
signed main()
{
    scanf("%s", num);
    n = strlen(num);
    for (register int k = 1; k < n; k++)
    {
        for (register int i = n - k - 1; i >= 0; i--)//正着也一样
        {
            int j = i + k;
            if (num[i] > num[j])//可以翻转
            {
                res++;
                f[i + j] = true;
            }
            else if (num[i] == num[j])//看区间[i+1,j-1]是否可以翻转
            {
                if (f[i + j])
                    res++;
            }
            else//不可以翻转
            {
                f[i+j]=false;
            }
        }
    }
    printf("%lld\n", res);
    return 0;
}

[蓝桥杯 2023 省 A] 颜色平衡树

题目描述

给定一棵树，结点由 至 编号，其中结点 是树根。树的每个点有一个颜色 。

如果一棵树中存在的每种颜色的结点个数都相同，则我们称它是一棵颜色平衡树。

求出这棵树中有多少个子树是颜色平衡树。

输入格式

输入的第一行包含一个整数 ，表示树的结点数。

接下来 行，每行包含两个整数 ，用一个空格分隔，表示第 个结点的颜色和父亲结点编号。

特别地，输入数据保证 为 ，也即 号点没有父亲结点。保证输入数据是一棵树。

输出格式

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

样例 #1

样例输入 #1

1
2
3
4
5
6
7
6
2 0
2 1
1 2
3 3
3 4
1 4

样例输出 #1

1
4

提示

【样例说明】

编号为 的 个结点对应的子树为颜色平衡树。

【评测用例规模与约定】

对于 的评测用例，，；

对于 的评测用例，，；

对于所有评测用例，，，。

解法

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
```

# [蓝桥杯 2023 省 A] 买瓜

## 题目描述

小蓝正在一个瓜摊上买瓜。瓜摊上共有 $n$ 个瓜，每个瓜的重量为 $A_i$。小蓝刀功了得，他可以把任何瓜劈成完全等重的两份，不过每个瓜只能劈一刀。

小蓝希望买到的瓜的重量的和恰好为 $m$。

请问小蓝至少要劈多少个瓜才能买到重量恰好为 $m$ 的瓜。如果无论怎样小蓝都无法得到总重恰好为 $m$ 的瓜，请输出 $-1$。

## 输入格式

输入的第一行包含两个整数 $n,m$，用一个空格分隔，分别表示瓜的个数和小蓝想买到的瓜的总重量。

第二行包含 $n$ 个整数 $A_i$，相邻整数之间使用一个空格分隔，分别表示每个瓜的重量。

## 输出格式

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

## 样例 #1

### 样例输入 #1

3 10
1 3 13

1
2
3

### 样例输出 #1


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
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

## 提示

### 【评测用例规模与约定】

对于 $20 \%$ 的评测用例，$n \leq 10$;

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

对于所有评测用例，$1 \leq n \leq 30$，$1 \leq A_i \leq 10^9$，$1 \leq m \leq 10^9$。

## 前情提要🍉(bushi)

<iframe src="https://player.bilibili.com/player.html?aid=448136466&bvid=BV14j41117D6&cid=1259813341&p=1" scrolling="no" border="0" frameborder="no" framespacing="0" allowfullscreen="true" style="position: absolute; width: 1000px; left: 0; top: 0;"> </iframe>

## 解法
（瞅了一眼标签，折半搜索？跟生瓜蛋子一样不熟）
西瓜对半切/不切，不妨乘二，当作一个西瓜/两个西瓜来做
先贪心排序，优先找大瓜。
然后深度优先搜索，根据质量上下超限（小于要求质量用后缀和判断）、劈瓜数已大于当前最小答案来剪枝。
```cpp
#include<bits/stdc++.h>
using ll=long long;
const int N=32;
using namespace std;
int n,mid,m;//西瓜总数量，一半数量，要求总质量
int ans=INT_MAX;//答案
int a[N];//有一个人前来买瓜
ll sum[N];//后缀和,用来剪枝
void dfs(int i,int num,int weight){//到哪个瓜了，劈了多少瓜，买了几斤瓜
    if(weight>=m){
        if(weight==m)
            ans=min(ans,num);
        return;
    }
    if(i==n||num>=ans||weight+sum[i]<m)//超总数的递归出口，超过最小劈瓜数递归，质量不足以达到要求数剪枝
        return;
    dfs(i+1,num,weight+(a[i]<<1));//卖你生瓜蛋子
    dfs(i+1,num+1,weight+a[i]);//你**劈我瓜是吧！
    dfs(i+1,num,weight);//你要不要吧
}
int main() {
    scanf("%d%d",&n,&m);
    mid=n/2;
    m*=2;
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    sort(a,a+n,greater<>());//从大到小贪心
    for(int i=n-1;i>=0;i--){
        sum[i]=sum[i+1]+(a[i]<<1);//求后缀和
    }
    dfs(0,0,0);
    if(ans==INT_MAX)
        ans=-1;
    printf("%d\n",ans);
    return 0;
}

[蓝桥杯 2023 省 A] 网络稳定性

题目描述

有一个局域网，由 个设备和 条物理连接组成，第 条连接的稳定性为 。

对于从设备 到设备 的一条经过了若干个物理连接的路径，我们记这条路径的稳定性为其经过所有连接中稳定性最低的那个。

我们记设备 到设备 之间通信的稳定性为 至 的所有可行路径的稳定性中最高的那一条。

给定局域网中的设备的物理连接情况，求出若干组设备 和 之间的通信稳定性。如果两台设备之间不存在任何路径，请输出 。

输入格式

输入的第一行包含三个整数 ，分别表示设备数、物理连接数和询问数。

接下来 行，每行包含三个整数 ，分别表示 和 之间有一条稳定性为 的物理连接。

接下来 行，每行包含两个整数 ，表示查询 和 之间的通信稳定性。

输出格式

输出 行，每行包含一个整数依次表示每个询问的答案。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
5 4 3
1 2 5
2 3 6
3 4 1
1 4 3
1 5
2 4
1 3

样例输出 #1

1
2
3
-1
3
5

提示

【评测用例规模与约定】

对于 的评测用例，，；

对于 的评测用例，，；

对于所有评测用例，，，，，，。

解法

[蓝桥杯 2023 省 A] 异或和之和

题目描述

给定一个数组 ，分别求其每个子段的异或和，并求出它们的和。或者说，对于每组满足 的 ，求出数组中第 至第 个元素的异或和。然后输出每组 得到的结果加起来的值。

输入格式

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

第二行包含 个整数 ，相邻整数之间使用一个空格分隔。

输出格式

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

样例 #1

样例输入 #1

1
2
5
1 2 3 4 5

样例输出 #1

1
39

提示

【评测用例规模与约定】

对于 的评测用例，；

对于 的评测用例，;

对于所有评测用例，，。

解法

异或的性质

异或和异或和
（没什么，复习一下）

设序列为，从到的异或和为， 从到的异或前缀和为,则

即对~个前缀和，两两异或的和。
按二进制位数相加
```cpp

include

using namespace std;
using ll=long long;
const int N=(1e5)+5;
int n;
int f[N];
ll res=0ll;
int main() {
int a;
scanf(“%d”,&n);
for(int i=1;i<=n;i++){
scanf(“%d”,&a);
f[i]=f[i-1]^a;
}
int bei=1;//位权
for(int i=0;i<=20;i++){//20位二进制
int numof1=0,numof0=1;
ll sum=0;
for(int j=1;j<=n;j++){
if(f[j]&1){//最低一位1^0=1
sum+=numof0;
numof1++;
}else{//最低一位0^1=1
sum+=numof1;
numof0++;
}
f[j]>>=1;//下一位
}
res+=sum*bei;
bei<<=1;//位权翻倍
}
cout<<res<<endl;
return 0;
}
```..