2020CSP-S1答案解析及总结
文章目录
P r e p a r a t i o n Preparation Preparation
回想以前的初赛经历，小学五年级第一次去初赛，差0.5分进普及组复赛，六年级因为特殊原因缺席了
初一第一次挤进普及组复赛，初二初三普及组就比较顺利了，初三挤进了提高组，分数还是挺悬的，讲真对这次初赛没有特别大的把握
于是9.17的时候就开始备战初赛了，起初是做做历年的NOIP，当然成绩不是很理想，开始整理错题复习知识点，写了一个错题本，说实话这个东西确实对我的帮助很大，特别是在修电脑的知识方面。。。
10/05开始正式天天做初赛，第一做了91.5（这辈子第一次初赛上90QwQ），第二次只有76，第三次又搞到了89，然后洛谷初赛做到了94，兴奋地写了题解，没想到看的人挺多的QwQ
然后间歇的刷刷复赛题，就到考试日了。。。
F e e l i n g Feeling Feeling
早上快八点出发去考点，到的时候和各位大佬复习了一下错题（中间趁上厕所的时间甚至开了一把单挑？？？）
然后做的总的来说还可以吧，由于监考人员的失误，大概开考5分钟了才正式做题，不过无关紧要。
今年是第一年初赛用答题卡的呢，时间还是有点紧
阅读2之前的题都很简单，做得很快，阅读2、3自闭了，完善1和2勉强能做到接近满分吧。。。
今年的阅读出奇的难，我这种菜鸡估计只有80+了
如果觉得作者太菜了的大佬轻点喷，给我留点面子QwQ
S o l u t i o n s Solutions Solutions
1~5
1：四个选项分别是，A 550、B 511、C 1024、D 558
2：定义题，没啥好说的
3：8分钟=480秒，每秒24帧，对应11520帧。每一帧都是
2048
×
1024
2048\times 1024
2048×1024的像素，且有32位，32位对应4B，相乘得到
11520
×
2048
×
1024
×
4
B
11520\times 2048\times 1024\times 4B
11520×2048×1024×4B，三项分别提取一个1024，得到
11.25
×
2
×
1
×
4
G
B
=
90
G
B
11.25\times 2\times 1\times 4 GB=90GB
11.25×2×1×4GB=90GB
4：如图，最后栈中只剩下a和c，a是栈底，c是栈顶
5：A选项7和18会冲突，B选项7和18会冲突，C选项7和18会冲突。。。
6
单独放出来不是因为它有多难或多重要，只是因为它占了两页。。。
7~15
7：每个点和每条边只会被遍历一次
8：左右侧各12各点，左侧的每个点都能向右连12条边，所以是
12
×
12
=
144
12\times 12=144
12×12=144
9：常识题
10：可以暴力求解，也可以像我考场一样列
C
R
T
CRT
CRT
{
x
≡
2
(
m
o
d
3
)
x
≡
3
(
m
o
d
5
)
x
≡
4
(
m
o
d
7
)
\left\{\begin{matrix} x\equiv 2 & (\mod\ 3)\\ x\equiv 3 & (\mod\ 5)\\ x\equiv 4 & (\mod\ 7) \end{matrix}\right.
⎩⎨⎧x≡2x≡3x≡4(mod 3)(mod 5)(mod 7)
M
=
3
×
5
×
7
=
105
M=3\times 5\times 7=105
M=3×5×7=105
M
1
=
M
3
=
35
M_1=\frac M3=35
M1=3M=35，
M
1
M
1
‘
≡
1
(
m
o
d
3
)
M_1M_1^`\equiv 1(\mod 3)
M1M1‘≡1(mod3)，得
M
1
‘
=
2
M_1^`=2
M1‘=2
M
2
=
M
5
=
21
M_2=\frac M5=21
M2=5M=21，
M
2
M
2
‘
≡
1
(
m
o
d
5
)
M_2M_2^`\equiv 1(\mod 5)
M2M2‘≡1(mod5)，得
M
2
‘
=
1
M_2^`=1
M2‘=1
M
3
=
M
7
=
15
M_3=\frac M7=15
M3=7M=15，
M
3
M
3
‘
≡
1
(
m
o
d
7
)
M_3M_3^`\equiv 1(\mod 7)
M3M3‘≡1(mod7)，得
M
3
‘
=
1
M_3^`=1
M3‘=1
所以该同余方程组有最小正整数解
x
=
(
2
M
1
M
1
‘
+
3
M
2
M
2
‘
+
4
M
3
M
3
‘
)
m
o
d
M
x=(2M_1M_1^`+3M_2M_2^`+4M_3M_3^`)\mod M
x=(2M1M1‘+3M2M2‘+4M3M3‘)modM
=
(
2
×
35
×
2
+
3
×
21
×
1
+
4
×
15
×
1
)
m
o
d
105
=(2\times 35\times 2+3\times 21\times 1+4\times 15\times 1)\mod 105
=(2×35×2+3×21×1+4×15×1)mod105
=
(
140
+
63
+
60
)
m
o
d
105
=(140+63+60)\mod 105
=(140+63+60)mod105
=
263
m
o
d
105
=263\mod 105
=263mod105
=
53
=53
=53
所以，
x
∈
(
50
,
60
)
x\in(50,60)
x∈(50,60)
11：爬到第
i
i
i层需要的体力为
∑
i
=
1
i
−
1
10
i
=
10
(
i
2
−
i
)
2
\sum _{i=1}^{i-1}10i=\frac {10(i^2-i)}2
∑i=1i−110i=210(i2−i)，暴力带入计算即可
12：如图，画出这个树，然后写出后序遍历即可
13：每一个格子都能和九个格子连边，这样会多算一倍，所以是
16
×
9
2
=
72
\frac{16\times 9}2=72
216×9=72
14：显然
15：修电脑题，不多BB
阅读1
1：可以等于1000
2：如果所有
d
i
d_i
di都相等，会输出-1
3：改过来之后如果是不上升序列一定会输出-1，不改的话不一定
4：
i
,
j
i,j
i,j都判断一次
d
i
<
d
j
d_i<d_j
di<dj或
d
j
<
d
i
d_j<d_i
dj<di，其实就相当于判断
d
i
≠
d
j
d_i\neq d_j
di=dj
5：容易发现那个运算其实在二进制下是不进位的
6：自己看，反例都举在旁边了
阅读2
1：显然是
[
L
,
R
]
[L,R]
[L,R]
2：运行是不会出毛病的
3：答案应该是
l
o
g
2
n
log^2n
log2n，所以四个选项都给分
4~6：作者都错了，无法给出解析（我太菜了5555）
阅读3
1：当两串完全相同时，输出0
2~6：作者不是蒙对了就是错了，无法给出解析（我是真的菜555）
完善1
1：提示里已经给出按照
w
j
v
j
\frac {w_j}{v_j}
vjwj从大到小排序，容易看出代码里写的是冒泡排序，所以当前面的权值比后面小时，交换，即
w
j
v
j
≤
w
j
+
1
v
j
+
1
\frac {w_j}{v_j}\leq \frac{w_{j+1}}{v_{j+1}}
vjwj≤vj+1wj+1，由于是分数运算，容易有精度问题，两边同时乘
v
j
(
v
j
+
1
)
v_j(v_{j+1})
vj(vj+1)，即可得到
w
j
v
j
+
1
≤
w
j
+
1
v
j
w_jv_{j+1}\leq w_{j+1}v_j
wjvj+1≤wj+1vj
2：若体积不够或刚刚好，才需要考虑后面的
3：初始化
4：
p
r
i
n
t
(
w
,
v
)
print(w,v)
print(w,v)其实相当于输出
w
v
\frac w v
vw，之前的
c
u
r
W
curW
curW都是可以完整选走的，由于输出的时候除了
v
[
i
]
v[i]
v[i]，所以要乘下去，然后剩下的空间
（
B
−
c
u
r
V
）
（B-curV）
（B−curV）全部填上
w
[
i
]
w[i]
w[i]
5：如果能完全填满，相当于输出
c
u
r
W
curW
curW，即
c
u
r
W
1
\frac {curW}1
1curW
完善2
1：可以带入二进制下的1010去试验，发现只有
D
D
D合法，其实其相当于
x
−
=
x
&
−
x
x-=x\&-x
x−=x&−x，即
l
o
w
b
i
t
lowbit
lowbit
2：观察发现
y
y
y取走了
a
a
a的低四位，那么显然
x
x
x是要取走
a
a
a的高四位
3：我也错了QwQ
4：低位转移
5：高位转移
有问题和建议可以在下方留言