初三下——NOIP 模拟赛（6~10）

6

Conclusion

T1

注意到一次碰撞后下一次一定不会碰到，一直这样直到出去。二分找位置即可然后算一下贡献。

T2

dp 部分

重排过后肯定是 0 + 01 + 1 的形式。于是根据这个 dp。

上面的 dp 冗余在其对于段数枚举了分界点。于是我们考虑就对于当前这个元素 \(i\) 进行单独考虑。记录是否有了过渡态/第 i 个，下一个期望填什么。

转移需要点脑子。

正解部分

考虑这个东西的实质。其实就是一堆连续 01。所以我们把它们弄成 \(len\) 数组。进行选择。

然后 01 的情况就是 2 个位置。

这个问题本质上是删数，删最小。而分析一下可以知道不能删除连续的 2 个。

这样就变成了反悔贪心板题。讨论边缘即可。