2021年第十二届蓝桥杯省赛A组题解(C/C++)
2021年蓝桥杯省赛A组题解(C/C++)
来自微信公众号:算法梦工厂,二维码见文末。
A:卡片
问题描述
答案:3181
解析
- 涉及知识点:枚举,十进制拆分
- 做法:初始化 res_num 数组记录当前每种卡牌剩余数量,从1向上枚举需要组合的卡片,直到剩余卡片不足则停止累加,最后成功组合成的卡片即为答案。
代码
#include <bits/stdc++.h>
using namespace std;
vector<int> Split(int 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) {
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) {
vector<int> need = Split(ans);
bool succFlag = Sub(need);
if (!succFlag) {
break;
}
ans++;
}
printf("ans = %dn", ans - 1);
return 0;
}
B:直线
问题描述
答案: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) {
return sqrt((p0.x - p1.x) * (p0.x - p1.x) + (p0.y - p1.y) * (p0.y - p1.y));
}
bool CheckPointInLine(Line x, Point p) {
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;
}
}
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;
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;
}
C:货物摆放
问题描述
答案:2430
解析
- 涉及知识点:质因数分解
- 做法:
- 问题可以转化成,将
2021041820210418
2021041820210418
a
∗
b
∗
c
a*b*c
- 将
2021041820210418
2021041820210418
p
0
n
u
m
0
∗
p
1
n
u
m
1
∗
.
.
.
∗
p
n
n
u
m
n
p_0^{num_0} * p_1^{num_1} * ... * p_n^{num_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;
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;
}
D: 路径
问题描述
答案: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];
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));
}
}
}
}
void Floyd() {
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];
}
}
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]);
}
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;
}
E: 回路计数
问题描述
答案:881012367360
解析
- 涉及算法:最大公约数,动态规划,状态压缩
- 做法:
- 状态设计:
d
p
(
s
t
a
t
e
,
p
o
s
)
dp(state, pos)
p
o
s
pos
s
t
a
t
e
state
s
t
a
t
e
state
21
21
i
i
0
0
i
i
1
1
i
i
- 状态转移方程:
d
p
(
s
t
a
t
e
,
p
o
s
)
=
∑
i
=
0
i
<
21
d
p
(
s
t
a
t
e
−
2
p
o
s
,
i
)
dp(state, pos) = sum_{i=0} ^{i<21} dp(state-2^{pos}, i)
i
+
1
i+1
p
o
s
+
1
pos+1
s
t
a
t
e
state
i
i
p
o
s
pos
1
1
- 初始状态:
d
p
(
1
,
0
)
=
1
dp(1,0) = 1
- 设
f
(
x
)
f(x)
0
0
x
x
f
(
x
)
=
d
p
(
2
21
−
1
,
x
)
f(x) = dp(2^{21}-1, x)
a
n
s
=
∑
i
=
0
i
<
21
f
(
x
)
=
∑
i
=
0
i
<
21
d
p
(
2
21
−
1
,
x
)
ans = sum_{i=0}^{i<21}f(x) = sum_{i=0}^{i<21}dp(2^{21}-1, x)
- 状态设计:
实际网络结构图
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 21;
long long int dp[1 << maxn][maxn];
bool IsPosVis(int state, int pos) {
if ((state & (1 << pos)) != 0) {
return true;
} else {
return false;
}
}
bool IsConnect(int x, int y) {
if (x == 0 || y == 0) {
return true;
}
if (__gcd(x + 1, y + 1) == 1) {
return true;
} else {
return false;
}
}
long long int f(int state, int finalPos) {
if (dp[state][finalPos] != -1) {
return dp[state][finalPos];
}
if (!IsPosVis(state, finalPos)) {
return dp[state][finalPos] = 0;
}
long long int ret = 0;
for (int net = 0; net < maxn; net++) {
if (!IsPosVis(state, net)) {
continue;
}
if (!IsConnect(net, finalPos)) {
continue;
}
ret += f(state - (1 << finalPos), net);
}
return dp[state][finalPos] = ret;
}
int main() {
memset(dp, -1, sizeof(dp));
long long int ans = 0;
int finalState = (1 << (maxn)) - 1;
dp[1][0] = 1;
for (int i = 0; i < maxn; i++) {
long long int temp = f(finalState, i);
printf("%d %d %d %lldn", IsConnect(i, 0), finalState, i, temp);
ans += temp;
}
printf("ans = %lldn", ans);
return 0;
}
F: 砝码称重
问题描述
解析
-
涉及知识点:动态规划,类背包问题
-
思路一:问题可以转化成:给定
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;
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);
}
int ans = 0;
for (int i = offset + 1; i < maxn; i++) {
if (vis[pre][i]) {
ans++;
}
}
printf("%d", ans);
return 0;
}
G: 异或数列
问题描述
解析
注:题目中少描述了一个信息就是,
A
A
A 和
B
B
B 初始的数值都是
0
0
0 。
- 涉及知识点:博弈,二进制拆分,思维分析
- 分析过程:
- 首先考虑到所有数字最后都会异或到
A
A
B
B
A
⨁
B
=
x
0
⨁
x
1
⨁
.
.
.
⨁
x
n
−
1
A bigoplus B = x_0 bigoplus x_1 bigoplus ... bigoplus x_{n-1}
0
0
A
l
i
c
e
Alice
B
o
b
Bob
A
A
B
B
- 其次,如果所有数字异或不同,那么异或和
s
u
m
sum
0
0
0
0
c
n
t
0
cnt0
0
0
c
n
t
1
cnt1
1
1
A
l
i
c
e
Alice
1
1
0
0
c
n
t
0
+
c
n
t
1
cnt0+cnt1
A
l
i
c
e
Alice
c
n
t
0
+
c
n
t
1
cnt0+cnt1
B
o
b
Bob
- 同时要考虑一个意外情况就是当
c
n
t
1
cnt1
1
1
A
l
i
c
e
Alice
1
1
c
n
t
0
cnt0
c
n
t
1
=
1
cnt1=1
A
l
i
c
e
Alice
B
o
b
Bob
- 首先考虑到所有数字最后都会异或到
代码
#include <bits/stdc++.h>
using namespace std;
int num[50] = {0};
void add(int x) {
int cnt = 0;
while (x > 0) {
if (x & 1) {
num[cnt]++;
}
cnt++;
x >>= 1;
}
}
int main() {
int T, n, a, b;
scanf("%d", &T);
while (T--) {
int xorSum = 0, temp;
memset(num, 0, sizeof(num));
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &temp);
add(temp);
xorSum ^= temp;
}
if (xorSum == 0) {
printf("0n");
continue;
}
int ans = 0, pos = 0;
for (int i = 30; i >= 0; i--) {
if (num[i] & 1) {
pos = i;
break;
}
}
if (n & 1 || num[pos] == 1) {
printf("1n");
} else {
printf("-1n");
}
}
return 0;
}
H: 左孩子右兄弟
问题描述
解析
- 涉及知识点:树存储、树形动态规划
- 解析:可以发现左孩子右兄弟的存储方法,对于树上的一个节点,它的所有儿子都会按照某种顺序依次成为它的右儿子,右儿子的右儿子,右儿子的右儿子的右儿子…依次类推深度不断增加。所以这里就有一个递归的结论:对于一个节点,只有把它的所有儿子形成的子树中,转化为二叉树深度最深的儿子放到最下边,才会最优。所以对于每个结点的所有儿子顺序选择,只需要选择它的儿子形成的子树中转化成二叉树高度最高的放到最后边就能得到最优答案。
- 动态规划设计:
- 状态设计:
d
p
(
x
)
dp(x)
- 状态转移方程:
d
p
(
x
)
=
m
a
x
{
d
p
(
u
)
+
s
i
z
e
(
x
)
∣
u
是
i
的
儿
子
}
dp(x) = max{dp(u) + size(x)| u是i的儿子}
s
i
z
e
(
x
)
size(x)
- 初始状态:当
x
x
d
p
(
x
)
=
1
dp(x) = 1
- 状态设计:
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100052;
int fa[maxn], n;
vector<int> u[maxn];
int dfs(int x) {
int ret = 1;
for (int i = 0; i < u[x].size(); i++) {
int temp = 1 + dfs(u[x][i]) + u[x].size() - 1;
ret = max(temp, ret);
}
return ret;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n - 1; i++) {
scanf("%d", &fa[i]);
u[fa[i]].push_back(i + 2);
}
printf("%dn", dfs(1) - 1);
return 0;
}
I: 括号序列
问题描述
解析
- 涉及知识点:动态规划,取模
- 动态规划设计:
- 状态设计:
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;
}
J: 分果果
问题描述
解析
- 涉及知识点:动态规划,单调栈优化
- 分析:该题目正解为动态规划+单调栈优化,但是难度较高,此处给出一个相对简单的暴力枚举方法,可以通过部分样例。
- 暴力搜索做法:枚举每个小朋友选择的糖的区间,判断是否合法,记录所有合法的选择中的最小值即为答案。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 152;
int n, m, w[maxn], rest[maxn];
bool Check(int l, int r) {
while (l <= r) {
if (rest[l] == 0) {
return false;
}
l++;
}
return true;
}
int dfs(int child, int curMax, int curMin) {
if (child == m) {
for (int i = 0; i < n; i++) {
if (rest[i] == 2) {
return 0x3f3f3f3f;
}
}
return curMax - curMin;
}
int ret = 0x3f3f3f;
for (int l = 0; l < n; l++) {
for (int r = l; r < n; r++) {
if (!Check(l, r)) {
continue;
}
int sum = 0;
for (int i = l; i <= r; i++) {
sum += w[i];
rest[i]--;
}
int temp = dfs(child + 1, max(curMax, sum), min(curMin, sum));
for (int i = l; i <= r; i++) {
rest[i]++;
}
ret = min(ret, temp);
}
}
return ret;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
scanf("%d", &w[i]);
rest[i] = 2;
}
int ans = dfs(0, -0x3f3f3f, 0x3f3f3f);
printf("%dn", ans);
return 0;
}
获取更多题解,算法讲解欢迎关注公众号:算法梦工厂