2023年第十四届蓝桥杯省赛C++ 大学生A组

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

 基本没有算法基础，第一次参加蓝桥杯，简单复盘一下。

目录

试题 A 幸运数

分析

枚举 O(K)

试题 B 有奖问答

分析

DFS 

试题 C 平方差

分析

枚举O（n^3）

因数分解 O(n*sqrt(n)) 

 奇偶判断 O(n) 

试题D 更小的数

分析 

动态规划DP O(n^2)  

试题E 颜色平衡树

分析

试题 F 买瓜

分析

试题 I 网络稳定性

分析

并查集+dijkstra算法

---

试题 A 幸运数

分析：

1~10e8，不用考虑奇数位跳过的问题，直接枚举。

枚举 O(K)

#include<iostream>using namespace std;int ans = 0;int main(){int a[9];for (int i = 10; i < 100000000; i++) {int temp = i;int index = 0;while (temp) {index++;a[index] = temp % 10;temp /= 10;}//奇数数位直接跳过if (index & 1) continue;int sum1 = 0, sum2 = 0;for (int i = 1; i <= index / 2; i++) {sum1 += a[i];sum2 += a[index - i + 1];}if (sum1 == sum2) ans++;}cout << ans << endl;return 0;}

答案：4430091

试题 B 有奖问答

分析：

第一反应肯定是dfs，2^30的规模，直接暴搜。

DFS 

#include<iostream>using namespace std;int ans = 0;void dfs(int k,int r){if (r == 70) ans++;if (k == 30 || r == 100) return;dfs(k + 1, r + 10);dfs(k + 1, 0);}int main(){dfs(0,0);cout << ans << endl;return 0;}

答案：8335366

试题 C 平方差

分析：

第一反应 x=y^2-z^2 可以转换成 x= (y+z)(y-z)，毫无疑问，奇数一定可以写作平方差的形式。那就只需要考虑偶数的情况，想半天没想好边界，最后还是选择了枚举，即对x，枚举 a 存在 b^2 == x+ a^2。

枚举O（n^3）

#include<iostream>#include<cmath>#define ll long long using namespace std;ll l, r;ll ans = 0;int main(){cin >> l >> r;for (ll i = l; i <= r; i++) {//奇数if (i & 1) ans++;//偶数else {bool flag = false;for (ll j = 0; j <= i; j++) {for (ll k = j + 1; k <= i; k++) {if (pow(k, 2) == pow(j, 2) + i) {flag = true;break;}}if (flag) {ans++;break;}}}}cout << ans << endl;return 0;}

因数分解 O(n*sqrt(n)) 

同理有  x=y^2-z^2 ->  x=(y+z)(y-z)

令 

a=(y+z)  

b=(y-z)

a>b;

x=a*b;

y=(a+b)/2;

z=(a-b)/2;

(这里是用到了初中知识吗，但有点三角函数的感觉，还想了半天，确实让我卡在这里了，汗)

#include<iostream>#include<cmath>#define ll long long using namespace std;ll l, r;ll ans = 0;int main(){cin >> l >> r;for (ll i = l; i <= r; i++) {//奇数if (i & 1) ans++;//偶数else {int flag = false;//因数分解for (ll j = 2; j <= sqrt(i); j++) {if (i%j == 0) {ll a = j;ll b = i / j;ll temp = a + b;if (!(temp & 1)) flag = true;}if (flag) {ans++;break;}}}}cout << ans << endl;return 0;}

 奇偶判断 O(n) 

在上述的递推式的基础上，不难发现，对一个偶数，只能存在两个偶数因子，若存在一个因子为4，则一定可以写作  a=2  ， b=2z-2  的形式；

#include<iostream>#include<cmath>#define ll long long using namespace std;ll l, r;ll ans = 0;int main(){cin >> l >> r;for (ll i = l; i <= r; i++) {//奇数if (i & 1) ans++;//偶数else {if (i % 4 == 0) ans++;}}cout << ans << endl;return 0;}

参考链接：(40条消息) 一道有趣的算法题： 将正整数表示成为两个正整数的平方差_卷儿~的博客-CSDN博客

试题D 更小的数

题目描述

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

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

输入格式

输入一行包含一个长度为 n 的字符串表示 num（仅包含数字字符 0 ∼ 9），

从左至右下标依次为 0 ∼ n − 1。

输出格式

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

样例输入

复制

210102

样例输出

复制

8

提示

一共有 8 种不同的方案：

1）所选择的子串下标为 0 ∼ 1 ，反转后的 numnew = 120102 < 210102 ；

2）所选择的子串下标为 0 ∼ 2 ，反转后的 numnew = 012102 < 210102 ；

3）所选择的子串下标为 0 ∼ 3 ，反转后的 numnew = 101202 < 210102 ；

4）所选择的子串下标为 0 ∼ 4 ，反转后的 numnew = 010122 < 210102 ；

5）所选择的子串下标为 0 ∼ 5 ，反转后的 numnew = 201012 < 210102 ；

6）所选择的子串下标为 1 ∼ 2 ，反转后的 numnew = 201102 < 210102 ；

7）所选择的子串下标为 1 ∼ 4 ，反转后的 numnew = 201012 < 210102 ；

8）所选择的子串下标为 3 ∼ 4 ，反转后的 numnew = 210012 < 210102 ；

对于 20% 的评测用例，1 ≤ n ≤ 100 ；

对于 40% 的评测用例，1 ≤ n ≤ 1000 ；

对于所有评测用例，1 ≤ n ≤ 5000 。

分析： 

第一反应肯定是DP，无奈做得题还是太少，经验不够，考场上第一直觉下的遍历方式回来演算一下发现还是出了一些问题。

DP题主要还是要考虑到递推的顺序以及状态转移的关系以及递推的顺序，这里懊悔到把最基础的数学知识给忽略了，简单的把算法训练当作了数学归纳和肌肉训练？

动态规划DP O(n^2)  

状态转移方程

状态转移方程不难理解，对一个子串是否可以翻转，只需要考虑最外层的字符即可。

a[ i ] > a [ j ]  , DP[ i ] [ j ] = 1 ;

a[ i ] < a[ j ]  , DP[ i ] [ j ]  = 0 ;

a[ i ] =a[ j ]  ,  DP[ i ] [ j ] = DP [ i+1 ] [ j-1 ];

递推顺序

再就是根据状态转移方程，来设置递推顺序。

这里以画图的形式，来推理递推顺序

首先建立设定一个二维有向图，L为左边界，R为右边界，i，j 分别为左右变量。

j > i ，所以左下部分为无关变量

由状态转移方程可以得知

 拓展到整体，原图可化作

递推顺序显而易见了，即由i=j -> i+n=j；

#include<iostream>#include<string>#include<cstring>#define ll long longusing namespace std;string n;int a[5001];int dp[5001][5001];int vis[5001][5001];ll ans = 0;bool check(int l, int r){if (a[l] > a[r]) return true;if (a[l] < a[r]) return false;if (a[l] == a[r]) {if (r - l <= 2) return false;else return dp[l + 1][r - 1];}}int main(){cin >> n;for (int i = 1; i <= n.size(); i++) {int temp = n[i - 1] - '0';a[i] = temp;}memset(dp, 0, sizeof(dp));for (int k = 1; k <= n.size(); k++) {for (int i = 1,j; i <= n.size(); i++) {j = i + k;if (j > n.size()) break;if (check(i, j)) {dp[i][j] = 1;ans++;}}}cout << ans << endl;return 0;}

试题E 颜色平衡树

题目描述

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

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

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

输入格式

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

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

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

输出格式

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

样例输入

复制

62 02 11 23 33 41 4

样例输出

复制

4

提示

编号为 1, 3, 5, 6 的 4 个结点对应的子树为颜色平衡树。

对于 30% 的评测用例，n ≤ 200，Ci ≤ 200 ；

对于 60% 的评测用例，n ≤ 5000，Ci ≤ 5000 ；

对于所有评测用例，1 ≤ n ≤ 200000，1 ≤ Ci ≤ 200000，0 ≤ Fi < i 。

分析：

第一反应肯定是dfs暴搜，结果还是不对，没有思路，待解。

试题 F 买瓜

分析：

二分，dfs，多数和，想到的思路就这些了，待解。

试题 I 网络稳定性

【问题描述】

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

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

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

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

【输入格式】

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

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

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

【输出格式】

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

【样例输入】

5 4 3

1 2 5 2 3 6

试题G: 网络稳定性

3 4 1

1 4 3

1 5

1 4

1 3

【样例输出】

-1

3

5

【评测用例规模与约定】

对于 30% 的评测用例，n,q ≤ 500，m ≤ 1000 ；对于 60% 的评测用例，n,q ≤ 5000，m ≤ 10000 ；对于所有评测用例，2 ≤ n,q ≤ 105，1 ≤ m ≤ 3×105，1 ≤ ui,vi, xi,yi ≤ n， 1 ≤ wi ≤ 106，ui , vi，xi , yi 。

分析：

第一反应是并查集和dijkstra算法，并查集判断是否存在链路，dijkstra算法求出最稳定链路。但空间规模上只能满足60%测试用例。

并查集+dijkstra算法

#include<iostream>#include<cstring>#include<algorithm>using namespace std;int n, m, q;int f[100001];int vis[100001];int dis[100001];int map[10001][10001];//并查集判断是否存在链路int find(int x){return x == f[x] ? x : find(f[x]);}int dfs(int u, int v){//初始化链路状态memset(dis, 0, sizeof(dis));for (int i = 1; i <= n; i++) {dis[i] = map[u][i];vis[i] = 0;}dis[u] = INT_MAX;vis[u] = 1;while (!vis[v]) {int maxn = 0;int v0;//找到当前u->vi稳定性最高的节点作为v0for (int i = 1; i <= n; i++) {if (!vis[i]) {if (dis[i] > maxn) {v0 = i;maxn = dis[i];}}}//更新节点状态vis[v0] = 1;//更新链路状态for (int i = 1; i <= n; i++) {if (!vis[i]) {//判断v0到vi节点是否为最稳定链路int doc = min(dis[v0], map[v0][i]);if (doc > dis[i]) {dis[i] = doc;}}}}return dis[v];}int main(){cin >> n >> m >> q;memset(map, 0, sizeof(map));//构建有向图for (int i = 1; i <= m; i++) {int u, v, w;cin >> u >> v >> w;f[v] = find(u);map[u][v] = w;map[v][u] = w;}for (int i = 1; i <= q; i++) {int u, v;cin >> u >> v;if (f[u] != f[v]) {cout << -1 << endl;continue;}//输出u->v，稳定性最高链路cout << dfs(u, v) << endl;}}

敲了一整天，剩下的题目考场上都没写，有时间再看。

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

本文链接：https://www.kjpai.cn/gushi/2024-04-19/160400.html，文章来源：网络cs，作者：胡椒，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！