2022 题面题解
这次比赛较水，巨佬们不是 AK 就是
94
94
94。我也 AK 了
我太菜了
P1 @@
题面
给定两个数
a
a
a 和
b
b
b，求
∑
i
=
0
len
(
a
)
∑
j
=
0
len
(
b
)
a
i
×
b
j
\sum_{i=0}^{\text{len}(a)}\sum_{j=0}^{\text{len}(b)}a_i\times b_j
i=0∑len(a)?j=0∑len(b)?ai?×bj?
样例
题解
直接模拟。
for(int i = 0;i < a.length();i++){
for(int j = 0;j < b.length();j++){
ans += (a[i] - '0') * (b[j] - '0');
}
}
P2 暗号
题面
给出
x
1
,
x
2
,
x
n
x_1, x_2, x_n
x1?,x2?,xn?，求
x
x
x，满足
x
x
x 是一个等差数列并求和。
注意：超过三项只显示前两项和最后一项，中间用 ... 省略。
样例
| 样例输入 | 样例输出 |
|---|
1 2 3 | 1+2+3=6 | -3 -2 0 | (-3)+(-2)+...+0=-6 |
保证
x
2
≠
x
n
x_2 \neq x_n
x2??=xn?。
题解
求出公差
d
=
x
2
?
x
1
d=x_2-x_1
d=x2??x1?。
用公式套就行了。
P3 偶遇
题面
给出
19
×
19
19\times 19
19×19 方格边上的两个点，求只沿着边走两个点的距离。
也就是说，从一个点到另一个点沿着边走至少要走多长。
样例
咕咕咕
题解
直接沿着边模拟就行了。
需要按照边判断位移增量。
int dir(int x, int y){
if(x == 1 && y == 19){
return ...
}
else if(x == 1 && y == 1){
return ...
}
else if(x == 19 && y == 19){
return ...
}
else if(x == 19 && y == 1){
...
}
else if(x == 19){
...
}
else if(x == 1){
...
}
else if(y == 1){
...
}
else{
...
}
}
然后求得
a
n
s
ans
ans，输出的不是
a
n
s
ans
ans，而是
min
?
(
a
n
s
,
72
?
a
n
s
)
\min (ans, 72 - ans)
min(ans,72?ans)。
P4 小数化分数
题面
给出一个小数，求它的最简分数值。循环节用括号表示。
（接下来是一堆介绍小数化分数的知识）
样例
| 样例输入 | 样例输出 |
|---|
0.125 | 1/8 | 0.(3) | 1/3 | 3.(142857) | 22/7 |
题解
模拟过程即可，除以它们的
gcd
?
\gcd
gcd 即可得到答案。
P5 整数拆分
题面
给出两个数
n
,
k
n,k
n,k，要把
n
n
n 看作字符串拆成若干段，给这些段求和。
求这些和中不超过
k
k
k 的数的最大值并输出方案。
如果没有拆法，输出 none。如果有多种，输出 many。
样例
| 样例输入 | 样例输出 |
|---|
1236 40 | 1+2+36=39 | 111 2 | none | 111 12 | many |
题解
大爆搜即可。
伪代码如下：
dfs(step, sum, lst):
if(step == n):
判断，记录
将节点记录
dfs(step + 1, sum + lst, si)
还原
dfs(step + 1, sum, lst * 10 + si)
P6 停车
题面
给出
n
n
n 个正整数
a
1
,
a
2
,
…
,
a
n
a_1,a_2,\dots,a_n
a1?,a2?,…,an?，要取出若干不相邻的数，求和的最大值。
题解
DP。
d
p
i
dp_{i}
dpi? 为当前的数为止，和的最大值。
d
p
i
=
max
?
(
d
p
i
?
1
,
d
p
i
?
2
+
a
i
)
dp_i = \max (dp_{i-1},dp_{i-2}+a_i)
dpi?=max(dpi?1?,dpi?2?+ai?)
|