Codeforces Round 925 (Div. 3)

比赛链接，官方题解

ID	Difficulty (0-5)	Topic	Status	Code
A	0	Greedy	Solved	A.cpp
B	0	Greedy	Solved	B.cpp
C	0	Greedy	Solved	C.cpp
D	1	Counting	Solved	D.cpp
E	1	Greedy, Games	Solved	E.cpp
F	1	Brute Force	Solved	F.cpp
G	2	Combinatorics	Solved	G.cpp

D. Divisible Pairs

给定 $x,y$ 和数列 $a_1,a_2,\dots,a_n$ ，求有多少对 $(a_i,a_j)$ 满足：

• $1\le i < j\le n$
• $a_i+a_j \mod x = 0$
• $a_i-a_j \mod y = 0$

把一个数字 $a_i$ 转化为 $(u_i,v_i)$ :
$$
\left\{
\begin{array}{l}
u_i=a_i\mod x\\
v_i=a_i\mod y\\
\end{array}
\right.
$$

根据限制条件，有 $(u_i,v_i)$ 和 $((x-u_i)\mod x,v_i)$ 匹配，map 计数即可，复杂度 $O(n\log n)$ 。

E. Anna and the Valentine’s Day Gift

每轮都是舍掉一个数的后缀 0 /保护一个数的后缀 0 。

按照后缀 0 的个数从大到小排序，然后贪心即可，复杂度 $O(n\log n)$ 。

F. Chat Screenshotss

如果 $k=1$ 一定是 YES 。

否则假设提供的前两个序列分别是 $a_1,a_2,\dots,a_n$ 和 $b_1,b_2,\dots,b_n$ 。

如果存在答案，那么答案序列一定在下列三个之中（假设 $b_j=a_1$ ）：

• $a$ 就是答案序列：$a_1,a_2,\dots,a_n$
• $a$ 不是答案序列，并且答案序列中 $a_1$ 不在 $b_1$ 后： $a_2,a_3,\dots,a_i,a_1,a_{i+1},\dots,a_n \ (a_i=b_{j-1})$
• $a$ 不是答案序列，并且答案序列中 $a_1$ 在 $b_1$ 后： $a_2,a_3,\dots,a_i,a_1,a_{i+1},\dots,a_n\ (a_i=b_1)$

check 就直接暴力的 $O(nk)$ 即可。

G. One-Dimensional Puzzle

观察到 $3,4$ 只是起类似于继承的关系，比如一个向右的突起可以接任意多个 $3$ 。

如果 $1,2$ 都没有，那么 $3,4$ 只能存在一种。

如果 $1,2$ 至少有一个，那么 $3,4$ 一定能用完，且 $3,4$ 的方案数相当于装箱计数。

如果 $1,2$ 不一样多，只有 $|c_1-c_2|=1$ 时有解，且 $1,2$ 的排列方式唯一，答案就是 $3,4$ 方案数乘积。

如果 $1,2$ 一样多，那么有两种排列 $1,2$ 的方法，分别计算对应的 $3,4$ 方案数求和即可。