F. Angel 兔子藏洞问题最少提问次数证明
文本内容
题意
一排有 n 个洞，有一只兔子在某个洞。每个时刻必定移动到相邻的洞中，需要构造长度最短的询问序列 qi，第 i 项表示询问在兔子第 i 次移动前是否在 qi 这个洞中，使得至少猜中一次。
解法
思路一：考虑兔子发生移动时奇偶性必定发生改变，那么可以钦定兔子初始奇偶性。确定了奇偶性后，由于每次只能走一步，所以可以把它往一边赶。最坏情况下需重复遍施这个过程即可，对边界稍加讨论可以发现 2(n-2) 大概率是这个思路下的最小值，注意特判 n=1,2 的情况。
解法
思路二：使用状态 DP 打表发现规律，令dp_s 表示兔子可能存在的状态为 s 的最小询问数，枚举询问地点进行转移等。
还有许多其他思路，例如建立兔子的时间-位置坐标标签等。
接下来给出 2(n-2) 是最小值的证明：
解法
证明：由思路一，当 n > 2 时，初始时刻在奇数位置情况的兔子和在偶数位置情况的兔子永远不会相遇，且每个时刻后奇偶互换。考虑一次检查实际上是一类奇-偶情形地消除一个可能，因此如果有m种兔子就只能在m-1步后赶全干完。这为最优情况提供了下界，即奇-偶递进的消除带来只需 2(n-2) 步。
Bonus: 此题有对应版本，详见：https://math.stackexchange.com/questions/4418051/how-do-you-catch-a-cat-on-a-tree
整体描述
这张图片是武汉大学2022年第八届ICPC/CCPC集训队编程竞赛试题F题目的题干与几种解法的幻灯片截图。图片分三页，内容主要关于“有n个洞和一只兔子，每次兔子只能挪到相邻的洞，人每次提问一组洞是否有兔子，怎样最少提问才能一定抓到兔子”的数学/算法问题。除了题意、标准思路，还包含动态规划、数学归纳等多种解答思路，并给出了最优提问次数为2(n-2)的证明。最后一页还有国外论坛解答的链接，说明该题世界范围有讨论。整体风格理性、学术，适合ACM竞赛圈内技术交流。
无明显双关、谐音梗或暗示，仅纯粹算法证明与技巧展示。
来源说明
图片来自武汉大学ICPC/CCPC集训队2022年第八届集训赛的幻灯片课件，是公开竞赛讲解内容。所用题目为广为流传的竞赛经典题型之一，与国际知名问答社区StackExchange的相关问题（图片底部给出链接）密切相关。内容常在ACM、ICPC、CCPC等大学竞赛中出现，被广泛用作训练与技巧教学。该图片为线下或线上分享课件的截图，并非原创题目，也并非特殊二次创作。
