题目

Turbo the snail plays a game on a board with $2024$ rows and $2023$ columns. There are hidden monsters in $2022$ of the cells. Initially, Turbo does not know where any of the monsters are, but he knows that there is exactly one monster in each row except the first row and the last row, and that each column contains at most one monster.

蜗牛 Turbo 在一个 $2024$ 行 $2023$ 列的棋盘上玩游戏。怪物的位置是未知的，但怪物的分步一定满足：除了第一行和最后一行之外，每一行都恰好有一只怪物，并且每列最多有一只怪物。

Turbo makes a series of attempts to go from the first row to the last row. On each attempt, he chooses to start on any cell in the first row, then repeatedly moves to an adjacent cell sharing a common side. (He is allowed to return to a previously visited cell.) If he reaches a cell with a monster, his attempt ends and he is transported back to the first row to start a new attempt. The monsters do not move, and Turbo remembers whether or not each cell he has visited contains a monster. If he reaches any cell in the last row, his attempt ends and the game is over.

Turbo 会尝试从第一行移动到最后一行。每次尝试，他都会从第一行的任意一个格子开始，然后反复移动到相邻的（有公共边）的格子（他允许移动到之前已经到达过的方格）。如果他到达了有怪物的格子，他的尝试结束，然后被送回第一行，开始下一次尝试。怪物不会移动，且 Turbo 会记住他访问过的每个格子中是否有怪物。如果他到达了最后一行的任意一个格子，游戏结束。

Determine the minimum value of $n$ for which Turbo has a strategy that guarantees reaching the last row on the $n^\text{th}$ attempt or earlier, regardless of the locations of the monsters.

求最小的 $n$，使得无论怪物如何分布，Turbo 总有一个策略可以保证至多使用 $n^\text{th}$ 次尝试到达最后一行。

解法

$n=3$，以下是策略：

1. 扫描第二行，找到第二行的坏人
2. 若第二行的坏人不在边缘，扫描第三行的坏人，并在第三行坏人的异侧通过（Case 1）。
3. 否则，阶梯状扫描剩余行。若在扫描中碰到坏人，则坏人中已经有一个可通行的区域（Case 3）；否则，已经有解（Case 2）。

彩蛋

1 探索阶段

聊天记录

显然 $n≤2023$，给出了一个上界，看看如何缩小。

继续 😃

断言：若 $n<2023$，则策略一定不能找出所有坏人，即存在不找出所有坏人的策略
（注：这是错的）

继续

感觉不太行诶

要提示吗

哦，每行恰有一个，看漏条件了

（汗

我就说

不然子子孙孙无穷匮也

那么撞到一个坏人可以直接排除一行一列了

很正

我有一种 $3$ 步的策略，只剩两种坏人排布可以卡掉，即三个坏人排成斜线

这是你的最终答案吗

显然不是

推广吧

目前正确的

这个策略在斜线排布会被卡到 $2023$

多么不妙

（

不如考虑蛇形前进

这样掌握的信息可能多一点

好像也不行

并不行

只能排除一种斜线

另外一种排不了

唉老师说这道题借鉴了 OI

有题目背景，这个风格确实像

懂了

撞到第一个坏人之后往一边转

撞到第二个坏人

不对，还是会被斜线卡

能不能把斜线 ban 了（恼

不 ban 斜线的话这种方法最坏还是 $2023$

你可能还看漏了什么

又漏了？

等等.我一开始也觉得是 $2023$

回想一下

里面几乎没有数学芝士

所以那唐人班才会讲的

我想到一个 $h/2$ 的构造

$2023$ 列，$2022$ 个坏人

对呀

那很坏了

不好

我说的是这种斜线

是的是的

我可能晚自习傻掉了

我好像懂了

教我

(汗)

我再想想

我只知道答案

需要利用第一行的特殊性卡斜线

没错

……但是会被另一种斜线卡掉

没错……

斜线不 ban 怎么玩

2 二分做法

聊天记录

能不能在斜线上二分怎么的？

斜线上二分可以做到 $\log$ 级，但是会不会有更好的？

我也在 try

我要不先跟你说一下我现在的策略？说不定能找到优化的地方

说吧

md 回想起来我第一眼看成了坏人不断移动

当时他们讨论 $2023$ 的时候我都蒙了

做法好像确实是真的

how

初始区间为 $[1,2023]$，设第 $i$ 列往下走可以“探测到”坏人在第 $d_i$ 行。由于探测不到的情况，已经找到解了，我们最坏的情况就是每次都能探测到。

对于一个区间，若区间的端点都被探测到，则称区间端点探测到的坏人为两角的矩形为探测矩形。

对于一个可能存在解的矩形，我们探测它的中间部分，此时可以探测出两个小矩形。由于最初的矩形不是正方形，我们可以知道两个小矩形之中至少有一个不是正方形。

于是我们可以不断缩小矩形，直至它只有两列。显然此时存在解。

由于每次矩形都会缩小到一半，因此它是 $\log$ 级的。

这是只有两列的矩形的解

扁的矩形也可以，只要不是正方形就行

只要每次在正中心探测，那两个小矩形就肯定有不是正方形的

这种构造是 $14$ 次

底数要是精确的吗

$\lceil \log_2(n-1) \rceil + 3$

$+3$ 有两次是用来确定边界（我不知道能不能省掉），最后一次是走到终点

答案再小一个量级

emm

那二分是不行了

你的方法我好像显然似乎无法完全理解

……可能搞信息的比较容易理解

是

意思是这样的：每次在竖向一刀切开，抛弃一半的棋盘，只在剩下的另一半玩。比较复杂的部分其实是证明这样抛弃是没有问题的

好活!

其实我是从斜线开始想的

因为斜线它必须空出来一个地方，这个空出来的地方就会导致斜率有不同

那我就只需要把斜率为 $1$ 或 $-1$ 的地方切掉就行了

3 正解

聊天记录

答案是__.

要说吗

从答案推

可以

$3$

……我好像一直以来都有一个误区

what

坏人是可以通过排除法确定的，所以一次尝试可以确定很多个坏人的位置

OK 了，我知道 $3$ 次是怎么来的了

我直接把各种情况给你画出来吧

恭候

对称的情况就不画了

美极了

浅显易懂