【蓝桥杯真题】2021年蓝桥杯省赛B组题目解析+代码(C/C++)
2021年蓝桥杯省赛B组题解(C/C++)
来自微信公众号:算法梦工厂,二维码见文末。可关注公众号获取往年试题题解。
试题 A: 空间
问题描述
涉及知识点:计算机基础知识
答案:67108864
解析:
主要考察一些计算机的基础知识,
32
32
32 位二进制数需要占
4
4
4 个字节,
256
M
B
=
256
∗
1024
K
B
=
256
∗
1024
∗
1024
256MB = 256*1024KB = 256*1024*1024
256MB=256∗1024KB=256∗1024∗1024 字节,所以一共可以存储的
32
32
32 位二进制整数的数量就是:
256
∗
1024
∗
1024
/
4
=
67108864
256*1024*1024/4 = 67108864
256∗1024∗1024/4=67108864 。
代码:
#include <bits/stdc++.h>
int main() {
printf("%d", 256 * 1024 * 1024 / 4);
return 0;
}
试题 B: 卡片
问题描述
答案:3181
解析
- 涉及知识点:枚举,十进制拆分
- 做法:初始化 res_num 数组记录当前每种卡牌剩余数量,从1向上枚举需要组合的卡片,直到剩余卡片不足则停止累加,最后成功组合成的卡片即为答案。
代码
#include <bits/stdc++.h>
using namespace std;
vector<int> Split(int x) { // 将x按照十进制拆分每一位
vector<int> ret;
if (x == 0) {
ret.push_back(0);
return ret;
}
while (x > 0) {
ret.push_back(x % 10);
x /= 10;
}
return ret;
}
const int maxn = 2021;
int rest_num[10] = {0}; // 记录当前每种数字卡牌剩余数量
bool Sub(const vector<int> &x) { // 将当前需要的数字卡牌从卡牌库中去除,卡牌库剩余卡牌不足则返回false
for (unsigned int i = 0; i < x.size(); i++) {
rest_num[x[i]]--;
if (rest_num[x[i]] < 0) {
return false;
}
}
return true;
}
int main() {
for (int i = 0; i < 10; i++) {
rest_num[i] = maxn;
}
int ans = 1;
while (1) { // 尝试利用剩余卡牌组合出数字ans,剩余卡牌不足则跳出循环
vector<int> need = Split(ans);
bool succFlag = Sub(need);
if (!succFlag) {
break;
}
ans++;
}
printf("ans = %dn", ans - 1);
return 0;
}
试题 C: 直线
问题描述
答案:40257
解析
- 涉及知识点:枚举、浮点数判
- 做法:
- 枚举所有点的两两组合,对于每一对两个点的组合就确定了一条直线,对于每条直线都判断其是否和之前已经出现过的直线相同,如果相同则忽略。
- 判断两个直线是否相同的做法:每个直线存储直线上两个点,对于直线
L
0
(
p
0
,
p
1
)
L_0(p_0,p_1)
L
1
(
p
2
,
p
3
)
L_1(p_2,p_3)
p
2
p_2
p
3
p_3
L
1
L_1
L
1
L_1
L
2
L_2
- 判断一个点是否在直线上的做法:假设存在点
p
2
p_2
L
(
p
0
,
p
1
)
L(p_0,p_1)
a
+
b
=
c
a+b=c
1
0
−
7
10^{-7}
代码
#include <bits/stdc++.h>
using namespace std;
struct Point {
int x, y;
Point() {}
Point(int x, int y) {
this->x = x;
this->y = y;
}
};
struct Line {
Point a, b;
Line(Point a, Point b) {
this->a = a;
this->b = b;
}
};
vector<Line> lineList;
double Dis(Point p0, Point p1) { // 计算点p0和p1之间的直线距离
return sqrt((p0.x - p1.x) * (p0.x - p1.x) + (p0.y - p1.y) * (p0.y - p1.y));
}
bool CheckPointInLine(Line x, Point p) { // 检查点p是否在直线x上
double dis[3];
dis[0] = Dis(x.a, x.b);
dis[1] = Dis(x.a, p);
dis[2] = Dis(x.b, p);
sort(dis, dis + 3);
if (fabs(dis[0] + dis[1] - dis[2]) < 1e-5) { // 三点在一条直线则较短两距离相加等于较长距离
return true;
} else {
return false;
}
}
// 检查当先直线cur是否和之前已经出现过得直线集合(lineList)中的某一直线重合
bool CheckLineRepeat(Line cur) {
for (unsigned int i = 0; i < lineList.size(); i++) {
if (CheckPointInLine(lineList[i], cur.a) &&
CheckPointInLine(lineList[i], cur.b)) {
return true;
}
}
return false;
}
int main() {
vector<Point> pointList;
// 将所有点记入pointList中
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 21; j++) {
pointList.push_back(Point(i, j));
}
}
// 尝试任意两点的组合组成的直线,如果直线没出现过则记录下来,否则跳过
int ans = 0;
for (unsigned int i = 0; i < pointList.size(); i++) {
for (unsigned int j = i + 1; j < pointList.size(); j++) {
Line curLine = Line(pointList[i], pointList[j]);
if (!CheckLineRepeat(curLine)) {
ans++;
lineList.push_back(curLine);
}
}
}
printf("ans = %dn", ans);
return 0;
}
试题 D: 货物摆放
问题描述
答案:2430
解析
- 涉及知识点:质因数分解
- 做法:
- 问题可以转化成,将
2021041820210418
2021041820210418
a
∗
b
∗
c
a*b*c
- 将
2021041820210418
2021041820210418
p
0
n
0
∗
p
1
n
1
∗
.
.
.
∗
p
n
n
n
p_0^{n_0} *p_1^{n_1}* ... *p_n^{n_n}
p
0
,
p
1
,
.
.
.
,
p
n
p_0, p_1, ... , p_n
2021041820210418
=
2
1
∗
3
3
∗
1
7
1
∗
13
1
1
∗
285
7
1
∗
588235
3
1
2021041820210418 = 2^1* 3^3 *17^1* 131^1 *2857^1* 5882353^1
- 对于质因数:
2
,
17
,
131
,
2857
,
5882353
2,17,131,2857,5882353
a
,
b
,
c
a,b,c
3
5
3^5
- 对于出现了
3
3
3
3
3
5
∗
10
=
2430
3^5 * 10 = 2430
- 问题可以转化成,将
代码
#include <bits/stdc++.h>
using namespace std;
vector<long long int> primeNum, primeVal;
// 将x质因数分解
void CalaPrime(long long int x) {
printf("%lld = ", x);
for (long long int i = 2; i * i <= x; i++) {
if (x % i == 0) {
int num = 0;
while (x % i == 0) {
x /= i;
num++;
}
primeNum.push_back(num);
primeVal.push_back(i);
}
}
if (x > 1) {
primeNum.push_back(1);
primeVal.push_back(x);
}
for (unsigned int i = 0; i < primeNum.size(); i++) {
if (i != 0) {
printf(" * ");
}
printf("n(%lld ^ %lld)", primeVal[i], primeNum[i]);
}
printf("n");
}
int main() {
CalaPrime(2021041820210418);
long long int ans = 0;
ans = 3 * 3 * 3 * 3 * 3;
ans *= 10;
printf("ans = %lldn", ans);
return 0;
}
试题 E: 路径
问题描述
答案:10266837
解析
- 涉及算法:图论,最短路,最大公约数
- 做法:
- 建图:共2021个结点组成的图,枚举任意两点组合,通过计算最大公约数,记录这两个点之间的距离,即增加一条边。
- 公式:
l
c
m
(
x
,
y
)
=
x
∗
y
g
c
d
(
x
,
y
)
lcm(x,y) = frac {x*y} {gcd(x,y)}
l
c
m
(
x
,
y
)
lcm(x,y)
x
x
y
y
g
c
d
(
x
,
y
)
gcd(x,y)
x
x
y
y
- 最短路求解:可以使用Floyd算法或DijkStra算法计算最短路。(这里因为是填空题,建议使用Floyd算法更加好写,可以考虑两个算法都实现用来相互验证)
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2021;
vector<int> u[maxn + 52];
vector<int> v[maxn + 52];
int disDijk[maxn + 52];
int disFloyd[maxn + 52][maxn + 52];
bool vis[maxn + 52];
// 初始化建图,u[i][j]表示i的第j条出边编号,v[i][j]表示i的第j条边的长度,也就是i和u[i][j]的距离
void InitGroup() {
for (int i = 1; i <= maxn; i++) {
for (int j = i + 1; j <= maxn; j++) {
if (j - i <= 21) {
u[i].push_back(j);
v[i].push_back(i * j / __gcd(i, j));
u[j].push_back(i);
v[j].push_back(i * j / __gcd(i, j));
}
}
}
}
// floyd算法计算最短路,disFloyd[i][j] 表示i到j的最短距离
void Floyd() {
// 初始化disFloyd为一个较大值
memset(disFloyd, 0x3f, sizeof(disFloyd));
for (unsigned int i = 1; i <= maxn; i++) {
for (unsigned int j = 0; j < v[i].size(); j++) {
disFloyd[i][u[i][j]] = v[i][j];
disFloyd[u[i][j]][i] = v[i][j];
}
}
// 执行floyd算法
for (int k = 1; k <= maxn; k++) {
for (int i = 1; i <= maxn; i++) {
for (int j = 1; j <= maxn; j++) {
disFloyd[i][j] = disFloyd[j][i] = min(disFloyd[i][j], disFloyd[i][k] + disFloyd[k][j]);
}
}
}
printf("floyd ans = %dn", disFloyd[1][maxn]);
}
// Dijkstra算法计算最短路,disDijk[i]表示i距离结点1的最短距离
void Dijkstra() {
memset(disDijk, 0x3f, sizeof(disDijk));
memset(vis, 0, sizeof(vis));
disDijk[1] = 0;
for (int i = 1; i <= maxn; i++) {
int curMin = 0x3f3f3f3f;
int curIndex = -1;
for (int j = 1; j <= maxn; j++) {
if (vis[j]) {
continue;
}
if (curMin > disDijk[j] || curIndex == -1) {
curMin = disDijk[j];
curIndex = j;
}
}
vis[curIndex] = true;
for (unsigned int j = 0; j < u[curIndex].size(); j++) {
int t = u[curIndex][j], val = v[curIndex][j];
disDijk[t] = min(disDijk[t], disDijk[curIndex] + val);
}
}
printf("Dijkstra ans = %d vis = %dn", disDijk[2021], vis[2021]);
}
int main() {
InitGroup();
Floyd();
Dijkstra();
return 0;
}
试题 F: 时间显示
问题描述
涉及知识点:取模,时间计算,格式化输出
解析
注意题目中给定的是毫秒,利用整除和取模就可以完成计算。具体细节可以参照代码中的注释。
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
long long int dayMs = 24 * 60 * 60 * 1000; //一天包含多少毫秒
long long int n;
scanf("%lld", &n);
// 扣除整天的描述之后,得到最后一天剩下了多少毫秒
n = n % dayMs;
// 忽略毫秒,得到还剩多少秒
n = n / 1000;
// 一小时3600秒,走过了多少个完整的3600秒就代表当前小时数是多少
int hour = n / (3600);
// 扣除整小时之后剩下的秒数,可以走过多少个完整的60秒就代表当前分钟数是多少
int minutes = (n - hour * 3600) / 60;
// 走完全部的完整60秒之后剩下的秒数就是秒数
int second = n % 60;
printf("%02d:%02d:%02dn", hour, minutes, second);
}
试题 G: 砝码称重
问题描述
解析
-
涉及知识点:动态规划,类背包问题
-
思路一:问题可以转化成:给定
n
n
n 个正整数,计算从中选出若个数字组合,每个数字可以加或者减,最终能得到多少种正整数结果。
- 状态定义:
d
p
(
i
,
j
)
dp(i,j)
i
i
j
j
−
1
0
5
≤
j
≤
1
0
5
-10^5le j le 10^5
- 状态转移方程:
d
p
(
i
,
j
)
=
d
p
(
i
−
1
,
j
)
∣
d
p
(
i
−
1
,
j
−
a
[
i
]
)
∣
d
p
(
i
−
1
,
j
+
a
[
i
]
)
dp(i,j) = dp(i-1,j) | dp(i-1, j-a[i]) | dp(i-1,j+a[i])
- 初始状态:
d
p
(
0
,
0
)
=
1
dp(0,0) = 1
- 时间复杂度分析:状态数
n
∗
s
u
m
∗
2
n*sum* 2
O
(
1
)
O(1)
O
(
n
∗
s
u
m
)
O(n*sum)
s
u
m
sum
1
0
5
10^5
- 状态定义:
-
思路二:问题还可以转化成:给定
2
∗
n
2*n
2∗n 个正整数,
a
0
,
a
1
,
.
.
.
,
a
n
,
−
a
0
,
−
a
1
,
.
.
.
,
−
a
n
a_0,a_1,...,a_n,-a_0,-a_1,...,-a_n
a0,a1,...,an,−a0,−a1,...,−an ,每个数字可以选或者不选,问相加可以组合成多少种不同的正整数。这样就是一个经典的01背包问题了,只要注意一下负数问题即可。
-
其它技巧注意事项:
- 利用滚动数组,反复交换
c
u
r
cur
p
r
e
pre
- 使用
o
f
f
s
e
t
offset
d
p
dp
- 利用滚动数组,反复交换
代码
#include <bits/stdc++.h>
using namespace std;
const int offset = 100052; // 为处理负数情况引入的偏移量
const int maxn = 100052 + offset;
int n, vis[2][maxn], a[2000];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
memset(vis, 0, sizeof(vis));
vis[0][offset] = 1;
int pre = 0, cur = 1;
// 三种情况分别是,不选择a[i],选择a[i],选择-a[i]
for (int i = 0; i < n; i++) {
for (int j = 0; j < maxn; j++) {
vis[cur][j] = max(vis[cur][j], vis[pre][j]);
if (j - a[i] >= 0) {
vis[cur][j] = max(vis[pre][j - a[i]], vis[cur][j]);
}
if (j + a[i] < maxn) {
vis[cur][j] = max(vis[pre][j + a[i]], vis[cur][j]);
}
}
swap(pre, cur); // 滚动循环利用数组的pre行和cur行
}
// 注意要从offset+1开始,因为能称出来的重量不应该是负数
int ans = 0;
for (int i = offset + 1; i < maxn; i++) {
if (vis[pre][i]) {
ans++;
}
}
printf("%d", ans);
return 0;
}
试题 H: 杨辉三角形
问题描述
涉及知识点:二分,组合数计算,打表
解析
这里其实需要知道或者自己分析出一些杨辉三角的性质,首先为了方便表示,将这个杨辉三角表示成这种形式:
第
i
i
i 行第
j
j
j 个数表示成
c
(
i
,
j
)
c(i,j)
c(i,j) ,行数和列数都从
0
0
0 开始计算。
可以发现如下的结论:
-
c
(
n
,
m
)
=
n
!
m
!
∗
(
n
−
m
)
!
c(n,m) = frac{n!}{m!*(n-m)!}
-
c
(
n
,
m
)
=
c
(
n
,
n
−
m
)
c(n,m) = c(n,n-m)
-
c
(
n
,
m
)
=
c
(
n
−
1
,
m
−
1
)
+
c
(
n
−
1
,
m
)
c(n,m) = c(n-1,m-1) + c(n-1,m)
考虑到每一行是对称的,所以如果如果一个数字在某一行的右半边出现,那么它一定也在这一行的左半边出现,因此每一行右半边的数字一定不会作为第一个出现的数字。此外可以发现
c
(
i
,
1
)
=
i
c(i,1) = i
c(i,1)=i ,所以任意一个数字
n
n
n 一定会在这个杨辉三角矩阵中出现过。另外根据上面的公式1可以发现,每一行的数字都是呈现一个先增后减的形式,并且增长速度极快。每一列数字则是完全单调递增的。因此可以尝试在每一列二分搜索是否有该数字。只需要考虑前
20
20
20 列即可,因为后面的数字大小已经完全超过了
n
n
n 的最大范围,所以一定不会等于
n
n
n。
代码
#include <bits/stdc++.h>
using namespace std;
// 打印杨辉三角前x行,帮助直观感受
void Print(int x) {
long long int c[100][100];
for (int i = 1; i <= x; i++) {
c[i][0] = 1;
printf("%lldt", c[i][0]);
for (int j = 1; j < i; j++) {
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
printf("%lldt", c[i][j]);
}
printf("n");
}
}
// 二分方法
long long int n;
long long int C(long long int a, long long int b) {
long long int ret = 1;
for (long long int i = a, j = 1; j <= b; i--, j++) {
ret = ret * i / j;
if (ret > n) {
return n + 1;
}
}
return ret;
}
long long int GetAns(int col) {
long long int l = col, r = max(n, (long long int)col);
while (l < r) {
long long int mid = (l + r) / 2;
if (C(mid, col) >= n)
r = mid;
else
l = mid + 1;
}
if (C(r, col) != n) { // 没有出现则返回出现位置无限大
return 4e18;
} else {
return r * (r + 1) / 2 + col + 1;
}
}
int main() {
scanf("%lld", &n);
long long int ans = 4e18;
for (int i = 0; i < 20; i++) { // 枚举前20列,记录最早出现位置
long long int cur = GetAns(i);
ans = min(ans, cur);
}
printf("%lldn", ans);
return 0;
}
试题 I: 双向排序
问题描述
涉及知识点:贪心,线段树,排序
解析
此题完全通过较为困难,此处给出简单版本使用sort函数代码。可以考虑,对于连续的0操作或者1操作,只需要执行覆盖数组长度最长的操作即可,这样就可以一定程度上减少操作次数,从而提高程序运行效率。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100052;
int a[maxn];
bool cmp(int x, int y) { return x > y; }
struct Oper {
int pos, op;
};
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
a[i] = i + 1;
}
// 读取操作列表
vector<Oper> opList;
for (int i = 0; i < m; i++) {
Oper temp;
scanf("%d%d", &temp.op, &temp.pos);
opList.push_back(temp);
}
// 操作去重转变成01交错的操作序列
vector<Oper> newList;
Oper curOp = opList[0];
for (unsigned int i = 0; i < opList.size(); i++) {
if (curOp.op != opList[i].op) { // 操作01转换则保存当前等价操作并重新记录
newList.push_back(curOp);
curOp = opList[i];
continue;
}
if (opList[i].op == 0 && opList[i].pos > curOp.pos) {
curOp = opList[i];
}
if (opList[i].op == 1 && opList[i].pos < curOp.pos) {
curOp = opList[i];
}
}
newList.push_back(curOp);
// 模拟执行操作
for (unsigned int i = 0; i < newList.size(); i++) {
if (newList[i].op == 0) {
sort(a, a + newList[i].pos, cmp);
} else {
sort(a + newList[i].pos - 1, a + n);
}
}
// 打印结果
for (int i = 0; i < n; i++) {
if (i != 0) {
printf(" ");
}
printf("%d", a[i]);
}
return 0;
}
试题 J: 括号序列
问题描述
解析
- 涉及知识点:动态规划,取模
- 动态规划设计:
- 状态设计:
d
p
(
i
,
j
)
dp(i,j)
i
i
j
j
- 状态转移方程:
d
p
(
i
,
j
)
=
d
p
(
i
−
1
,
j
−
1
)
dp(i,j) = dp(i-1,j-1)
s
t
r
i
str_i
d
p
(
i
,
j
)
=
∑
k
=
0
j
+
1
d
p
(
i
−
1
,
k
)
dp(i,j) = sum_{k=0}^{j+1}dp(i-1,k)
s
t
r
i
str_i
- 状态转移优化:当
s
t
r
i
str_i
d
p
(
i
,
j
−
1
)
=
∑
k
=
0
j
d
p
(
i
−
1
,
k
)
dp(i,j-1) = sum_{k=0}^{j}{dp(i-1,k)}
d
p
(
i
,
j
)
=
d
p
(
i
−
1
,
j
+
1
)
+
d
p
(
i
,
j
−
1
)
dp(i,j) = dp(i-1,j+1) + dp(i,j-1)
O
(
n
)
O(n)
O
(
1
)
O(1)
- 初始状态:
d
p
(
0
,
0
)
=
1
dp(0,0) = 1
- 状态设计:
- 注意事项:要增加
v
i
s
vis
d
p
dp
0
0
d
p
dp
d
p
dp
0
0
0
0
0
0
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5052;
const long long int MOD = 1e9 + 7;
int dp[maxn][maxn];
bool vis[maxn][maxn];
char str[maxn];
int n;
long long int mod(long long int x) { return x % MOD; }
long long int GetAns() {
memset(dp, 0, sizeof dp);
memset(vis, 0, sizeof vis);
dp[0][0] = 1;
vis[0][0] = true;
for (int i = 1; i <= n; i++) {
if (str[i - 1] == '(') {
for (int j = 1; j <= n; j++) {
dp[i][j] = dp[i - 1][j - 1];
vis[i][j] = vis[i - 1][j - 1];
}
} else {
dp[i][0] = mod(dp[i - 1][0] + dp[i - 1][1]);
vis[i][0] = vis[i-1][0] | vis[i-1][1];
for (int j = 1; j <= n; j++) {
dp[i][j] = mod(dp[i - 1][j + 1] + dp[i][j - 1]);
vis[i][j] = vis[i - 1][j + 1] | vis[i][j - 1];
}
}
}
for (int i = 0; i <= n; i++) {
if (vis[n][i] != 0) {
return dp[n][i];
}
}
return -1;
}
int main() {
scanf("%s", str);
n = strlen(str);
long long int ansL = GetAns();
reverse(str, str + n);
for (int i = 0; i < n; i++) {
if (str[i] == ')') {
str[i] = '(';
} else {
str[i] = ')';
}
}
long long int ansR = GetAns();
printf("%lldn", mod(ansL * ansR));
return 0;
}
获取更多题解,算法讲解欢迎关注公众号:算法梦工厂