CodeForces1244
A.Pens and Pencils
唯一的难度在于读题,$⑧$ 说了.
B.Rooms and Stairscases
$⑧$ 说了,$\Theta(1)$ 好题.
答案就是:
从右边走到最左边的梯子上/下楼之后走回右边,从左边走到最右边的梯子上/下楼之后走回左边,从左边一路走向右边取 $max$ 即可.
C.The Football Season
咕咕咕…
D.Paint the Tree
你发现大于等于二叉的树都无解…
只需要考虑一条链的情况.
但这时!我 $TM$ 在想 $DP$ .
令 $f_{i,0/1/2}$ 表示到第 $i$ 个点颜色为 $0/1/2$ 的最优解…
这应该是对的,但我在一遍没写对且发现了更好做的做法(正解)的情况下放弃了它.
正解:
先说复杂度,$\Theta(3!\times n)$ 也就是 $\Theta(n)$.
你发现,你如果确定了链端的三个点的颜色,其后所有的点只能按这个颜色顺序排列,否则不合法.
所以你就枚举前三个点的颜色种类(其实就是三的全排列),然后 $\Theta(n)$ 统计答案即可.
E.Minimizing Difference
咕咕咕…
F.Chips
咕咕咕…
G.Running in Pairs
咕咕咕…