|
[技术]【纯技术】扫雷中IOE的最大可能值及其证明.精 (6/2686) |
|
|
|
|
基本思路：将整张图上的操作分解成许多组，每组以包含1个雷以及在雷周围的一些左键和双击为单位，并证明一个单一的局部IOE上限为3.4
证明：
记左键为L，右R，双D。
对一张图A，设能使扫完这张图（解决所有BBBV）并使IOE达到最大的一系列操作的集合为U。那么，集合U中显然不会有点在同一格的两个L或点在同一格的两个D（否则去掉其中一个，IOE变大）
记所有操作依次为a_1,a_2,…,a_n，（其中a_i包含的信息有：该操作是L/D/R，以及该操作的位置(坐标)）
令B_i为第i次操作新打开的BBBV的集合，即这次操作后比操作前新开的BBBV。
对于每个D操作，它所在的格子一定之前已经开了，该格可能是L点开的，也可能是D点开的。
下面将a_1,a_2,…,a_n中的操作按顺序分组，满足如下条件：
1. 每组中最多有一个R（飙泪）。
2. 对于每一个D操作，任选一个相邻的R操作，归入该组.
3. 对于一个L操作，若所有操作中该格上还有D操作，那么将这个L分到对应的D那组；其余的L分到各自单独的组中（即每组中只有一个L操作）。
再给出对于其中一组来说，该组新开的BBBV的定义：
该组新开的BBBV为该组中所有操作新开的BBBV的并集。也就是说，记该组开的BBBV集合为S，该组包含的操作有a_(x_1),…a_(x_j)，则S为B_(x_1),…,B_(x_j)的并集（B_1,…B_n定义在上一个加粗的地方）。
类似地，定义该组直接新开的格子为该组中所有操作直接新开的格子（也就是不包含开op带开的格子）的并集。
由于最终开的BBBV为所有组中开的BBBV的并集，所以开的BBBV总数<=各组所开BBBV数相加（好像就是等于，但不影响证明）。同时，IOE=总bv数/总操作数，那么只要能证明每组的新开BBBV数<=操作数*c（c为一个常数系数），就能证明IOE<=c。
下面证明：对于每一组操作，它们开的bv数<=操作数*3.4。
首先，一组操作新开的bv数一定小于等于该组操作直接新开的格子数。我们把上面的不等式转化为证：
对于每一组操作，它们直接新开的格子数<=操作数*3.4。
对此，我们进行分类讨论。
① 这组操作中不包含R。那么由分组要求2，发现有D的组一定有R，那么此时组中也无D，于是组里只有L。那么，该组直接新开的格子数<=操作数<=操作数*3.4。
② 这组操作中包含R，且该组中存在一个L和D的顺序，使得在不需要组外的L或D、并且不开op的情况下，能够使该组新开的所有格子都能够打开。
这些条件保证了组内每个D操作的点都是被组内操作直接打开的，因此我们只需要关心以R标的雷为中心的5*5区域。并且在下面的穷举中可以发现，
另外，这个5*5区域内可能有标了其它的雷或被其它操作先开的某些格子，不过我们可以把这些格子都换成未开bv，这样IOE不减，穷举起来也方便一些。
此时对于任意两个L和对应点位的D来说（由分组要求3，有L就必定有对应点位的D），只要两个L不处于对角位置（如下图左），那么L*2+D*2其实都可以被L+D*3取代（例如下图右，在2个1处分别L+D，开出的格子包含于在旗左下1处L后依次在旗左下、左、上D开出的格）并且IOE不减。（即使在多次替换后，替换后的那组操作依旧满足前面要求的不需要组外操作，这个大概想想就能明白，证明细节写起来貌似有点烦，我先略了）
 
其次，这时组内必包含一个L（否则必定需要组外的操作先开一些格）。于是，我们只要穷举L的数量=1个或2个即可（大于2个L的都能用D替代掉其中的一些L，化归为1或2个L的情形）。
1) 如果L有2个、且不能被化归为一个L，那么只能是想上面左图那样的两个点位，这时稍微穷举一下就发现这样的局部直接新开的格子数<操作数*3.4。（最大是3.2）
2) 如果L只有一个，那么可以直接参照
http://saolei.net/BBS/Title.asp?Id=8243
中的穷举，把中心的数字换成标的雷，数字周围的雷换成一个D，L点在任意一个D处即可（并且事实上第②类的分类条件可以保证此时每个D操作，或者在原位有L，或者和某个D相邻。这让我们能少穷举很多情况）。跳过具体步骤，发现此时格子数<=操作数*3.4。取等条件：在雷左L，雷左、上、右分别D。
③ 剩下的情况。此时，这组操作中包含R，且对于该组中任意一个L和D的顺序，都需要组外的L或D、或组内操作开op，才能够使该组新开的所有格子都能够打开。
此时，这组中一定有一个D操作，它点的那格不能被组内任意操作直接打开（L和R都不需要前置操作，只能是D需要组外操作或开op）。此时，该格不可能是被组外的L直接点开的。因为如果这格上有L，那么必定只有一个L（集合U性质）；根据分组要求，这个L必定要分到这一组，所以它不是组外操作。所以它只能是被组外的D直接开的或者是开op带开的。而开op本质上就是在一堆相邻数字0上的D操作，所以也可以化归为被D直接开的情况。
记组外D为D1，组内D为D2。D1要开D2所在格，它们就必定相邻。分类讨论：若D1不与组内所标雷相邻，那么D2旁边最多还剩4格能新开；若相邻，D2旁边最多剩3格。所以，D2操作最多新开4格。
现在，把D2操作置换为：把D2相邻格全部填成新开的格子，操作变为在D2处L后再D。现在，新开的格子比原来至少多4格，操作只多了一个，那么只要替换后该局部直接新开的格子数/操作数仍小于4，这个替换就事实上增加了直接新开的格子数/操作数；同时，原来D2相邻格中之前开的和新开的格子现在也都在D2后被打开了，因此不会导致该组内其它操作由于这个调整而不能进行。
将这组中所有不能被组内任意操作直接打开的D都进行上述替换后，③就化归成了②中的情形。而在②中，直接新开的格子数/操作数<=3.4<4，所以③中直接新开的格子数/操作数<3.4，即直接新开的格子数<操作数*3.4。
综上，对每组操作均有：直接新开的格子数<=操作数*3.4，故对任意一张扫雷图（任意长宽雷数），全图IOE<=3.4。
===============================分割线==============================
发现这个证明即使略去了一些细节，但写的还是好长...证明里面又用了不少神奇的技巧（自我感觉），也不知道这么纯技术的贴有多少人看完，不过如果有大佬发现证明有什么问题的话也请说一声。
经建议，附上以前的几个相关的帖子：
http://saolei.net/BBS/Title.asp?Id=14243
http://saolei.net/BBS/Title.asp?Id=4509
|
|
最近一次修改:2018-6-22 17:03:51
|
|
|
|
沙发。
如果该证明是对的，那么这篇帖子中的“进程中IOE”最大值又是多少呢？
http://saolei.net/BBS/Title.asp?Id=14243
|
|
回1L，如果证明没问题的话，对于你的问题，只要把最前面集合U的定义改成“使扫雷进程中IOE达到最大的前k个操作”的集合就行。（其实证明里面没太用到集合U的太多性质）
证明的其它地方都不用动，结果仍然是3.4。
|
|
|
流弊，经过自己摆雷get到了最高ioe的由来，不过与实际情况区别还是很大，毕竟有雷数限制，不知道有没有办法算出初级最高ioe（中高级不指望了）。
|
|
|
理论值3.4，实际上雷网录像能刷到2.2以上的图估计都很少
|
|
|
用了好几天，非常仔细地看完了。这个证明很强，就是跳了许多步骤看起来费劲，有时间想写一篇解读。
|
|
|
|
