AtCoder Beginner Contest 285

ABC 一点也不娱乐

Source

AtCoder Beginner Contest 285

D - Change Usernames

判环即可。由于本题的特殊性，可以直接用 DSU 判断。我采用 DFS 判环

由于本题图一定是由链、环、链 + 环组成的，我选择拿入度为 0 的点开始 DFS，但是在一整个环的情况下 WA 了

Code

ABC285 D

E - Work or Rest

化成多重背包问题

记 0 为 holiday，1 为 weekday。由周期性，不妨令第一天恒为 0。之后，我们把一串 holiday(s) + weekday 看作一个物体，填满空间为 $N$ 的背包（末尾多出来的 weekday 和第 $N + 1$ 天重合）

具体而言，我们有 $2N$ 种物体（虽然有些是不可能用上的），代表着 11...110 这样的一串。把这些物体合起来就成了长度为 $N + 1$ 的串 01..101..101..10，首尾的 0 为第一天和第 $N + 1$ 天

需要构造的物体形如：10，110，1110，11110 等，value 和 cost 显然

实际上我们有第 $2N + 1$ 种物体 0，也就是纯 holiday，因为我们要求一定要把背包塞满。而多重背包的方法做下来可能会有空余，默认空余由 holiday(s) 填充即可

注意是多重背包不是 01 背包

Code

ABC285 E

F - Substring of Sorted String

对于每个字母，建一棵线段树即可

Code

ABC285 F

Warnings

• submit 之前多试试边界情况