P8679 [蓝桥杯 2019 省 B] 填空问题 题解
题目传送门
欢迎大家指出错误并联系这个蒟蒻
更新日志
- 2023-05-25 21:02 文章完成
- 2023-05-27 11:34 文章通过审核
- 2023-06-20 21:03 优化了文章代码格式
试题 A ：组队
【解析】
本题是一道经典的 DFS 搜索题，每次对各号位的选手进行 DFS，找到各号位上有成绩的选手时再进行进一步搜索即可。
【程序】
#include <bits/stdc++.h>
using namespace std;
int team[20][6];
int max_sum;
bool vis[20];
void dfs(int u, int sum) {
if (u > 5) {
max_sum = max(max_sum, sum);
return;
}
for (int i = 0; i < 20; i++) {
if (!vis[i]) {
vis[i] = true;
dfs(u + 1, sum + team[i][u]);
vis[i] = false;
}
}
}
int main() {
freopen("team.txt", "r", stdin);
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 6; j++) {
cin >> team[i][j];
}
}
dfs(1, 0);
cout << max_sum;
return 0;
}
【答案】
490
试题 B ：年号字串
【解析】
该题的 A~Z 相当于二十六进制的 $26$ 个基，因此本题就转换成将 $2019$ 转成二十六进制数的问题。
【程序】
#include <bits/stdc++.h>
using namespace std;
char ch[26];
char ans[5];
int a, n = 2019;
int main() {
for (int i = 0; i < 26; i++) {
ch[i] = 'A' + i;
}
while (n) {
int t = n % 26;
n = n / 26;
if (t == 0) {
t += 26;
}
ans[a++] = ch[t - 1];
}
for (int i = a - 1; i >= 0; i--) {
printf("%c", ans[i]);
}
return 0;
}
【答案】
BYQ
试题 C ：数列求值
【解析】
该数列其实很容易让人联想到斐波那契数列，可以采用计算斐波那契数列的递推法进行计算。
【程序】
#include <bits/stdc++.h>
using namespace std;
int dp[20190324];
int main() {
int i;
dp[0] = dp[1] = dp[2] = 1;
for (i = 3; i < 20190324; i++) {
dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 10000;
}
printf("%d", dp[i - 1]);
return 0;
}
【答案】
4659
试题 D ：数的分解
【解析】
本题可以枚举 $3$ 个数字，但是如果 $3$ 个数字都从 $1$ 枚举到 $2019$，则程序就会变得很复杂，我们应该主要解决以下 $2$ 个问题：
1、三数之和等于 $2019$。
2、解决重复情况。
对于情况 $1$，要满足 $i+j+k=2019$，其实 $i$ 和 $j$ 一旦确定，$k$ 的值就已经确定了，所以利用该式，定义的 $3$ 个变量可以变成 $i$、$j$、$2019-i-j$。
对于情况 $2$，要想使得 $3$ 个数字不重复，则只需要将这 $3$ 个数排序，保证排序后的序列是唯一的即可。
【程序】
#include <bits/stdc++.h>
using namespace std;
int judge(int a) {
while (a != 0) {
int t = a % 10;
if (t == 2 || t == 4) {
return 0;
}
a = a / 10;
}
return 1;
}
int main() {
int sum = 0;
for (int i = 1; i < 2019 / 3 + 1; i++) {
if (judge(i)) {
for (int j = i + 1; j < 2019 - i - j; j++) {
if (judge(j)) {
if (judge(2019 - i - j)) {
sum++;
}
}
}
}
}
printf("%d", sum);
return 0;
}
【答案】
40785
试题 E ：迷宫
【解析】
本题求步数最少的迷宫路径，即求最短路线。利用 DFS 搜索时回溯较多，容易“爆栈”，所以本题使用 BFS 求最优解即可。
【答案】
DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
P8684 [蓝桥杯 2019 省 B] 灵能传输 题解
题目传送门
欢迎大家指出错误并联系这个蒟蒻
更新日志
- 2023-06-20 21:46 文章完成
【解析】
本题涉及到了 $3$ 种算法：前缀和，排序以及贪心
（1）前缀和
本题实际上要求通过某种灵能传输可以使得该序列的最大值最小。而由前缀和可知，当某一个前缀和序列保持有序（或前缀和序列表示的函数单调）时，其 $\max(s[i]-s[i-1])$ 的最大值可以达到最小。
通过对几个样例的观察我们不难发现：
1.当 $a[i]>0$ 时，若 $a[i-1]=a[i-1]+a[i]$，则$s[i-1]$ 等于原来的 $s[i]$。
2.若 $a[i]=a[i]-2a[i]$，则原 $s[i-1]=s[i-1]+s[i]$。
3.现 $s[i]=$ 现 $s[i-1]-a[i]=$ 原 $s[i]-a[i]=$ 原 $s[i-1]$。
这意味着除了 $s[0]$ 和 $s[n]$ 以外，$1\sim n$ 的任何 $s[i]$ 都可以进行互相交换，从而得到一个有序序列。而 $a[i]=s[i]-s[i-1]$ 也就意味着可以通过交换 $s[i]$ 的方式得到灵能传输后的最终结果。
（2）排序
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i], s[i] = s[i - 1] + a[i]);
}
sort(s + 1, s + 1 + n);
当然，如果 $s[0]$ 和 $s[n]$ 也可以正常交换，则只需要将整个前缀和序列进行排序，即可直接得到一个单调函数，那么本题的推导到这一步就可以结束了，可以通过直接计算 $\max(s[i]-s[i-1])$ 的值获得最大值和最小值。但问题就在于 $s[0]$ 和 $s[n]$，即最终得到的序列不一定是单调的，所以接下来就要通过一系列操作解决序列不单调的问题。
（3）贪心
通过上述的分析可以得知，想要求出本题的最优解就是使得所求序列尽可能保持单调。通过画图可知，在两个端点无法移动的条件下，在对于整个前缀和序列进行排序时，总能得到一个拥有两个拐点且中间部分保持单调的函数。此时就应该往贪心上思考，即当一条有两个拐点的曲线的重叠部分最小时单调部分最多，而一条曲线符合下列情况时符合要求。
①左端点小于右端点，即 $s[0]<s[n]$。在记录 $s_0$ 和 $s_n$ 的值时需要进行一次判定，如果得到的左端点比右端点大，那么就将这两个端点交换（尽量保证得到的函数是一个中部递增的单调函数，其目的是将得到的所有函数都变成中部递增函数，这样就可以少算至少一半的数据）。
if (s0 > sn) {
swap(s0, sn);
}
②极小值在极大值左边（刚刚的情况中，要求得到的函数一定是中部递增的，因此不仅需要控制函数中部的递增，还要控制最大值和最小值以使得中部函数递增）。这就要求在后续选点时应遵循 $s[0]$ 向左取，$s[n]$ 向右取，因为这样才能取得两边的极值。
因为已经将两个端点确定并保证了两者的顺序，也对前缀和序列进行了升序处理，于是此时得到了一个存放着递增的前缀和序列的有序数组（左右端点的位置已经发生改变，情况①中已经记录了两者位置）。
接下来需要从左端点的位置向左依次取点，从右端点的位置向右依次取点（从左端点向左依次取点并取得前缀和序列的最小值，从右端点向右依次取点并取得前缀和序列的最大值）。此时通过画图可以求得函数为两个端点有拐点且中部有序递增的函数。
int l = 0, r = n - 1;
for (int i = s0; i >= n; i -= 2) {
f[l++] = s[i];
st[i] = true;
}
for (int i = sn; i <= n; i += 2) {
f[r--] = s[i];
st[i] = true;
}
for (int i = 0; i <= n; i++) {
if (st[i] == false) {
f[l++] = s[i];
}
}
因为图像中有两个拐点而且会形成两个重叠部分，所以想要得到最优解，就要使得求得的函数图像中的递增部分尽可能地多，这样拐点处的图像就会尽可能地少，即可保证序列 $f$ 为重叠部分最小的前缀和序列。
在通过特定规则将所有点都遍历完毕后，此时已经得到最优解的图像（前缀和序列）。最后就是求出所有前缀和表示的灵能值中的最大者（一定为正），该灵能值便是最终答案。
int res = 0;
for (int i = 1; i <= n; i++) {
res = max(res, abs(f[i] - f[i - 1]));
}
$res$ 即为所求结果
【代码】
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
typedef long long ll;
ll a[N];
ll s[N];
ll f[N];
bool st[N];
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
s[0] = 0;
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
s[i] = s[i - 1] + a[i];
}
ll s0 = s[0];
ll sn = s[n];
if (s0 > sn) {
swap(s0, sn);
}
sort(s, s + 1 + n);
for (int i = 0; i <= n; i++) {
if (s0 == s[i]) {
s0 = i;
break;
}
}
for (int i = 0; i <= n; i++) {
if (sn == s[i]) {
sn = i;
break;
}
}
memset(st, false, sizeof st);
int l = 0, r = n;
for (int i = s0; i >= 0; i -= 2) {
f[l++] = s[i];
st[i] = true;
}
for (int i = sn; i <= n; i += 2) {
f[r--] = s[i];
st[i] = true;
}
for (int i = 0; i <= n; i++) {
if (st[i] == false) {
f[l++] = s[i];
}
}
ll res = 0;
for (int i = 1; i <= n; i++) {
res = max(res, abs(f[i] - f[i - 1]));
}
printf("%lld\n", res);
}
return 0;
}
P8741 [蓝桥杯 2021 省 B] 填空问题 题解
题目传送门
欢迎大家指出错误并联系这个蒟蒻
更新日志
- 2023-05-09 23:19 文章完成
- 2023-05-09 23:20 通过审核
- 2023-06-20 21:03 优化了文章代码格式
试题 A ：空间
【解析】
本题考察计算机存储的基础知识，只要掌握空间存储的换算方法，就能够算出答案。
【程序】
#include <bits/stdc++.h>
using namespace std;
int main() {
printf("%d\n", 256 * 8 / 32 * 1024 * 1024);
return 0;
}
【答案】
67108864
试题 B ：卡片
【解析】
这道题应该先定义一个长度为 $10$ 的数组，用来存放数字 $0 \sim 9$ 的卡片数，下标则代表数字，元素代表卡片已经使用的张数，初始值为 $0$ ，每种卡片如果使用超过 $2021$ 张，则输出结果。
程序从 $1$ 开始递增遍历，当遍历到某个数时，将拼成该数所需的所有卡片类型数增加，随后判断数组中每种卡片是否被用完，如果用完则退出循环。
【程序】
#include <bits/stdc++.h>
using namespace std;
int a[10];
int main() {
for (int s = 1;; s++) {
int temp = s;
while (temp) {
a[temp % 10]++;
temp /= 10;
}
for (int i = 1; i < 10; i++) {
if (a[i] > 2021) {
printf("%d\n", s - 1);
// 减1是因为这一张无法凑出
return 0;
}
}
}
return 0;
}
【答案】
3181
试题 C ：直线
【解析】
本题很容易让人想到枚举和去重，本人代码就是用枚举和去重来实现的。
为了储存 $3$ 个数，本人采取了 $\operatorname{STL}$ 中 $\operatorname{pair}$ 类来表示，为了去重，本人采取了 $\operatorname{STL}$ 中的 $\operatorname{set}$ 集合 （如果没学过，请自行查阅资料）。
【程序】
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef pair<PII, int> PIII;
set<PIII> s;
vector<PII> vec;
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
int main() {
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 21; j++) {
vec.push_back({ i, j });
}
}
for (int i = 0; i < vec.size(); i++) {
for (int j = i + 1; j < vec.size(); j++) {
int x1 = vec[i].first, y1 = vec[i].second;
int x2 = vec[j].first, y2 = vec[j].second;
int A = x2 - x1, B = y1 - y2, C = x1 * y2 - x2 * y1;
int gcdd = gcd(gcd(A, B), C);
s.insert({ { B / gcdd, A / gcdd }, C / gcdd });
}
}
cout << s.size() << endl;
return 0;
}
【答案】
40257
试题 D ：货物摆放
【解析】
本题根据题意，要满足 $\operatorname{n}=\operatorname{x}\times \operatorname{y}\times \operatorname{z}$ 的所有情况，首先想到枚举法，分为两步：
1、找出 $n$ 的所有因子。
2、对所有因子进行暴力枚举。
【程序】
#include <bits/stdc++.h>
using namespace std;
long long a[100];
long long n = 2021041820210418;
int len;
int main() {
for (long long i = 1; i * i <= n; i++) {
if (n % i == 0)
// i是约数
{
a[len++] = i;
// 将约数放入数组
if (n / i != i)
// n/i也是约数
{
a[len++] = n / i;
}
}
}
int ans = 0;
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
for (int k = 0; k < len; k++) {
if (a[i] * a[j] * a[k] == n) {
ans++;
}
}
}
}
printf("%d\n", ans);
return 0;
}
【答案】
2430
试题 E ：路径
【解析】
本题题意比较直接，通过题意就可以知道题目考查图的最短路径算法，本人则使用了 $\operatorname{Dijkstra}$ 算法直接计算 （如果没学过，请自行查阅资料并学习）。
【程序】
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2022;
int edges[MAXN][MAXN];
int d[MAXN];
bool visited[MAXN];
int gcd(int u, int v) {
int temp = u % v;
while (temp > 0) {
u = v;
v = temp;
temp = u % v;
}
return v;
}
int lcm(int u, int v) {
return (u * v / gcd(u, v));
}
int main() {
memset(edges, 0x3f3f3f, sizeof(edges));
for (int i = 1; i <= 2021; i++) {
edges[i][i] = 0;
for (int j = i + 1; j <= 2021; j++) {
if (j - i <= 21) {
edges[i][j] = edges[j][i] = lcm(j, i);
} else {
break;
}
}
}
memset(d, 0x3f3f3f, sizeof(d));
memset(visited, false, sizeof(visited));
d[1] = 0;
for (int i = 1; i < 2021; i++) {
int x = 0;
for (int j = 1; j < 2021; j++) {
if (!visited[j] && d[j] < d[x]) {
x = j;
}
}
visited[x] = 1;
for (int j = max(1, x - 21); j <= min(2021, x + 21); j++) {
d[j] = min(d[j], d[x] + edges[x][j]);
}
}
printf("%d\n", d[2021]);
return 0;
}
【答案】
10266837