文章目录
CSP-J 2020题解
A
Solution
直接说正解。
首先，如果
n
n
n
是个奇数，那么应该输出
−
1
-1
−
1
，因为必须有
1
1
1
的参与才可以满足要求，但是不能有
1
1
1
的参与。
否则，我们对
n
n
n
进行二进制拆分，从大到小输出每一个该位为
1
1
1
的位权即可。
时间复杂度
O
(
log
n
)
O(\log n)
O
(
lo
g
n
)
。
Summary
这题的坑点并不多，有那么一点点”思维含量”，而不是往年PJ T1的大水题；是一道清新的签到题。
考场上大家都切掉了吧~
花絮
忍不住要吐槽一下，看到这题目名字的时候我瞬间就慌了，想到了某年NOI的一道”优秀的拆分”，
而那却是一个需要后缀数组优化的神仙哈希
黑
题
……后来仔细看完了题目才不那么慌。希望大家不要用题目名字来辨认难度！更不要想到之前的同名题目！
B
Solution
Subtask 1: 50pts
从前往后扫，每加入进来一个数就重新排序；每次输出对应排名的分数即可。
时间复杂度
O
(
n
2
l
o
g
n
)
O(n^2 logn)
O
(
n
2
l
o
g
n
)
。
Subtask 2: 100pts(
n
≤
1
0
5
,
a
i
≤
600
n≤10^5, a_i≤600
n
≤
1
0
5
,
a
i
≤
6
0
0
)
做法一: 采用双向链表，先将所有数排序然后依次插入双向链表。从后往前扫，链表每次
O
(
1
)
O(1)
O
(
1
)
删除；由于每次数只会少一个，所以需要查询的排名最多只会变一位，我们只需要用双向链表
O
(
1
)
O(1)
O
(
1
)
查询前后继即可。
时间复杂度
O
(
n
)
O(n)
O
(
n
)
。
做法二: 每次桶排序，时间复杂度
O
(
600
n
)
O(600n)
O
(
6
0
0
n
)
。控制不好会被卡常。
做法三: 二分套树状数组/树状数组上倍增
我考场上一秒想到的做法，然后就写了
首先，我们维护一个桶；从前往后扫，每次在桶内进行单点修改。每次查询的时候，我们二分答案，每次
c
h
e
c
k
check
c
h
e
c
k
的时候使用资瓷查询前缀和的树状数组来快速求出这个排名，从而决定二分上下界的变化。
二分套树状数组的时间复杂度为
O
(
n
log
2
600
)
O(n \log^2 600)
O
(
n
lo
g
2
6
0
0
)
，
树状数组内倍增的时间复杂度为
O
(
n
log
600
)
O(n \log 600)
O
(
n
lo
g
6
0
0
)
。
我又开始大炮轰蚊子了
Summary
相比往年的
T
2
T2
T
2
，难度基本一样，但是考察了基本算法而不是纯模拟。
可以说是一道清新的签到题。
C
Solution
直接说正解。
首先，我们将这个表达式读入进来，建立一棵表达式树。
别跟我说不会，老师讲过的
可以发现这是一棵二叉树，且叶子节点是一个值。
我们先将这棵树给
d
f
s
dfs
d
f
s
一遍，
d
p
i
dp_i
d
p
i
表示以
i
i
i
为根的子树的表达式的值。
然后我们开始挖性质。假设当前树上
d
f
s
dfs
d
f
s
到的节点为
x
x
x
，左孩子为
l
l
l
，右孩子为
r
r
r
。
①如果节点
x
x
x
的符号为&：
(1)如果
d
p
l
=
0
dp_l=0
d
p
l
=
0
，那么所有在
r
r
r
子树内发生的翻转操作都不会产生任何影响，即表达式的值不变。原因是，
0
0
0
与任何数做与操作的值都是
0
0
0
。
(2)同理，如果
d
p
r
=
0
dp_r=0
d
p
r
=
0
，那么所有在
l
l
l
子树内发生的翻转操作都不会产生任何影响，即表达式的值不变。
②如果节点
x
x
x
的符号为
∣
|
∣
：
(1)如果
d
p
l
=
1
dp_l=1
d
p
l
=
1
，那么所有在
r
r
r
子树内发生的翻转操作都不会产生任何影响，即表达式的值不变。原因是，
1
1
1
与任何数做或操作的值都是
1
1
1
。
(2)同理，如果
d
p
r
=
1
dp_r=1
d
p
r
=
1
，那么所有在
l
l
l
子树内发生的翻转操作都不会产生任何影响，即表达式的值不变。
我们可以通过
d
f
s
dfs
d
f
s
的方式，求出每个节点的翻转操作是不是一定不会影响答案；如果会影响当且仅当不存在任何该节点的祖先满足上面的情况。
于是，我们通过
O
(
∣
s
∣
)
O(|s|)
O
(
∣
s
∣
)
的预处理(输入，转表达式树，树上
d
f
s
dfs
d
f
s
)，每次可以
O
(
1
)
O(1)
O
(
1
)
查询。总时间复杂度
O
(
∣
s
∣
+
n
+
q
)
O(|s|+n+q)
O
(
∣
s
∣
+
n
+
q
)
。
Summary
一道不错的表达式题。作为PJ T3感觉难度有点大……我太菜了，考场最后花了
2
h
2h
2
h
才把这题绝杀肝出来。
考察了表达式的输入以及表达式树的应用，较为综合。在考场上A掉这题有一定的难度，需要代码能力(比如我就几乎没有)，需要思维能力(观察能力，挖性质能力)。
一定要会后缀表达式的输入啊啊啊啊啊啊啊啊啊啊啊啊
花絮
洛谷数据目前有问题，别信，去计蒜客、牛客上测测看。
D
Solution
Subtask 1: 70pts
这题发现有一个重要的条件:
我们只能向上，向下或向右走一格。
所以，我们不能向左走！所以，在列维度是无后效性的，但是在行维度是有的。同时，
任何一个节点最多只能经过一次
，也就是说，在一列上我们一定是走了连续的一段区间，但是有可能向上走，也有可能向下走。
状态设计:
d
p
i
,
j
dp_{i,j}
d
p
i
,
j
表示从
(
i
,
j
)
(i,j)
(
i
,
j
)
走到右下角的最大和。
状态转移: 我们按照列
倒序枚举
。假设目前看到的是第
i
i
i
行第
j
j
j
列，我们枚举在这一列上，从
j
j
j
出发走到了哪里。
状态转移:
d
p
i
,
j
=
max
1
≤
k
≤
n
d
p
k
,
j
+
1
+
∑
q
=
m
i
n
(
i
,
k
)
m
a
x
(
i
,
k
)
a
q
,
j
dp_{i,j}=\max_{1≤k≤n}{dp_{k,j+1}+\sum_{q=min(i,k)}^{max(i,k)} a_{q,j}}
d
p
i
,
j
=
max
1
≤
k
≤
n
d
p
k
,
j
+
1
+
∑
q
=
m
i
n
(
i
,
k
)
m
a
x
(
i
,
k
)
a
q
,
j
。
使用前缀和优化即可。
时间复杂度
O
(
n
2
m
)
O(n^2m)
O
(
n
2
m
)
。
Subtask 2: 100pts
既然状态的数量并不多，但是状态转移并不是
O
(
1
)
O(1)
O
(
1
)
的；我们套路性地考虑如何优化状态转移。
定义
p
r
e
i
pre_{i}
p
r
e
i
表示这一列上前
i
i
i
个数的和，目前我们想要求出这一列上第
j
j
j
个的
d
p
dp
d
p
值。
假设
k
k
k
是
j
j
j
的决策点(不懂的话请举手，感谢)且
k
<
j
k<j
k
<
j
。此时，可以发现这个式子等于
d
p
k
,
j
+
1
+
p
r
e
k
−
p
r
e
i
−
1
=
(
d
p
k
,
j
+
1
+
p
r
e
k
)
−
p
r
e
i
−
1
dp_{k,j+1}+pre_k-pre_{i-1}=(dp_{k,j+1}+pre_k)-pre_{i-1}
d
p
k
,
j
+
1
+
p
r
e
k
−
p
r
e
i
−
1
=
(
d
p
k
,
j
+
1
+
p
r
e
k
)
−
p
r
e
i
−
1
。
于是，我们从前往后扫一遍，求出使得
d
p
k
,
j
+
1
+
p
r
e
k
dp_{k,j+1}+pre_k
d
p
k
,
j
+
1
+
p
r
e
k
最大的
k
k
k
作为
向上走
的决策点即可。注意我们这里只处理了
k
<
j
k<j
k
<
j
的情况，我们还要类似地从后往前扫一遍处理
向下走
的状态转移。
时间复杂度
O
(
n
m
)
O(nm)
O
(
n
m
)
。
Summary
一道很套路的题，放在
T
4
T4
T
4
难度偏低。
关键在于这个状态转移的优化。我们先随便推一推式子，然后从前往后、从后往前扫一遍也就可以了。
一定要开long long啊啊啊啊啊啊啊啊啊啊啊
PJ总结
一套难度中规中矩的题目，
虽然我知道自己作为菜鸡并没有多大资格评价。
考察了位运算(进制)、桶排序/链表、表达式、树、
d
p
dp
d
p
以及
d
p
dp
d
p
的简单优化，并没有超纲，但是有思维含量。涉及了各种各样的芝士点。
为良心出题人点赞！
分数线预估
1=: 215
2=: 180
3=: 150
CSP-S 2020题解
T1
Solution
啥也不想说了，说了就想哭。一道大模拟。
Summary
这题直接导致了我的退役，请大家引以为戒。
至于是如何导致我退役的，去看我的游记吧。
T2
Solution
考场上一眼切，结果挂了十分
如果对于某一位需要买饲料(即如果这一位是
1
1
1
)，但是目前还没有这样的动物(即没有动物的这一位是
1
1
1
)，那么就不能买任何这一位为
1
1
1
的动物。
显然剩下的位为
0
/
1
0/1
0
/
1
。假设这样的位有
k
k
k
个，那么答案就是
2
k
−
n
2^k-n
2
k
−
n
。特别注意一下，如果
k
=
64
k=64
k
=
6
4
，我们一定要这么特判：
①如果
n
=
0
n=0
n
=
0
，我们就输出
2
64
2^{64}
2
6
4
。这个数字可以手算；
②如果
n
>
0
n>0
n
>
0
，那么我们就输出
(
2
64
−
1
)
−
(
n
−
1
)
(2^{64}-1)-(n-1)
(
2
6
4
−
1
)
−
(
n
−
1
)
。
2
64
−
1
2^{64}-1
2
6
4
−
1
我们手算，然后减一下就可以了。
Summary
符合TG D1T1难度的一道题，考场上一定要注意到
u
l
l
ull
u
l
l
。不建议写又臭又长的高精度。
T3
Solution
考场上几乎没看这题，结果在学校里想出来了。
首先，考虑三个部分分。如果不考虑这三个部分分，就较难想到正解。
①没有第三种函数。
首先这显然可以用线段树来维护。但是有更简单的方法。
可以发现，对于一次全局乘并无大碍。对于一次单点加，假设当前加的这个数为
k
k
k
，且在这一次之后操作之后所有全局乘操作的乘量的积为
p
p
p
，那么我们这个数就要加上
k
p
kp
k
p
。换句话说，我们采用了“先乘再加”的方法，先处理了全局乘，再通过反向扫一遍维护
p
p
p
的方式来完成了单点修改。
②没有第一种函数。
首先，我们按照第三种函数建图。
u
u
u
到
v
v
v
有一条边当且仅当
u
u
u
这个函数直接调用了
v
v
v
。显然这是一个
D
A
G
DAG
D
A
G
，否则就出现了递归。
我们对于每个节点求出一个值
m
u
l
mul
m
u
l
，表示
所有可以通过这个节点到达的节点的乘量的积
。显然可以通过一次拓扑排序求出。
于是，我们维护一个
p
p
p
，对于一次询问，我们将
p
p
p
乘上我们询问的那个函数对应节点的
m
u
l
mul
m
u
l
值。最终将序列中的所有数乘
p
p
p
即可。
③没有第二种函数。
你在学校里甩锅吗？如果甩过，这个部分分非常好想。
我们对于每一个节点维护一个
t
t
t
，表示
这个函数被间接或直接调用了
t
t
t
次
。对于一次询问，在我们直接调用的函数上打上一个标记(即加
1
1
1
)；最后一遍拓扑排序，求出所有节点的
t
t
t
值，转移显然。然后做单点修改即可。
考虑正解。
我们综合一下①②③的思想，很容易得到：
(1)建图。
(2)我们先完成所有全局乘的操作。
(3)对于每个节点维护一个
t
t
t
值，等价于这个函数被调用了
t
t
t
次。
但是，这里的求
t
t
t
的方式与③中的就有点区别了。我们仍然倒序扫描询问，维护
p
p
p
表示目前扫描到的所有询问的全局乘的量；假设当前处理的这个函数是第
r
t
rt
r
t
个函数，那么我们就将
r
t
rt
r
t
对应的
t
t
t
值加上一个
p
p
p
。
最后我们采用图上拓扑的方式就可以求出每种函数被调用的次数。更详细地说，对于一个第三类函数，我们类似地倒序处理它的所有子函数，类似地维护一个
p
p
p
值表示对于当前的这个节点扫描到的子函数的
m
u
l
mul
m
u
l
值之积，注意
p
p
p
的初值为当前这个节点的
t
t
t
值。将该子函数的
t
t
t
值加上
p
p
p
。
最终单点修改即可。
总结一下：
(1)建图
(2)拓扑排序求出
m
u
l
mul
m
u
l
值；
(3)对于每一个询问打上标记，注意
倒序处理
并维护
p的值
；
(4)将所有数乘上
p
p
p
(即处理所有的全局乘的操作)；
(5)通过一遍拓扑排序，求出每个单点修改被调用的次数；
(6)处理所有单点修改。
时间复杂度
O
(
n
+
q
)
O(n+q)
O
(
n
+
q
)
。
Summary
一道套路题。综合了许多提高组的经典考点，是一道好题。
考场上我作为猛刚T1，放弃T3(100分)与T4(55分)的选手，已经2=无望，请大家为我默哀。
d
u
c
a
t
i
真
可
怜
…
…
\huge {\color {grey} {ducati}真可怜……}
d
u
c
a
t
i
真
可
怜
…
…
T4
首先
70
70
7
0
分做法很显然。
Solution
Subtask 1: 70pts
可以发现，如果一只蛇吃掉了另外一只蛇，又过了一段时间，它自己又被别的蛇吃了；那么这显然不是最优策略。
换句话说，我们每次将最大的减去最小的，记录下每一次操作涉及到的两只蛇。我们从后往前扫一遍，找到最靠前的时刻
i
n
d
e
x
index
i
n
d
e
x
，使得在这个时刻中消费者在
i
n
d
e
x
index
i
n
d
e
x
之后变成了生产者，那么答案就是
i
n
d
e
x
index
i
n
d
e
x
。
采用堆即可。时间复杂度
O
(
n
l
o
g
n
)
O(nlogn)
O
(
n
l
o
g
n
)
。如果采用手写堆并
不要脸地
采用O2优化并且大力卡常，也许可以通过。
这不是正解。
Subtask 2: 100pts
考虑优化我们找最大值以及找最小值并相减的步骤。
我们可以另外维护一个双端队列，每次存储下当前序列中的最大值减去最小值；找最小值的方法与找最大值的方法类似，这里只介绍找最大值的方法：我们可以将双端队列中的
末尾
与序列中的末尾进行比较即可。注意这里原序列的形式也应该是一个双端队列。
为什么这样是正确的？考虑，我们每次弹出的
最大值与最小值
之差是
单调不增的
。我们把这些数放进一个双端队列里面，那么这个队列就是有单调性的；由于原来序列就是有序的，而每次我们只是去掉了最大值与最小值，那么这个序列(双端队列)仍然是有序的。
在双端队列中查询开头与结尾均为
O
(
1
)
O(1)
O
(
1
)
，最后我们类比Subtask 1的方法找到最小的
i
n
d
e
x
index
i
n
d
e
x
即可；时间复杂度
O
(
n
)
O(n)
O
(
n
)
。
Summary
我们类比了蚯蚓那题的解法，使用两个双端队列解决了这道
黑
题。
作为提高组的T4，是一道难度符合，比较套路的一道性质题，略韩博弈，并且卡掉了
O
(
t
n
l
o
g
n
)
O(tnlogn)
O
(
t
n
l
o
g
n
)
的朴素解法。虽然套路，但是这仍然是一道好题。
TG总结
四道题中有三道不错的题目(真的很客观)，T1是一道害我退役的模拟题，T2是一道不错的位运算+简单性质题，T3是一道考察了图论(建图、拓扑排序)+数学(先乘再加)+
d
p
dp
d
p
的绝世好题，T4是一道略含博弈(挖性质)，然后就变成了一个套路(两个双端队列，分别拥有单调性，用来快速维护查询最大值、查询最小值等操作)题。顺便提一句，T2,4要用快读，否则可能会被卡。
你考场策略错了，就不要想拿到什么奖了(例子: ducati)。
你考场策略对了，就算你挂了一堆分，一等奖也是稳的(例子: 你们)。
所以，千万不要死磕T1，拿个
80
80
8
0
分走人就可以了(类似莫队)。
然后T2可以轻松切掉，一定要特判
64
64
6
4
的情况。没想到？那就
90
90
9
0
分吧。
剩下的时间肝
T
3
T3
T
3
，最终拿了
50
50
5
0
分，并没有想到正解(就是那几个部分分)。
然后T4轻松拿了
20
(
n
≤
3
)
20(n≤3)
2
0
(
n
≤
3
)
分，回去检查，一分没挂。
走人，
240
240
2
4
0
分，发现自己压线拿了
1
=
1=
1
=
。
可惜，我只有
10
+
90
+
0
+
0
=
100
10+90+0+0=100
1
0
+
9
0
+
0
+
0
=
1
0
0
分，可以说是大家的一个反面案例了吧。我通过血的教训证明了，时间的安排有多重要。
AFO