第十届蓝桥杯2019年C/C++ 大学A组省赛试题
做了好久, 终于把第十届的题全部做完了, 最后一题听了yls的思路后还啃了四五个小时(考试一共才四个小时啊), 还是太菜了. 没做前几届的题, 感觉这届挺难的,后面几个大题第一遍的时候都没能AC.糖果那题第一次用状压dp做, 后面三个数据超时了, 听了yls讲的改成IDA*才能AC.最后一题只是把样例过了, 试了几组大数据也没问题, 但是没找到地方测, 不能保证完全正确, 哪位小伙伴发现问题记得联系我哈.
试题 A: 平方和 (暴力)
本题总分：5 分
【问题描述】
小明对数位中含有 2、0、1、9 的数字很感兴趣，在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574，平方和是 14362。注意，平方和是指将每个数分别平方后求和。
请问，在 1 到 2019 中，所有这样的数的平方和是多少？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
提示：如果你编写程序计算，发现结果是负的，请仔细检查自己的程序， 不要怀疑考场的编程软件
#include <iostream>
using namespace std;
typedef long long LL;
bool st[10];
bool check(int n)
{
while (n)
{
if (st[n % 10]) return true;
n /= 10;
}
return false;
}
int main()
{
st[0] = st[1] = st[2] = st[9] = true;
LL res = 0;
for (int i = 1; i <= 2019; i ++ )
{
if (check(i)) res += i * i;
}
cout << res;
return 0;
}
答案 2658417853
试题 B: 数列求值（暴力
本题总分：5 分
【问题描述】
给定数列 1, 1, 1, 3, 5, 9, 17, …，从第 4 项开始，每项都是前 3 项的和。求
第 20190324 项的最后 4 位数字。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个 4 位整数（提示：答案的千位不为 0），在提交答案时只填写这个整数，填写多余的内容将无法得分。
#include <iostream>
using namespace std;
typedef long long LL;
const int P = 10000;
int main()
{
LL a = 1, b = 1, c = 1;
LL res = 0;
for (int i = 4; i <= 20190324; i ++ )
{
res = (a + b + c) % P;
a = b, b = c, c = res;
}
cout << res;
return 0;
}
答案 4659
试题 C: 最大降雨量
本题总分：10 分
【问题描述】
由于沙之国长年干旱，法师小明准备施展自己的一个神秘法术来求雨。
这个法术需要用到他手中的 49 张法术符，上面分别写着 1 至 49 这 49 个
数字。法术一共持续 7 周，每天小明都要使用一张法术符，法术符不能重复使用。
每周，小明施展法术产生的能量为这周 7 张法术符上数字的中位数。法术
施展完 7 周后，求雨将获得成功，降雨量为 7 周能量的中位数。
由于干旱太久，小明希望这次求雨的降雨量尽可能大，请大最大值是多少？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
? ? ? ? ? ? ?
? ? ? ? ? ? ?
? ? ? ? ? ? ?
? ? ? 34 35 36 37
? ? ? 38 39 40 41
? ? ? 42 43 44 45
? ? ? 46 47 48 49
答案 34
试题D: 迷宫(bfs)
【问题描述】
下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可 以通行的地方。
010000
000100
001001
110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。 对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫， 一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。 对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式， 其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。 请注意在字典序中D<L<R<U。
【题目给出的数据】
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 55;
int n, m;
char g[N][N];
pair<PII, char> pre[N][N];
bool st[N][N];
int dx[] = {1, 0, 0, -1}, dy[] = {0, -1, 1, 0};
char os[5] = "DLRU";
void bfs()
{
queue<PII> q;
PII t;
t.first = 0, t.second = 0;
q.push(t);
st[0][0] = true;
while (!q.empty())
{
PII u = q.front();
q.pop();
int x = u.first, y = u.second;
if (x == n - 1 && y == m - 1) break;
for (int i = 0; i < 4; i ++ )
{
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m) continue;
if (st[a][b] || g[a][b] == '1') continue;
st[a][b] = true;
pre[a][b].first = u, pre[a][b].second = os[i];
PII v(a, b);
q.push(v);
}
}
vector<char> path;
int x = n - 1, y = m - 1;
while (x != 0 || y != 0)
{
path.push_back(pre[x][y].second);
PII t = pre[x][y].first;
x = t.first, y = t.second;
}
reverse(path.begin(), path.end());
for (int i = 0; i < path.size(); i ++ )
cout << path[i];
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ ) cin >> g[i];
bfs();
return 0;
}
答案
DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUU
RRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
试题E: RSA 解密 (数论)
【问题描述】
RSA 是一种经典的加密算法。它的基本加密过程如下。
首先生成两个质数 p, q，令 n = p · q，设 d 与 (p − 1) · (q − 1) 互质，则可找到 e 使得 d · e 除 (p − 1) · (q − 1) 的余数为 1。n, d, e 组成了私钥，n, d 组成了公钥。当使用公钥加密一个整数 X 时（小于 n），计算 C = X^d mod n，则 C 是加密后的密文。
当收到密文 C 时，可使用私钥解开，计算公式为 X = C^e mod n。例如，当 p = 5, q = 11, d = 3 时，n = 55, e = 27。若加密数字 24，得 243 mod 55 = 19。解密数字 19，得 1927 mod 55 = 24。现在你知道公钥中 n = 1001733993063167141, d = 212353，同时你截获了别人发送的密文 C = 20190324，请问，原文是多少？
思路:
1: 将n分解质因数求出p, q, 算出d = (p - 1) * (q - 1)
2: 扩展欧几里得求出d模(p - 1)(q - 1)的逆元e
3:快速幂算出X = C^e mod n (龟速乘优化)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL n = 1001733993063167141;
LL d = 212353, C = 20190324;
LL p, q, e, X;
LL mul(LL a, LL b, LL P) // 龟速乘
{
LL res = 0;
while (b)
{
if (b & 1) res = (res + a) % P;
a = (a + a) % P;
b >>= 1;
}
return res;
}
LL qmi(LL a, LL b, LL P) // 快速幂
{
LL res = 1 % P;
while (b)
{
if (b & 1) res = mul(res, a, P);
a = mul(a, a, P);
b >>= 1;
}
return res;
}
LL exgcd(LL a, LL b, LL &x, LL &y) // 扩展欧几里得求逆元
{
if (!b)
{
x = 1, y = 0;
return a;
}
LL d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int main()
{
for (LL i = 2; i <= n / i; i ++ )
if (n % i == 0) p = i, q = n / i;
// p = 891234941, q = 1123984201;
LL u = (p - 1) * (q - 1);
cout << "u = " << u << endl;
LL k;
exgcd(d, u, e, k);
while (e < 0) e += u;
cout << "e = " << e << endl;
X = qmi(C, e, n);
cout << "X = " << X << endl;
return 0;
}
试题F: 完全二叉树的权值 (暴力)
【问题描述】
给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从上到下、从左到右的顺序依次是 A1, A2, · · · AN
现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。
注：根的深度是 1。
【输入格式】
第一行包含一个整数 N。
第二行包含 N 个整数 A1, A2, · · · AN 。
【输出格式】
输出一个整数代表答案。
【样例输入】
7
1 6 5 4 3 2 1
【样例输出】
2
水题直接上代码
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
int n, ans;
long long maxv = -1e9;
int w[N], pow[30];
int main()
{
pow[0] = 1;
for (int i = 1; i <= 30; i ++ ) pow[i] = 2 * pow[i - 1];
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
int h = 1;
long long sum = 0;
for (int i = 1; i <= n; i ++ )
{
sum += w[i];
if (i == pow[h] - 1)
{
if (sum > maxv)
{
maxv = sum;
ans = h;
}
sum = 0;
h ++ ;
}
}
if (sum > maxv) ans = h;
cout << ans;
return 0;
}
试题G: 外卖店优先级 (模拟)
【问题描述】
“饱了么”外卖系统中维护着 N 家外卖店，编号 1 ∼ N。每家外卖店都有一个优先级，初始时 (0 时刻) 优先级都为 0。
每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减到 0；而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。
如果某家外卖店某时刻优先级大于 5，则会被系统加入优先缓存中；如果优先级小于等于 3，则会被清除出优先缓存。
给定 T 时刻以内的 M 条订单信息，请你计算 T 时刻时有多少外卖店在优先缓存中。
【输入格式】
第一行包含 3 个整数 N、M 和 T 。
以下 M 行每行包含两个整数 ts 和 id，表示 ts 时刻编号 id 的外卖店收到一个订单。
【输出格式】
输出一个整数代表答案。
【样例输入】
2 6 6
1 1
5 2
3 1
6 2
2 1
6 2
【样例输出】
1
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
int n, m, T;
int last[N], w[N];
bool st[N];
pair<int, int> works[N];
int main()
{
scanf("%d%d%d", &n, &m, &T);
for (int i = 0; i < m; i ++ )
scanf("%d%d", &works[i].first, &works[i].second);
sort(works, works + m);
for (int i = 0; i < m; i ++ )
{
int t = works[i].first, id = works[i].second;
int sub = t - last[id] - (t == last[id] ? 0 : 1);
if (w[id] - sub < 0) w[id] = 0;
else w[id] -= sub;
if (w[id] <= 3) st[id] = false;
w[id] += 2;
if (w[id] > 5) st[id] = true;
last[id] = t;
}
int cnt = 0;
for (int i = 1; i <= n; i ++ )
{
if (w[i] - (T - last[i]) <= 3) st[i] = false;
if (st[i]) cnt ++ ;
}
cout << cnt;
return 0;
}
试题H: 修改数组 (并查集)
【问题描述】
给定一个长度为 N 的数组 A = [A1, A2, · · · AN]，数组中有可能有重复出现的整数。
现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改
A2, A3, · · · , AN。
当修改 Ai 时，小明会检查 Ai 是否在 A1 ∼ Ai−1 中出现过。如果出现过，则小明会给 Ai 加上 1 ；如果新的 Ai 仍在之前出现过，小明会持续给 Ai 加 1 ，直到 Ai 没有在 A1 ∼ Ai−1 中出现过。
当 AN 也经过上述修改之后，显然 A 数组中就没有重复的整数了。现在给定初始的 A 数组，请你计算出最终的 A 数组。
【输入格式】
第一行包含一个整数 N。
第二行包含 N 个整数 A1, A2, · · · , AN 。
【输出格式】
输出 N 个整数，依次是最终的 A1, A2, · · · , AN。
【样例输入】
5
2 1 1 3 4
【样例输出】
2 1 3 4 5
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int n;
LL p[N];
LL find(LL x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
for (int i = 1; i <= N; i ++ ) p[i] = i;
cin >> n;
while (n -- )
{
LL x;
cin >> x;
x = find(x);
cout << x << ' ';
p[x] = find(x + 1);
}
return 0;
}
试题I: 糖果 (重复覆盖问题 IDA*)
【问题描述】
糖果店的老板一共有 M 种口味的糖果出售。为了方便描述，我们将 M 种口味编号 1 ∼ M。
小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果，而 是 K 颗一包整包出售。
幸好糖果包装上注明了其中 K 颗糖果的口味，所以小明可以在买之前就知道每包内的糖果口味。
给定 N 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖果。
【输入格式】
第一行包含三个整数 N、M 和 K。
接下来 N 行每行 K 这整数 T1, T2, · · · , TK，代表一包糖果的口味。
【输出格式】
一个整数表示答案。如果小明无法品尝所有口味，输出 −1。
【样例输入】
6 5 3
1 1 2
1 2 3
1 1 3
2 3 5
5 4 2
5 1 2
【样例输出】
2
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 110, M = 1 << 20;
int ans;
int n, m, k;
int w[N];
vector<int> path[20];
int f(int state)
{
int cnt = 0;
for (int i = 0; i < m; i ++ )
{
if (!(state >> i & 1))
{
for (int j = 0; j < path[i].size(); j ++ )
{
state |= path[i][j];
}
cnt ++ ;
}
}
return cnt;
}
bool dfs(int u, int state, int depth)
{
if (u > depth) return false;
if (u + f(state) > depth) return false;
for (int i = 0; i < m; i ++ )
{
if (!(state >> i & 1))
{
for (int j = 0; j < path[i].size(); j ++ )
{
int v = path[i][j];
if (dfs(u + 1, state | v, depth)) return true;
}
return false;
}
}
return true;
}
int main()
{
cin >> n >> m >> k;
for (int i = 1; i <= n; i ++ )
{
int x;
for (int j = 0; j < k; j ++ )
{
cin >> x;
w[i] |= 1 << (x - 1);
}
}
for (int i = 0; i < m; i ++ )
{
for (int j = 1; j <= n; j ++ )
{
if (w[j] >> i & 1)
{
path[i].push_back(w[j]);
}
}
}
int depth = 1;
while (depth <= m && !dfs(0, 0, depth)) depth ++ ;
if (depth > m) cout << "-1" << endl;
else cout << depth << endl;
return 0;
}
试题J: 组合数问题 (卢卡斯定理 + 数位dp)
【问题描述】
给 n, m, k， 求 有 多 少 对 (i, j) 满 足 1 ≤ i ≤ n, 0 ≤ j ≤ min(i, m) 且 C j ≡
0(mod k)，k 是质数。其中 C j 是组合数，表示从 i 个不同的数中选出 j 个组成
一个集合的方案数。
【输入格式】
第一行两个数 t, k，其中 t 代表该测试点包含 t 组询问，k 的意思与上文中相同。
接下来 t 行每行两个整数 n, m，表示一组询问。
【输出格式】
输出 t 行，每行一个整数表示对应的答案。由于答案可能很大，请输出答案除以 109 + 7 的余数。
【样例输入】
1 2
3 3
【样例输出】
1
【样例说明】
在所有可能的情况中，只有 C(2, 1) = 2 是 2 的倍数。
【样例输入】
2 5
4 5
6 7
【样例输出】
0
7
【样例输入】
3 23
23333333 23333333
233333333 233333333
2333333333 2333333333
【样例输出】
851883128
959557926
680723120
这题数据范围很大,每组数据要用logn的做法, 具体思路参照y的讲解, 这里把代码发一下
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 70, P = 1e9 + 7;
LL n, m, k, num;
int t;
int f[N], g[N], pow[N];
inline LL sum(int a, int b)
{
return (b - a + 1) * (a + b) / 2;
}
void init(vector<LL> A, vector<LL> B)
{
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
for (int i = 0; i < B.size(); i ++ )
{
f[i] = (sum(k - B[i] + 1, k) * pow[i]) % P;
if (i) f[i] = ((k - B[i]) * f[i - 1] + f[i]) % P;
else f[i] = (k - B[i] + f[i]) % P;
if (i) g[i] = (sum(1, A[i]) * pow[i] + (A[i] + 1) * g[i - 1]) % P;
else g[i] = sum(1, A[i] + 1);
}
}
LL dp()
{
LL ans = 0;
vector<LL> nums_n, nums_m;
while (n) nums_n.push_back(n % k), n /= k;
while (m) nums_m.push_back(m % k), m /= k;
init(nums_n, nums_m);
if (nums_m.size() > nums_n.size()) return g[nums_n.size()];
LL last = 0;
for (int i = nums_n.size() - 1; i >= 0; i -- )
{
if (i >= nums_m.size())
{
last = last * k + nums_n[i];
continue;
}
if (i == nums_m.size() - 1)
ans = (ans + last * f[i]) % P;
if (nums_m[i] > nums_n[i])
{
ans = (ans + sum(1, nums_n[i]) * pow[i] % P + (nums_n[i] + 1) * (i ? g[i - 1] : 1) % P) % P;
break;
}
else
{
ans = (ans + sum(nums_n[i] - nums_m[i] + 1, nums_n[i]) * pow[i] % P) % P;
ans = (ans + (nums_n[i] - nums_m[i]) * (i ? f[i - 1] : 1) % P) % P;
ans = (ans + nums_m[i] * (i ? g[i - 1] : 1) % P) % P;
}
if(!i) ans ++ ;
}
return ans;
}
LL mul(LL a, LL b, int p)
{
LL res = 0;
while (b)
{
if (b & 1) res = (res + a) % p;
a = (a + a) % p;
b >>= 1;
}
return res;
}
int main()
{
cin >> t >> k;
pow[0] = 1;
int v = sum(1, k);
for (int i = 1; i <= 64; i ++ ) pow[i] = ((LL)v * pow[i - 1]) % P;
while (t -- )
{
cin >> n >> m;
if (m >= n)
{
if (n % 2 == 0) num = mul((n + 2) / 2, n + 1, P);
else num = mul((n + 1) / 2, (n + 2), P);
}
else
{
if (m % 2 == 0) num = mul((n + n + 2 - m) / 2, m + 1, P);
else num = mul((m + 1) / 2, n + n + 2 - m, P);
}
LL res = dp();
cout << ((num - res) % P + P) % P << endl;
}
return 0;
}
