【做题笔记】CF 1400-1600 构造题

本人比较菜，所以做的 rating 很低/kk/kk/kk
欢迎各位大佬嘲讽这个蒟蒻/kk/kk/kk/kk

$ * $ 表示看了题解才过的（所以你会发现这里的大部分题后面都会有 $ * $）
实时通过率直接贴在后面

当不看题解通过率稳定在 \(50\%\) 以上就弃坑。希望早日弃坑

ABBC or BACB*

题面中给了两种操作 \(AB->BC\)，\(BA->CB\)。我们发现这两种操作的本质就是将在左边的 \(B\) 换到 右边，在右边的 \(B\) 换到左边，并且消掉一个 \(A\)。

因此一个 \(B\) 能消掉一串连续的 \(A\)。我们考虑统计 \(B\) 的个数 \(x\) 和 \(A\) 连续的串的个数 \(y\)。如果 \(x>y\) 那么显然 \(A\) 都能被消掉，否则就减去最小的一段 \(A\) 不消。

为什么是统计 B 的个数而不是连续的 B 的段数？ 因为我们发现如果是这样的一个串 \(ABBA\)，这样两边的 \(A\) 也能消掉，但 \(B\) 的段数是小于 \(A\) 的段数的。

AC: \(0\%\)

Two-Colored Dominoes*

一个比较显然的结论，如果一行需要涂色的地方是奇数那么一定无解。有解的情况只需要判断 \(L,U\) 的颜色，直接依次按照 \(WBWBWB\) 的顺序涂即可。

AC: \(0\%\)

Kolya and Movie Theatre

没看题解过掉了，可喜可贺，可喜可贺（完了太菜了）

题面像 dp，但并不是。我们发现只要确定了最后一次看电影是在哪一天就知道要减多少个 \(d\)了，再贪心的用优先队列维护最多前 \(m\) 个最大的正数的和即可。

AC: \(33.3\%\)

Dual (Easy Version)*

找到绝对值最大的 \(a[x]\)，并考虑让其他数的正负性都跟它一样，这需要 \(n-1\) 次操作。当都是正数或者负数的时候可以直接线性推一下，这依旧需要 \(n-1\) 操作。

AC: \(25\%\)