A - Space Station

B - Monitored Area

C - Optimal Strategy

Solution

最大值的个数为奇数时先手必定选取，转换为偶数的情况。
当任意一个人选取时，另一个人必定跟随选取。

考虑讲元素按从小到大添加计算。当前为 $n$ 个元素的方案数 $f$，加入 $c$ 个相同的更大的元素：新的方案数为 $f' = f \times c! \times \binom{n + \lfloor c/2 \rfloor}{n}$ 。

Code

D - Arithmetic Sequence

Solution

假设等差数列为 $ki + b$，那么答案为 $a_i - ki$ 到 $b$ 的距离和。
记 $f(k)$ 为固定 $k$，$b$ 可变时取得的最小值。（可以 $O(n)$ 计算。）

可以发现 $\lim \limits _{k \to \pm \infty} f(k) \to + \infty$，猜测 $f$ 为上凹函数。
考虑证明 $2f(k) \leq f(k - 1) + f(k + 1)$。

$2f(k) = \sum \left | 2t_i - 2b_0 \right |$
$f(k - 1) = \sum \left | t_i + i - b_1 \right |$
$f(k + 1) = \sum \left | t_i - i - b_2 \right|$
$f(k - 1) + f(k + 1) \geq \sum \left | 2t_i - b_1 - b_2 \right | \geq 2f(k)$

因此可以用三分解决问题，总时间复杂度为 $O(nlogw)$ 。

Code

E -Insidemen

F - Neural Network Counting

G - Happy Alice

H - Game Coin

I - Permutation Pair

J - Determinant

Solution

使用浮点数计算精度不够。使用整型复杂度额外带个 $\log$ 且位数过多。

取模计算？🤔 怎么判断绝对值？

$+x \equiv -x \pmod p$ 当且仅当 $(p \mid x) \lor (p = 2x)$ 时成立。

于是我们只需要找一些特殊的模数稍加计算即可。

特别的，$\operatorname{odd}(p) \land (p \nmid x)$ 时，$odd(+x) = even(-x)$ 。

Code

Search for Mafuyu

花了很久的时间想最优的贪心策略，🤡 但是实际上任意顺序都是相同的。

Solution

比较明显遍历的顺序一定是个欧拉序。

遍历子树 $v$ 并返回一共需要花费 $2siz(v)$ 步（每条边走两次）。
于是可以知道交换子树的遍历顺序，答案不变。

也就是说按任意顺序 $\operatorname{dfs}$ 并计算就可以得到答案。

Code

L - Strange Series

M - Coloring Rectangles