浅谈一类【变色地砖】问题

· · 算法·理论

似乎没有人仔细搞过这个。更可能的原因是我起的名字和别人不一样。
就这样吧。
碰到了很多次，所以写一下。真的很浅。

保证 AI 贡献小于等于 0.1\%。

问题情景

有 n 个地砖，每个地砖有（至少）三种类型：

  1. 离开地砖，碰到就可以结束。
  2. 方向 0 地砖，会沿着某个方向前进到下一个地砖。
  3. 方向 1 地砖，会沿着某个方向前进到下一个地砖。
  4. ...
  5. 方向 w-1 地砖，会沿着某个方向前进到下一个地砖。

其中 w\ge 2，当从方向 i 地砖离开时（0\le i<w），该地砖切换为方向 (i+1)\bmod w。
这里的方向 i 即使相同，也不一定有着相同的跳转规则，可能是某个地砖独有的。

问题可能是：

  1. 从某个点出发会走多少步，从哪个离开地砖离开，或者判断根本不能走出。
  2. 进行一次或多次行走，某个或者每个地砖被走多少次。或者说地砖的形态。
  3. 进行一次或多次行走，某种地砖最后有多少个。

约定的名称

我们称 nxt_{x,i} 为当地砖 x 是方向 i 的时候，下个地砖是什么。
特别的，我们规定，对于离开地砖，nxt_{x,i}=x。

我们称 a_x 为当地砖 x 现在的方向。
特别的，我们规定，对于离开地砖，a_x=0。

我们称 dep_x 为假如可以随意规定接下来每一步的方向，那么从 x 走到一个离开地砖最小步数。特别的，如果无法到达，dep_x=\inf。

我们称非离开地砖为普通地砖。

我们称 w=2，且对于任意普通地砖 x，都有 nxt_{x,1}=x+1,nxt_{x,0}=x-1 的问题为序列变色地砖问题。
我们称 w=2 的问题为普通变色地砖问题。

一些性质

通用

将点按照 dep_x 排序。有性质：
这个排列的任意一个前缀可以有一个状态 (a_{p_1},a_{p_2},\dots,a_{p_k})。无论怎么走，某一个状态至多出现一次。

有一个略不严谨的证明，你能发现他的漏洞吗？

:::error[略不严谨的证明]{open} 假设我们当前处于状态 A。接下来，我们会走到 p_1~p_k 中的一个元素。这个时候，A 会被改变，如果想要第二次回到 A，我们需要总共到达这个点 w 次，于是走过所有 w 个方向。我们只关心 dep_x 最小的一个方向。因为 dep_x 一定从这几个方向中转移而来，所以一定有一个方向走到了 dep_x 更小的点，然后我们以此类推，总可以推到 n。 :::

:::warning[问题] 上面的证明已经可以理解了，但是有一点没有说清楚。
我们可以递归到一个点，是因为我们发现这个点的状态改变了，和上个问题一致，于是可以递归。
但是有一种可能，其中有一个点的所有出边全是一个点，于是这个点的状态没有改变，我们还有理由递归问题吗？
::: :::success[解决] 请先看【问题】部分。
其实是能的。我们发现虽然状态没有变，但是我们照样遍历了这个点的所有出边，本质上也是递归了。
事实上，即使不那么特殊，只是涉及了多个，只要某个点被路过至少一次，他就会被路过至少 w 次，从而经过所有边，以此递归。
::: 这个性质好像用到的不多，但确实有用到这个的，用到即王炸。因此我常常把这种题想偏到这里。

序列变色问题

我们可以轻松将序列从离开地砖拆开来，然后问题可以视为离开地砖出现且仅出现在序列两边的情况。

方便起见，称方向 0 为 L，方向 1 为 R。离开地砖因为出现且仅出现在序列两边，所以忽略。

性质 1

对于只有一个点在上面动的情况，如果到达了某个点 x，那么之后这个点不会在之后的移动中是 x 切换前进方向。

这是显然的，因为人离开 x 后，x 方向改变，而人如果想要回来则需要调转方向，此时方向又相同，所以不会切换方向。

这个东西很显然，但是可以让我们得出更多的性质。

性质 2

我们每次转向都是在起始位置左边的 R 和右边的 L，同时每次都会在较接近的转折点转向，那边转向的多，就会在对面的离开地砖离开。

显然。

性质 3

假设起始点在 i，初始方向为右，那么将会把左边的 i 个 L 或右边的 n-i+1 个 R 变换。显然至少有一个可行。

证明简单，假设左边有 x 个 L，i-x-1 个 R。那么我们会转 i-x-1 次方向。如果是左边出，那么右边就转了 i-x 次，于是我们要把 i-x+x=i 个 L 改成 R。另外一边类似。

这个就比较有用了。

性质 4

本质上是性质三的特殊情况。如果初始序列较特别，为 RRR...RRRLLL...LLL，那么有更多性质。

首先声明一些东西： 每次从某个点开始行走，都会将一个前缀改成 R 或者把一个后缀改成 L。因此无论进行多少次操作序列始终为 RRR...RRRLLL...LLL 的结构，可能全为某种字符，但无伤大雅。我们用 S 即 R 的个数来表达这个序列。显然 S 满足 0\le S \le n。

然后在 x 的位置出发之后，新的序列 S^\prime 为：

S^\prime = \left\{ \begin{align*} &S+x&n-S\le x\\ &S-(n-i+1)&n-S>x\\ \end{align*} \right.

这个已经对了，但是不够好，可以稍微美化亿下。

S^\prime = \left\{ \begin{align*} &(S+x)\bmod(n+1)&n-S\le x\\ &(S-(n-i+1))\bmod(n+1)&n-S>x\\ \end{align*} \right.

然后我们发现……

S^\prime = (S+x)\bmod(n+1)

这真是一个有用的性质。

例题

P13336 [GCJ 2012 Finals] Shifting Paths - 洛谷

首先这是一个普通变色地砖问题，比较困难，直接的想法是考虑暴力。复杂度 O(2^Npoly(N)) 的，其中 poly(N) 表示一个有关 N 的多项式，不重要，也不是影响复杂度的主要因素。
然后我们想要 meet in middle，这样复杂度说不定变成 O(2^{\frac{N}{2}}poly(N)) 就可过了。于是你打算集合 A 快速跳，快速的搜索出从某个点以某种状态进入时会从哪个点以什么状态出去。B 集合暴力跳。
结果你发现失败了。由于 B 集合中的状态反复出现，可能会暴力跳很多步，你很可能会被卡回 O(2^N)。

然后你敏锐注意到#通用|通用性质，于是你考虑把 B 集合里的点改成 dep_x 最小的点。这样 B 集合里的状态就不会反复出现了。B 集合内的步数严格小于 |B|。

复杂度是 O(2^{|A|}|A|+2^{|B|}) 的。严格折半会 TLE，让 |A| 小一点，|B| 大一点会更优。

提交记录 实现

CF733E Sleep in Class - 洛谷

序列变色地砖简单题。

走一步就花一秒。即求每个位置独立出发，走过的格子数。

根据性质 2，我们仅会在转折点变向，其他地方都是一路畅通的。
所以你的路线一定长这样（其他情况类似）:

所以我们只考虑端点的贡献即可。

那么我们要怎么求所有点的答案呢？
首先我们可以快速地判断出来一个点出发是从左边出去的还是右边出去的，然后分别处理。
不妨处理左边出去的。
然后我们发现其代价核心的部分在于转折点的贡献。
左边的贡献是简单的，容易发现如果从左往右扫，将会不删。于是直接继承上次计算的东西即可。或者直接预处理也行。
右边处理也相对简单，容易发现产生贡献的东西是个区间，而左端点和右端点都不降，所以可以双指针。

提交记录/实现

P9353 [JOI 2023 Final] 现代机器 / Modern Machine - 洛谷

这题太难了，不会，留给读者当课后练习。

其中特殊性质启发我们使用#性质 4，但是一般情况没有这个性质。

:::info[特殊说明] 本题有要求放入时强制覆盖，所以需要调整。
结果是：

S^\prime = \left\{ \begin{align*} &(S+x)\bmod(n+1)&S\ge x\\ &(S+x+1)\bmod(n+1)&S<x\\ \end{align*} \right.

:::

但我们发现很多时候由于我们每次染一个前缀染一个后缀，序列很可能马上就会变成 RRR...RRRLLL...LLL 的特殊结构。
显然这个序列一定是前缀被染成 R，后缀被染成 L，可能有中间保持原状。
接着你使用#性质 3，发现能把点落在前后缀上的情况快速做掉。
然后你又发现，如果没落在中间，被染色的无论是前缀还是后缀都会翻倍。
所以，中间的变换是 O(\log n) 的。
但是你发现维护前缀和后缀太难了，一直在变，且总数巨大。于是我们考虑偷一点懒，不严格维护前后缀大小，而是维护略小一点的 2^k。
之后就是一些预处理加速和复杂度证明的事情了，和变色地砖关系不大了。
实现貌似有很多细节，所以没写。