Atcoder Regular Contest 121
这场是和蛤蛤一起开的毒瘤场, 让我对 $\text{Atcoder}$ 有了不好的看法.
前三题均为 $\color{green}{\text{[EASY]}}$ , 但都很诈骗, 非常离谱, 后面的题大致思考方向没啥问题, 但到关键步骤都有点思考不下去, 还是菜吧.
$\text{[ARC121D]1 or 2}$
$\color{green}{\text{[EASY]}}$
虽说简单, 但还是没自己想出来.
假设我们每次吃两个糖果, 并且糖果数为偶数.
直接考虑第 $i$ 大美味值的和第 $i$ 小美味值的匹配.
这是因为对于 $a \leqslant b \leqslant c \leqslant d$ 的时候, 有 $\max{(a+d,b+c)} \leqslant \max{(a+c,b+d)}$ , $\min{(a+d,b+c)} \leqslant \min{(a+c,b+d)}$ .
对于单独吃一个糖果的情况可以看作加入一个美味值为 $0$ 的糖果.
所以每次多加一个 $0$ , 代表多单吃一个糖果, 时间复杂度 $\mathcal{O}(n^2)$ .
$\text{[ARC121E]Directed Tree}$
$\color{green}{\text{[EASY]}}$
这题想到大体思路和做法都很简单, 但是 $dp$ 确实扯不清.
考虑容斥, 令 $f(S)$ 为, $\forall i \in S$ , $a_i$ 严格在 $i$ 的子树中的排列数, 答案即 $\sum\limits_{S \subseteq [1,n]}{(-1)^{|S|}f(S)}$ .
考虑 $dp$ , 令 $f_{i,j}$ 表示以 $i$ 为根的子树中 $\sum\limits_{x \in S 且 x 在 i 的子树中}{1} = j$ 的方案树, 最终答案就是 $\sum\limits_{i=1}^n{(-1)^i(n-i)!f_{1,i}}$ .
因为对于 $i \not \in S$ 有 $(n-i)!$ 种.
转移方程即 $f_{i,j+k} = \sum{f_{i,j}f_{son,k}}$ , 最终再把 $i$ 加入 $S$ , 即 $f_{i,j} = f_{i,j}+(size_i-j)f_{i,j-1}$ .
时间复杂度 $\mathcal{O}(n^2)$ .
$\text{[ARC121F]Logical Operations on Tree}$
$\color{green}{\text{[EASY]}}$
特判 $n=1$ .
考虑确定权值之后怎么判定是否合法.
考虑一个度为 $1$ 的点, 对其分类讨论:
$1 \lor$ , 显然只要最后选这条边即可.
$1 \land$ 或 $0 \lor$ , 显然这种边没意义, 可以直接选.
$0 \land$ , 将最终结果变成 $0$ , 显然不如直接将初始值变为 $0$ , 所以也可以直接选.
综上, 有以下策略, 若存在 $1 \lor$ 的边一定合法, 否则不断选度数为 $1$ 的边即可.
然后就可以 $dp$ 了, 令 $f_{x,0/1/2}$ 表示以 $x$ 为根的子树中, 最终的权值为 $0/1$ , 且为出现 $1 \lor$ 的方案数, 和出现 $1 \lor$ 的方案数.
初始状态为 $f_{x,0} = f_{x,1} = 1$ .