Table of Contents
题目
大厨Bouillon的一个学徒摞好了一叠煎饼，但其中有些煎饼是反着放的。按大厨的标准来说，这些煎饼没有把“最好的一面”朝上。
学徒打算用下面的方法把它们纠正过来：
他选取一段连续的子叠，这段子叠至少包含一张煎饼，并且这段子叠最上面和最下面的那张煎饼都必须是反面的。然后他把这一整段抽出来，作为一个整体翻面，再按原位置塞回去。
证明：无论每一步具体选的是哪一段，只要不断重复这个过程，最终总会得到一整叠全都正面朝上的煎饼。
分析
这道题的关键不是去猜“怎样翻得最快”，而是找一个每做一步都会严格变小的量，也就是单调量。
最自然的做法，是把整叠煎饼的朝向编码成一个二进制数。
约定：
- 正面朝上记作\(0\)；
- 反面朝上记作\(1\)。
如果从上到下把整叠煎饼写成一个\(0\)-\(1\)串，例如：\(101100\)，就把它看成一个二进制整数。
我们的目标状态“全部正面朝上”恰好对应二进制数\(0\)。
现在看一次合法操作会发生什么。
设当前状态从上到下是\(a_1a_2\cdots a_na_{n+1}\cdots a_m\)，其中选中的那一段是第\(i\)张到第\(j\)张，且因为这一步合法，必有：\(a_i=a_j=1\)。
把这一段抽出来整体翻面后，这一段内部的顺序会颠倒，而且每张煎饼的正反都会翻转。所以新状态变成：
\[ a_1a_2\cdots a_{i-1}\,(1-a_j)(1-a_{j-1})\cdots(1-a_i)\,a_{j+1}\cdots a_m\]
更关键的是：在第\(i\)位之前，前面的\(a_1,a_2,\dots,a_{i-1}\)完全没有变化；而第\(i\)位原来是\(a_i=1\)，翻完以后变成了\(1-a_j=0\)。
所以，把新旧两个状态当成二进制数比较时，它们从左往右第一次出现不同，恰好就在第\(i\)位，并且旧状态这一位是\(1\)，新状态这一位是\(0\)。因此，新状态对应的二进制数严格小于旧状态。
重要结论：每进行一次合法操作，整个二进制数都会严格减小。
这已经足够了。因为：
- 这个二进制数始终是一个非负整数；
- 每做一步，它都会严格变小。
而非负整数不可能无限次严格下降，所以这样的操作序列一定只能进行有限步。
当过程停下来时，说明已经不存在任何合法操作了。也就是说，堆里不可能再找到一段“首尾都是反面”的连续子叠。
但这就意味着，整叠煎饼里根本不存在任何反面朝上的煎饼。因为只要还存在某一张反面朝上的煎饼，那么把只含这一张煎饼的长度为\(1\)的子叠拿出来，就是一次合法操作，这和“过程已经停下”矛盾。
所以，过程停止时只能是所有煎饼都正面朝上。于是这位可怜的学徒最终总能解决问题。
补充：如果学徒每一步都选最优操作，最少需要几步
如果我们假定学徒足够聪明，每一步都会选择最优操作，那么真正该问的不是“期望步数”，而是：从一个给定初始状态出发，最少要多少步才能全部翻正？
这个量有一个非常简单的答案：最少步数恰好等于反面煎饼连续块的个数。
例如：
- \(1100110\)里有两段连续的\(1\)，所以最少需要\(2\)步；
- \(10101\)里有三段连续的\(1\)，所以最少需要\(3\)步；
- \(111000\)里只有一段连续的\(1\)，所以最少只要\(1\)步。
为什么是这样？证明分成上下两部分。
先证“至多这么多步”。
如果当前有一段连续的反面块\(11\cdots1\)，那么直接把这一整段作为子叠拿出来翻一次，就会整段变成\(00\cdots0\)，而且因为这一段首尾本来都是\(1\)，这正是合法操作。所以每一步都可以消去一整段连续的反面块。若一开始共有\(r\)段连续的\(1\)，那么用这种方法至多\(r\)步就能完成。
再证“不可能更少”。
设当前共有\(r\)段连续的反面块。我们证明：一次合法操作至多只能让这个数减少\(1\)。
确实如此。设选中的子叠内部原本有\(k\)段连续的\(1\)。因为这段子叠的首尾都是\(1\)，所以它在内部的形状一定是
\[ 1\cdots10\cdots01\cdots1\cdots01\cdots1,\]
也就是恰好有\(k\)段\(1\)块，被\(k-1\)段\(0\)块隔开。
把这段整体翻面以后，“倒序”并不会改变连续块的个数，而“取反”会把其中的\(k\)段\(1\)块变成\(k\)段\(0\)块，把原来的\(k-1\)段\(0\)块变成\(k-1\)段\(1\)块。所以在这段子叠内部，连续的\(1\)块个数恰好从\(k\)变成\(k-1\)，也就是减少了\(1\)。
子叠外面的部分完全不变；并且由于翻完以后这段子叠的首尾都变成了\(0\)，它也不会和子叠外面的\(1\)块在边界处连成一块。因此，整串中连续反面块的总数每一步至多减少\(1\)。
所以，若一开始有\(r\)段连续的\(1\)，任何策略都至少需要\(r\)步。
上下两部分合起来，就得到：最优策略下的最少步数正好是\(r\)，也就是初始状态中连续反面块的个数。
这也说明：即使只给出\(n\)和\(m\)，通常也还不能唯一确定最少步数，因为它还取决于这\(m\)张反面煎饼是怎样分布的。
例如\(n=3,m=2\)时：
- \(110\)只有一段连续的\(1\)，所以最少\(1\)步；
- \(101\)有两段连续的\(1\)，所以最少\(2\)步。
两者的\(n,m\)相同，但最优步数不同。