闲的想做道 *2000，于是找到了 CF1618F。
wc，我怎么会了。
o，只有绿啊，没事了。
再看看 G 吧。
wc，我怎么又会了？？？
wc，这有蓝？？？
1618F
首先，我们发现对于一个合法二进制数添加 \(0\)，相当于去除末尾所有的 \(0\) 后再翻转，即翻转后会变成 \(1\ldots 1\) 的形式。
引理：二进制数如果在非第一次操作时被添加一个 \(0\)，相当于将二进制数翻转。
对于给出的二进制数 \(1\ldots 0\)，无论第一次操作添加什么数，都会变成 \(1\ldots 1\)。此后如果添加 \(0\)，根据起初的结论，相当于将二进制数翻转。
若给出的是 \(1\ldots 1\)，可以归纳到上面的那种情况中。
于是我们对第一次操作分类讨论进行的是哪种操作，设得到的数为 \(s\)。
现在有两种操作：
-
将 \(s\) 翻转。
-
将 \(s\) 翻转后在最高位添加 \(1\)。
两种操作结合起来不难发现相当于可以在 \(s\) 的首尾加任意个 \(1\)，并且可以翻转。由于 \(s\) 的数位不会很多，暴力做一下就行。
1618G
一眼了。
对于每个物品来说，它能换得的最大价值可以通过一个链状的结构表示出来。
所以对于 \((n+m)\) 个物品排序，相邻的两个物品 \(a,b\)，\(a\rightarrow b\) 当且仅当 \(a\le b\le a+k\)，于是一个物品能获得的最大价值就是它所在链的顶部。如果一条链上 \(x\) 个物品被初始获得，那么这条链对答案的贡献就是链的前 \(x\) 个物品的价值。一开始想的用 set 启发式合并，但是查询太慢了，看题解才发现可以前缀和。
至于多测，离线以后把链合并一下就行。怎么合并？用优先队列维护两个链之间的差就行。
标签：wc,二进制,添加,物品,CF1618FG,ldots,翻转 From： https://www.cnblogs.com/BYR-KKK/p/18202709