©2020-2024 ioDraw All rights reserved
<>第十三届蓝桥杯模拟赛（第二期）试题与题解
<>1、试题A
【问题描述】
小蓝的IP地址为 192.168. * .21，其中 * 是一个数字，请问这个数字最大可能是多少 ?
<>题解
IP地址由四个字节组成，每个字节是一个 8 比特位的无符号数，最大为 255 所以答案是 255
<>2、试题B
【问题描述】
如果一个整数 g 能同时整除整数 A 和 B，则称 g 是 A 和 B 的公约数。例如：43 是 86 和 2021 的公约数。
请问在 1（含） 到 2021（含） 中，有多少个数与 2021 存在大于 1 的公约数。请注意 2021 和 2021 有大于 1
的公约数，因此在计算的时候要算一个。
<>题解：枚举
//答案 89 #include <iostream> using namespace std; int gcd(int a, int b) { return
(a % b == 0) ? b : gcd(b, a % b); } int main() { int ans = 0; for (int i = 1; i
<= 2021; i++) { if (gcd(2021, i) > 1) ans++; } cout << ans << endl; return 0; }
<>3、试题C
【问题描述】
2021 是一个非常特殊的数，它可以表示成两个非负整数的平方差，2021 = 45 * 45 - 2 * 2。
2025 也是同样特殊的数，它可以表示成 2025 = 45 * 45 - 0 * 0。
请问，在 1 到 2021 中有多少个这样的数？
请注意，有的数有多种表示方法，例如 9 = 3 * 3 - 0 * 0 = 5 * 5 - 4 * 4，在算答案时只算一次
<>方法一：枚举
假设有: x = a^2 - b^2 = (a + b) * (a - b)
可知 (a + b) 和 (a - b) 是 x 的一对约数
反过来，要判断 x 是否符合条件
可以找出 x 的每一对约数，判断两约数是否能变成 (a + b) * (a - b)的形式，并且 a 和 b 都是正整数
因为 (a + b) + (a - b) = 2a (a + b) - (a - b) = 2b
所以判断这一对约数的和与差是否为偶数即可
若两数之和为偶数，那么两数之差也为偶数，所以两者判断其一即可
//答案 1516 #include <bits/stdc++.h> using namespace std; bool check(int x) { int
n= sqrt(x); for (int i = 1; i <= n; i++) { if (x % i == 0 && (i + x / i) % 2 ==
0) { return true;; } } return false; } int main() { int ans = 0; for (int i = 1;
i<= 2021; i++) { ans += check(i); } cout << ans << endl; return 0; }
<>方法二：枚举因数
方法一是为判断某个数是否是特别的数，方法二是枚举出特别的数，判断是否在 1 ~ 2021 范围内
令 i 代替 (a + n)，j 代替 (a - b) 枚举，若 (i + j) 是偶数并且 (i * j) 在范围内就打上标记，最后查有多少个数被标记
//答案 1516 #include <bits/stdc++.h> using namespace std; int main() { int a[2022
] = {0}; for (int i = 1; i <= 2021; i++) { for (int j = 1; j <= i; j++) { if ((i
+ j) % 2 == 0 && i * j <= 2021) { a[i * j] = 1; } } } int ans = 0; for (int i =
1; i <= 2021; i++) { ans += a[i]; } cout << ans << endl; return 0; }
<>4、试题D
【问题描述】
小蓝要用01串来表达一段文字，这段文字包含 a, b, c, d, e, f 共 6 个字母，每个字母出现的次数依次为：a 出现 10 次，b 出现
20 次，c 出现 3 次，d 出现 4 次，e 出现 18 次，f 出现 50 次。
小蓝准备分别对每个字母使用确定的 01 串来表示，不同字母的 01 串长度可以不相同。
在表示文字时，将每个字母对应的 01 串直接连接起来组成最终的 01 串。为了能够正常还原出文字，小蓝的编码必须是前缀码，即任何一个字符对应的 01
串都不能是另一个字符对应的 01 串的前缀。
例如，以下是一个有效的编码：
a: 000
b: 111
c: 01
d: 001
e: 110
f : 100
其中 c 的长度为 2，其它字母的编码长度为 3，这种方式表示这段文字需要的总长度为：103 + 203 + 32 + 43 + 183 + 503 =
312。
上面的编码显然不是最优的，将上面的 f 的编码改为 10，仍然满足条件，但是总长度为 262，要短 50。
要想编码后的总长度尽量小，应当让出现次数多的字符对应的编码短，出现次数少的字符对应的编码长。
请问，在最优情况下，编码后的总长度最少是多少？
<>题解：哈夫曼编码
将每个字符出现的次数作为权值，每次取出最小的两个权值，作为二叉树的左右节点，再将权值之和作为父节点，放回队列中，循环此过程构建哈夫曼树
自二叉树根节点开始，向左为 0，向右为 1，得出每个字符的编码，结果如下：
左右子节点的位置不同，会使编码结果不同，但位数相同 a: 1101(4位) b: 10(2位) c: 11000(5位) d: 11001(5位) e:
111(3位) f: 0(1位) 所以答案为： 4*10 + 2*20 + 5*3 + 5*4 + 3*18 + 1*50 = 219
<>5、试题E
【问题描述】
下面的矩阵中包含 ABCDEF 六种字符，请问出现最多的字符出现了几次？
FFEEFEAAECFFBDBFBCDA DACDEEDCCFFAFADEFBBA FDCDDCDBFEFCEDDBFDBE
EFCAAEECEECDCDECADDC DFAEACECFEADCBFECADF DFBAAADCFAFFCEADFDDA
EAFAFFDEFECEDEEEDFBD BFDDFFBCFACECEDCAFAF EFAFCDBDCCBCCEADADAE
BAFBACACBFCBABFDAFBE FCFDCFBCEDCEAFBCDBDD BDEFCAAAACCFFCBBAAEE
CFEFCFDEEDCACDACECFF BAAAFACDBFFAEFFCCCDB FADDDBEBCBEEDDECFAFF
CDEAFBCBBCBAEDFDBEBB BBABBFDECBCEFAABCBCF FBDBACCFFABEAEBEACBB
DCBCCFADDCACFDEDECCC BFAFCBFECAACAFBCFBAF
<>题解：哈希表
用数组代替哈希映射即可
//用题目中的矩阵作为输入可得出答案 //答案 78 #include <iostream> using namespace std; int mp[200]
, idx = 0; string str; int main() { for (int i = 0; i < 20; i++) { cin >> str;
for (int j = 0; j < str.length(); j++) { mp[str[j]]++; } } for (int i = 0; i <
200; i++) { if (mp[i]) { cout << char(i) << " " << mp[i] << endl; if (mp[i] > mp
[idx]) idx = i; } } cout << "ans = " << mp[idx] << endl; return 0; }
<>6、试题F
【问题描述】
小蓝要到店里买铅笔。
铅笔必须一整盒一整盒买，一整盒 12 支，价格 p 元。
小蓝至少要买 t 支铅笔，请问他最少花多少钱？
【输入格式】
输入一行包含两个整数 p、t，用一个空格分隔。
【输出格式】
输出一行包含—个整数，表示答案。
【样例输入】
5 30
【样例输出】
15
【评测用例规模与约定】
对于所有评测用例， 1 <= p <= 100，1 <= v <= 10000。
<>题解
t / 12 表示盒数，若 t % 12 不为 0 就多买一盒
#include <iostream> using namespace std; int main() { int p, t; cin >> p >> t;
int k = (t / 12) + bool(t % 12); cout << k * p << endl; return 0; }
<>7、试题G
【问题描述】
给定一个三角形的三条边的长度 a, b, c，请问这个三角形是不是一个直角三角形。
【输入格式】
输入一行包含三个整数 a, b, c，表示三角形三边的长度，相邻整数之间用一个空格分隔。
【输出格式】
如果是直角三角形，输出 “YES”（全大写），否则输出 “NO”（全大写）。
【样例输入】
3 4 5
【样例输出】
YES
【样例输入】
4 5 4
【样例输出】
NO
【评测用例规模与约定】
对于50%的评测用例， 1 <= a, b, c <= 1000。
<>题解
排序，最小的两个数的平方和等于最大数的平方，就是直角三角形
#include <iostream> #include <algorithm> using namespace std; int a[3]; bool
check() { return a[0] * a[0] + a[1] * a[1] == a[2] * a[2]; } int main() { for (
int i = 0; i < 3; i++) { cin >> a[i]; } sort(a, a + 3); if (check()) cout <<
"YES" << endl; else cout << "NO" << endl; return 0; }
<>8、试题H
【问题描述】
n 个小朋友正在做一个游戏，每个人要分享一个自己的小秘密。
每个小朋友都有一个 1 到 n 的编号，编号不重复。
为了让这个游戏更有趣，老师给每个小朋友发了一张卡片，上面有一个 1 到 n 的数字，每个数字正好出现一次。
每个小朋友都将自己的秘密写在纸上，然后根据老师发的卡片上的数字将秘密传递给对应编号的小朋友。如果老师发给自己的数字正好是自己的编号，这个秘密就留在自己手里。
小朋友们拿到其他人的秘密后会记下这个秘密，老师会再指挥所有小朋友将手中的秘密继续传递，仍然根据老师发的卡片上的数字将秘密传递给对应编号的小朋友。
这样不断重复 n 次。
现在，每个小朋友都记下了很多个秘密。
老师现在想找一些小朋友，能说出所有秘密，请问老师最少要找几个小朋友？
【输入格式】
输入的第一行包含一个整数 n。
第二行包含 n 个整数 a[1], a[2], …, a[n]，相邻的整数间用空格分隔，分别表示编号 1 到 n 的小朋友收到的数字。
【输出格式】
输出一行包含一个整数，表示答案。
【样例输入】
6
2 1 3 5 6 4
【样例输出】
8
【样例说明】
最终小朋友 1, 2 互相知道了对方的秘密，小朋友 3 只知道自己的秘密，小朋友 4, 5, 6 互相知道了对方的秘密。
至少要找 3 个小朋友才能说出所有秘密。
【评测用例规模与约定】
对于 30% 的评测用例，2 <= n <= 30。
对于 60% 的评测用例，2 <= n <= 1000。
对于所有评测用例，2 <= n <= 100000。
<>方法一：广搜
由于卡片不会重复，所以答案就是环的个数
因为经过 n 轮循环后，环中的每个小朋友都知道环中所有人的秘密，所以从每个环中找出一人即可
#include <iostream> using namespace std; const int MAXN = 100005; int n, tmp,
ans= 0;; int a[MAXN]; int main() { // freopen("input.txt", "r", stdin); cin >> n
; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i <= n; i++) {
if (a[i] != 0) ans++; int idx = i; while (a[idx]) { tmp = a[idx]; a[idx] = 0;
idx= tmp; } } cout << ans << endl; return 0; }
<>方法二：并查集
本该是道并查集的题，但是数据范围太大，时间复杂度不稳定，极限数据时递归会爆栈，只能过 60% 的样例
#include <iostream> using namespace std; const int MAXN = 100005; int n, tmp,
ans= 0;; int a[MAXN]; int findf(int idx) { if (a[idx] == 0 || a[idx] == idx)
return idx; a[idx] = findf(a[idx]); return a[idx]; } int main() { //
freopen("input.txt", "r", stdin); cin >> n; for (int i = 1; i <= n; i++) { cin
>> tmp; a[i] = findf(tmp); } for (int i = 1; i <= n; i++) { if (a[i] == i) ans++
; } cout << ans << endl; return 0; }
<>9、试题 I
【问题描述】
一个 1 到 n 的排列被称为半递增序列，是指排列中的奇数位置上的值单调递增，偶数位置上的值也单调递增。
例如：(1, 2, 4, 3, 5, 7, 6, 8, 9) 是一个半递增序列，因为它的奇数位置上的值是 1, 4, 5, 6,
9，单调递增，偶数位置上的值是 2, 3, 7, 8，也是单调递增。
请问，1 到 n 的排列中有多少个半递增序列？
【输入格式】
输入一行包含一个正整数 n。
【输出格式】
输出一行包含一个整数，表示答案，答案可能很大，请输出答案除以 1000000007 的余数。
【样例输入】
5
【样例输出】
10
【样例说明】
有以下半递增序列：
(1, 2, 3, 4, 5)
(1, 2, 3, 5, 4)
(1, 2, 4, 3, 5)
(1, 3, 2, 4, 5)
(1, 3, 2, 5, 4)
(1, 4, 2, 5, 3)
(2, 1, 3, 4, 5)
(2, 1, 3, 5, 4)
(2, 1, 4, 3, 5)
(3, 1, 4, 2, 5)
【评测用例规模与约定】
对于 50% 的评测用例，2 <= n <= 20。
对于所有评测用例，2 <= n <= 1000。
<>题解：组合数
从 n 个数中选出 (n / 2) 个数，使它们升序排列，放在偶数位置上，剩下的数升序排列放在奇数位置上
所以答案是 C(n, n / 2)
#include <iostream> using namespace std; const int MOD = 1E9 + 7; int getc(int
a, int b) { b = min(b, a - b); long long ans = 1; for (int i = 0; i < b; i++) {
ans= (ans * (a - i) / (i + 1)) % MOD; } return ans; } int main() { int n; cin >>
n; cout << getc(n, n / 2) << endl; return 0; }
<>10、试题J
【问题描述】
小蓝住在 LQ 城，今天他要去小乔家玩。
LQ 城可以看成是一个 n 行 m 列的一个方格图。
小蓝家住在第 1 行第 1 列，小乔家住在第 n 行第 m 列。
小蓝可以在方格图内走，他不愿意走到方格图外。
城市中有的地方是风景优美的公园，有的地方是熙熙攘攘的街道。小蓝很喜欢公园，不喜欢街道。他把方格图中的每一格都标注了一个属性，或者是喜欢的公园，标为1，或者是不喜欢的街道标为2。小蓝和小乔住的地方都标为了1。
小蓝每次只能从一个方格走到同一行或同一列的相邻方格。他想找到一条路径，使得不连续走两次标为 2 的街道，请问在此前提下他最少要经过几次街道？
【输入格式】
输入的第一行包含两个整数 n, m，用一个空格分隔。
接下来 n 行，每行一个长度为 m 第数字串，表示城市的标注。
【输出格式】
输出一行包含一个整数，表示答案。如果没有满足条件的方案，输出 -1。
【样例输入】
3 4
1121
1211
2211
【样例输出】
1
【样例输入】
3 4
1122
1221
2211
【样例输出】
-1
【样例输入】
5 6
112121
122221
221212
211122
111121
【样例输出】
5
【 评测用例规模与约定】
对于 50% 的评测用例，2 <= n, m <= 20。
对于所有评测用例，2 <= n, m <= 300。
<>方法一：迪杰斯特拉（优先队列）
可以当作带权最短路问题，加上前一步与后一步不能都为 ‘2’ 的条件
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; const
int N = 305, INF = 0x3f3f3f3f; int m, n; int a[N * N]; string g[N]; int ans = -1
; int d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int main() { memset(a, 0x3f,
sizeof a); cin >> m >> n; for (int i = 0; i < m; i++) { cin >> g[i]; } a[0] = g[
0][0] - '1'; priority_queue< pii, vector<pii>, greater<pii> > q; q.push( pii(a[0
], 0) ); while ( !q.empty() ) { int val = q.top().first; int x = q.top().second;
int y = x % n; x /= n; if (x == m - 1 && y == n - 1) { ans = val; break; } q.pop
(); for (int idx = 0; idx < 4; idx++) { int i = x + d[idx][0]; int j = y + d[idx
][1]; if (i >= 0 && i < m && j >= 0 && j < n && (g[x][y] == '1' || g[i][j] ==
'1')) { int id = i * n + j; if (val + g[i][j] - '1' < a[id]) { a[id] = val + g[i
][j] - '1'; q.push( pii(a[id], id) ); } } } } cout << ans << endl; return 0; }
<>方法二：0-1 BFS 广搜（双端队列）
对于所有边权均为 1（或均相同）的图可以使用队列进行广搜
而有边权为 0 或 1 的图，可以使用双端队列（deque）进行 0-1 广搜
边权为 0 就 push_front( )，为 1 则 push_back( )
同样加入前一步与后一步不能都为 ‘2’ 的条件
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; const
int N = 305, INF = 0x3f3f3f3f; int m, n; int vis[N * N]; string g[N]; int ans =
-1; int d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int main() { cin >> m >> n
; for (int i = 0; i < m; i++) { cin >> g[i]; } vis[0] = 1; deque< pii > q; q.
push_back( pii(g[0][0] - '1', 0) ); while ( !q.empty() ) { int val = q.front().
first; int x = q.front().second; int y = x % n; x /= n; if (x == m - 1 && y == n
- 1) { ans = val; break; } q.pop_front(); for (int idx = 0; idx < 4; idx++) {
int i = x + d[idx][0]; int j = y + d[idx][1]; if (i >= 0 && i < m && j >= 0 && j
< n && (g[x][y] == '1' || g[i][j] == '1')) { int id = i * n + j; if (vis[id])
continue; vis[id] = 1; if (g[i][j] == '1') q.push_front( pii(val, id) ); else q.
push_back( pii(val + 1, id) ); } } } cout << ans << endl; return 0; }