闲扯
今天的题太坑了, $B$ 题 $fst$ 了一堆(包括我),果然还是太捞了。
也可以到我 $Luogu$ 博客上康康 $B\sim D$ 的题解(也许会具体点??)。
题面
Codeforces Round #608 (Div. 2)
$A$
可以发现只有 $jecket$ 是共有的,直接枚举两种分别分到了几个即可。
$B$
我们需要发现两个结论:
- 对于形如 $WW,BB$ 的,我们翻转后会变成 $BB,WW$ 。
- 对于形如 $WB,BW$ 的,我们翻转后相当于交换两个字符。
然后我们分别对全部换为 $B,W$ 计算是否合法。
具体的方法为:从第二个位置开始枚举(设要换为 $c$ )
- 如果 $s_i=s_{i-1}\not=c$ ,那么直接翻转这两个。
- 如果 $s_i=c,s_{i-1}\not=c$ ,那么翻转这两个。(这是使得一个非法元素位置后移)
可以证明,如果 $\sum_{i=1}^n[s_i\not=c]$ 为偶数,那么一定有解。
$C$
易得最后的 $p$ 点,一定可以在 $(s-1,t),(s+1,t),(s,t-1),(s,t+1)$ 四个点取到。
直接统计答案即可。
$D$
我们有一个贪心策略:对于一个点 $u$ ,我们一定选择在所有能在向它派兵的位置中的最大值处派兵。
因为在前面派兵一定不会使答案更优。(如果该点不能过,那么在前面派兵更不能过)
我们设 $dp_{i,j}$ 表示当前在 $i$ 号节点,还剩了 $j$ 个兵可以派遣的最大收益,直接大力转移即可。
$E$
打表,可以发现如下规律:对于每一个对 $val$ 有贡献的位置,
- 若 $val$ 为奇数,那么一定是被分为了 $m$ 段,其中第 $i$ 段的长度为 $2^{i-1}$ ,开头位置的值为 $val\cdot 2^{i-1}$ 。
- 若 $val$ 为偶数,那么一定是被分为了 $m$ 段,其中第 $i$ 段的长度为 $2^i$ ,开头位置的值为 $val\cdot 2^{i-1}$ 。
然后对奇数和偶数分别二分,取最大值即可。