cf1779g：用套路思维地解决思维题

feecle6418 · 2023-01-06 11:59:34 · 题解

本题解旨在展示，如何动最少的脑筋，”思维地“（也就是说得到简洁优美的做法，不用高级算法草过去）解决这类“套路的思维题”。

首先发现，如果最外圈是一个环，则答案是 0。这启示我们，题目的限制应该是很“松”的，很容易满足。

经典思维方式：既然限制很松，那很可能找到答案的一个合理的下界，就是真实答案。

如何找一个“界”？又是经典思维方式，从特殊处考虑。

考虑最外圈的角 A,B,C。不妨设 A\to B,B\to C,A\to C。那 A 只有出边，C 只有入边，所以 A 的邻边之中必须反转一条，C 同理。

这个特殊情况能否拓展到更广泛的情况？可以！考虑下图。

如果红线所示的边全是从下往上（或者全是从上往下），那上面的和下面的两部分肯定无法互相到达，所以在这一层至少要反向一条边。

进一步分析，

1. 如果某一层至少要反向一条边，则它上面的所有层都至少要反向一条边，因为所有边都会以同一方向延伸到上一层。
2. 至多有两个方向可能出现上述情况，否则在某条边的方向上会导出矛盾。

因此，必须反向的层长成下图：

若 p+q\le n 也就是两坨互不相交，显然至少要反转 p+q 条边。否则，直接把右侧最外层全反转了，只用反转 n 条边。因此，答案至少是 \min(p+q,n)。

实际上，答案就是 \min(p+q,n)，证明也不难，只需证明，只要不存在两层之间全部方向相同，就一定互相可达。请读者自行证明。

可以发现，我们只需要牢记“找下界”和“从特殊到一般“两种思维方式就可以解决本题。唯一的需要灵感的地方是，发现最外圈是一个环，则答案是 0。