[AGC045B] 01 Unbalanced 题解

Jeefy · 2024-01-03 21:53:43 · 题解

其实看到这道题的第一眼就应该想到二分，但是这个 check 比较麻烦。

将 01 看作网格在上下，我们手模一下可能的路径，发现一定是一个区间的奇数或者偶数位置。

这是样例 0??0 的图。

现在我们需要将路径限制在一个大小为 mid 的区间内，看是否有合法路径，这很抽象，因为上下限会随着路径而改变。但是有个十分新奇的思路，我们设置 mid 个起点，限制在一个 mid 的长条内。

这是当 mid = 3 时的三条路径。

如果将三者重叠，我们会发现每一列的合法位置是一个区间：

那么我们二分的时候维护这个区间即可，但是此时我们发现样例过不去。

对于 0??0 在 k = 1 时，如果单纯的维护上下界会存在如下情况：

红色为实际的合法路径，但是我们会将黑色的两个点都算为合法进去。

这是因为在第一次加入 ? 时我们单纯的扩展了上下界，并且将溢出下界的去掉，但是忽略了恰好在下界位置的那个点没有办法取到。导致算重。

回顾 可能的路径，发现一定是一个区间的奇数或者偶数位置，那么我们可以将奇偶位置分开考虑，维护合法的区间，这样如果越过边界，那么利用 \pm 2 来修正即可。

代码非常简单：https://atcoder.jp/contests/agc045/submissions/49005863