[WC/CTS2023] 楼梯：用套路思维地解决思维题

feecle6418 · 2023-02-14 13:15:30 · 题解

这题要是想到“考虑右下边界”，就很容易了。可惜，想到这一点是很不容易也不”套路“的，至少我没想到。

然而，我们仍然能套路地，不需要任何思维火花地，解决本题。这也是本题解讲述的重点。

读完题，最让人迷惑的就是 q 是 p 的因数这个条件。所以，本题肯定要在这个条件上做文章。

接下来，我们考虑一些老生常谈的”思维技巧“，看能否套到这题上来。

• 主动强化题目条件，尝试增加条件让题目存在一个做法，尽管增加的条件可能相比原题太强了。要在 n^2 个格子中找到一个作为答案，是很难的；但要是强制这个格子要么在上边界上要么在左边界上，则直接用线段树维护每行的格子数，线段树上二分即可（虽然维护的是行，但是对列二分也是容易的，因为列数随行数单调变化）。

  进一步，要是我们知道答案格的上边界所在行或是左边界所在列，也容易用线段树上二分找出答案。

  自然地，我们可以猜测：一定存在一种合法的答案，使得答案格要么在上边界上要么在左边界上。但可惜，这个猜想是错的，随便画个格子就可以举出反例。但这给了我们一点提示：我们能否将找寻答案的过程，完全放在一个固定的边界上进行呢？

• 从特殊情况考虑。诚然，本题中很难一眼看出什么有趣的特殊情况，不妨枚举所有”可能比较边界“的情况。因为上面提到要从 q 是 p 的因数入手，所以可以考虑一些较为特殊的因数。

  • 对于 q=1,2,3 或者其它较小的正整数，似乎并不能给我们带来启示。
  • 对于 q=p，是平凡的。
  • 对于 q=p/2……似乎不是很平凡！

  这时就可以手搓一些小数据来找找性质了，如果不行的话再多试几个思维技巧。但是，要是你恰好刚刚已经想到了”主动强化题目条件“这个技巧，就不难发现或者猜测一个关键性质：如果 q=p/2，则可以强制答案格要么在上边界上要么在左边界上。读者可以感受一下这个猜测是很自然的：对于 p 除了自身外最大的因数，要是以它为边界长度的生成格都只在内部，那这个题看起来就不怎么可做了。

• 从证明过程推出新的性质。我们来尝试着证明一下上面的猜想。事实上，证明是非常容易的。

  考虑一个楼梯，从下往上找到最上面一行 i，满足以这一行左端为生成格的子楼梯的边界长度 \le p/2。如果它恰好是 p/2，则证毕。否则它 <p/2，则其上一行左端为生成格的子楼梯边界长度 >p/2。考虑把 (i,1) 生成的楼梯向右拓展（如下图红色线，编号为 1，的虚线部分），使得其长度达到恰好 p/2。注意，因为 (i-1,1) 生成的楼梯边界长度至少为 p/2+1，所以这个位置向上一格一定在原楼梯内。假设这个拓展到的位置为 (i,j)，则 (1,j) 一定合法（图中橙线，标号为 2），这是因为红线（包括虚线）和橙线的总长度是 p。

  这样，我们证明了上述性质。但是注意，全程用到的关于”q=p/2“的性质只有 q+q=p 这一条！这意味着我们的讨论完全可以证明更宽泛的结论：

  • 最终结论：如果 x+y=p，则要么存在边界长度为 x 的在左边界上的生成格，要么存在边界长度为 y 的在上边界上的生成格。

综上，我们通过运用”思维技巧“，在每一步思考都有迹可循、没有让人大呼妙而摸不着头脑的步骤的前提下，发现了一个非常有趣的结论。

有了最终结论，本题就很容易了。设 u=p/q，则运用结论可以设计一个二分算法：我们每次要么找到一个边界长度为 \lceil u/2\rceil\cdot q 的子楼梯，要么找到一个边界长度为 \lfloor u/2\rfloor\cdot q 的子楼梯，递归 O(\log V) 层后就找到了边界长度为 q 的子楼梯。

上述过程都只需要维护每行的格子数和线段树上二分，而线段树的所有操作都是严格的，所以直接就可以可持久化。如果事先离散化，时间复杂度为 O(m\log m\log V)。