上期问题 每期一题之3:猜对错
解答:
第一问比较容易,我们可以胡乱猜一个作为基准,比如就猜所有都是T。然后每轮仅把一题的答案改为F,看看新的结果和基准比是大了还是小了,大了说明这题应该是F,否则说明应该是T。这样用N+1轮得到所有结果。
想要仅用kN轮(k<1)有多种方法,基本思路是把题目每m个分成一组,每次用n轮提问确定m个答案(n<m)。下面是官方题解中用两轮确定三个答案的方案:
首先用两轮猜测TTTTTT…T和TFTFTF…TF作为基准一和基准二,设这两个基准值分别为x和y。我们把相邻三个题目作为一组,对于每一组,第一轮猜测时,以基准一为模版,只把对应组里前两题答案改为F,其他全不变。把结果与x值对比,那么有三种情况
1) 如果结果为x-2,说明前两题答案为TT。然后再简单用一轮提问确定第三题
2) 如果结果为x+2,说明前两题答案为FF。同样再用一轮确定第三题
3) 如果结果为x,说明前两题答案为TF或FT。此时,我们发起第二轮提问,这一次是以基准二为模版,把对应三道题的答案反转(不妨设本来是…TFT…,变成…FTF…),然后把结果与y值比较,那么我们会发现有四种情况:
3.1) 结果是y+3,说明这三题答案为FTF
3.2) 结果是y-3,说明这三题答案为TFT
3.3) 结果是y+1,说明前两题改对了,第三题改错了,这三题答案应为FTT
3.4) 结果是y-1,说明前两题改错了,第三题改对了,这三题答案应为TFF
综上,我们可以用每两轮搞定三题,外加两轮基准,还可能有最后一组不足三题的特殊处理。总之大约就是n*2/3轮查询。
第三问非常难,理论上说,总的可能性是2^n种,也就是n个比特的信息量。我们每轮询问得到一个数字n,即log(n)比特信息量,那么问题轮数的理论下界为O(n/log(n))次。这个下界是可以达到的,但是题解我看不懂…… 题解可以点击下方“原文链接”查看,哪位看懂了可以给我解释一下。
本期题目:矩阵翻转
给定一个M*N的起始矩阵和一个M*N的目标矩阵,我们可以在起始矩阵上进行如下操作:选择一个K*K的子方阵(k<=M, k<=N),把这个方阵的元素沿对角线翻转,注意可以沿两条对角线的任一条。问能否经过若干次操作,把起始矩阵变成目标矩阵。只需判断是否可以,不必输出具体过程。
例如,如果起始矩阵是[[1 2 3] [4 5 6]],目标矩阵是[[1 4 3] [6 5 2]],那么可以经过两次操作得到。先把右边2×2子方阵沿反对角线翻转,再把左边2×2子方阵沿主对角线翻转即可。