[THUPC 2023 决赛] 喵了个喵 III

yemuzhe · 2023-07-31 21:49:35 · 题解

此题解篇幅太长，请谨慎观看！

题目大意

• 有一个大小为 n 的牌堆 A，牌堆中的数均为 1 \sim n / 2，且每个数恰好出现 2 次。

• 刚开始有两个空栈。可以进行 op 次操作，有两种操作：

  1. 可以把牌堆顶上的数放入一个栈中，如果该栈最上方的两个数相同，则自动消去这两个数。

  2. 如果两个栈顶的数相同，则可以消去这两个数。

• 构造一种操作方案，使得所有数都被消去。

解题思路

这题可用区间 dp 解决。

容易发现，第一种操作的后半句没什么用，因为可以改写成第二种操作来实现。

于是我们把相同的两个数放入不同的栈中，也避免了第一种操作的自动消除。

考虑牌堆中的一段区间 [l, r]。内部可以消去的肯定要消去，剩下的是不能消去的数，且按原牌堆顺序排列。

如图：（图中一种颜色的球代表一个数）

当然，也不一定像这样所有一起加入后再消除。

在 dp 时我们枚举 [l, r] 内最后消去的数（可能一个或两个），然后分段处理。

我们把 [1, l - 1] 中能和 [l, r] 中的数配对的数称为「有用的数」。

这里有一条非常重要的性质：

「有用的数」一定都（要）堆在同一个栈的最顶部。

我们把这个栈称为「有用的栈」。如果没有「有用的数」则认为两个栈都是「有用的栈」。

这条性质的证明将会在「区间 dp」部分的末尾给出。请读者时刻牢记这一性质。

Part 1：预处理

在 dp 之前，我们需要预处理几个数组：p, lx, ry, xl, ly, yr。

• p 数组

  ```cpp for (int i = 1; i <= n; i ++) { // 如果 A[i] 已经出现过，那么那么令 p[上一次出现的位置] = i 且 p[i] = 上一次出现的位置 if (l[a[i]]) p[l[a[i]]] = i, p[i] = l[a[i]]; l[a[i]] = i; // 用当前位置更新 } ```

• lx 数组

  初始化 $lx _ {r + 1, r} = r + 1$（即无穷大），易得递推式 $lx _ {l, r} = \begin {cases} lx _ {l + 1, r} & (p _ l \le r) \\ \min \{lx _ {l + 1, r}, l\} & (p _ l > r) \end {cases}$。 这个函数可以用来判断 $[l, r]$ 内的数是否可以全部消除（即 $lx _ {l, r}$ 是否大于 $r$）。

• ry 数组

  初始化 $ry _ {l, l - 1} = 0$（即负无穷大），易得递推式 $ry _ {l, r} = \begin {cases} lx _ {l, r - 1} & (p _ r \ge l) \\ \min \{lx _ {l, r - 1}, r\} & (p _ r < l) \end {cases}$。 可以在 dp 时顺便处理，省去两维（就变成变量了）。

• xl 数组

  初始化 $xl _ {l, l - 1} = l$，易得递推式 $xl _ {l, r} = \min \{xl _ {l, r - 1}, p _ r\}$。 可以在 dp 时顺便处理，省去第一维（如果不是还要预处理 $yr$ 数组还可省去第二维）。

• ly 数组

  考虑用树状数组实现。注意这里的树状数组的循环顺序有些不同，用来实现后缀查询。 加入时只加 $p _ i < l$ 的。在 $p _ i$ 位置加入 $i$。 查询时 $(xl _ {l, r}, n]$ 这一段区间的最小值，也可以查询 $[xl _ {l, r}, n]$。 可以在 dp 时顺便处理，省去第一维。 ```cpp void modify (int p, int c) // 单点修改（其实是加入） { for (; p; p &= p - 1) tr[p] = min (tr[p], c); return ; } int ask (int p) // 区间（后缀）求最小值 { int res = inf; for (; p <= n; p += p & -p) res = min (res, tr[p]); return res; } // int main () for (int l = n; l; l --) { // ... memset (tr, 0x3f, sizeof tr); for (int r = n; r >= l; r --) { ly[r] = ask (xl[r]); // 询问满足条件的最小 i if (p[r] < l) modify (p[r], r); // 加入当前 r } // ... } ```

• yr 数组

  初始化 $yr _ {l, l - 1} = l$，易得递推式 $yr _ {l, r} = \max \{yr _ {l, r - 1}, p _ r\}$。 可以在 dp 时顺便处理，省去两维（就变成变量了）。

这样我们就完成了所有的预处理。

Part 2：区间 dp

状态设计

记 f _ {l, r} 为当一个栈是「有用的栈」时，能否删完 [l, r] 内配对的部分并把剩下的堆在另一个栈。

同理记 g _ {l, r} 为当一个栈是「有用的栈」时，能否删完 [l, r] 内配对的部分并把剩下的堆在同一个栈。

考虑到可能没有剩余的，记 both _ {i, j} 为当一个栈是「有用的栈」时，能否删完 [l, r] 这部分。

容易发现 both 其实是 f 和 g 共同的特殊情况。

注意「状态转移」部分中分界点的同 / 另一个栈是相对整个区间而言，而子区间的同 / 另一个栈是对子区间而言。

由于题目还要求具体方案，需要存三个数组 pf, pg, pboth，来记录转移的信息（具体见「状态转移」部分）。

根据「状态转移」部分可知，最终答案即 both _ {1, n} 的过程仅与 f, g, both 有关，故只设计设三种状态即可。

初始化

初始化 f _ {i + 1, i} = g _ {i + 1, i} = both _ {i + 1, i} = 0（0 \le i \le n）即可。

状态转移

• 第一种：g \leftarrow f + f

  概念

  如上图，我们选择最前面的满足 p _ i > r 的 i 即 lx _ {l, r}，然后把这个序列分成 [l, i - 1]、i 和 [i + 1, r] 三段。

  对于 [l, i - 1] 这段，把它们放进另一个栈（右边）。

  对于 i，把它放进同一个栈（左边），它不会产生任何消除（和它配对的在 r 后面）。

  对于 [i + 1, r]，把它们放进另一个栈（这时是左边），这时它们会把 [l, i - 1] 这部分剩下的全部消掉。

  为什么这时候另一个栈是左边呢？因为左边的栈已经被 i 堵住了，相当于是空栈（没用），但右边的栈很可能是「有用的栈」。

  这样我们就不会在另一个栈（右边）剩东西，从而实现了 g 的转移。

  为什么 i 一定是最后消除的呢？

  如果分界点为 i，那么 [i + 1, r] 的剩余部分都会叠在 i 上面（堵住了），而 [l, i - 1] 没有剩余；

  如果分界点不为 i，那么 i 就会剩在另一个栈无法消去，不符合 g 的定义。

  读者不妨可以模拟一下上图的具体过程。

  前提

  首先得保证存在这么一个 i，也就是存在 i 使得 p _ i > r，即 lx _ {l, r} \le r。

  其次要保证 [i + 1, r] 与前面的 [1, l - 1] 无关。

  也就是 [l, r] 最后面的满足 p _ j < l 的 j 不在 [i + 1, r] 中，即 ry _ {l, r} \le i（也可 ry _ {l, r} < i）。

  转移

  放入 i 一定是合法的。所以只需判 f _ {l, i - 1} 和 f _ {i + 1, r} 的合法性即可。

  这时 pg 数组不需记录信息，具体见「查找每个数放入的栈」。

  if (lx[l][r] <= r) // 第一种情况
  {
    now = lx[l][r];
    if (ry < now) g[l][r] = f[l][now - 1] & f[now + 1][r];
  }

• 第二种：f \leftarrow g + f

  概念

  如上图，我们选择最前面的满足 p _ i > r 的 i 即 lx _ {l, r}，然后把这个序列分成 [l, i - 1]、i 和 [i + 1, r] 三段。

  对于 [l, i - 1] 这段，把它们放进同一个栈（左边）。

  对于 i，把它放进另一个栈（右边），它不会产生任何消除。

  对于 [i + 1, r]，把它们放进另一个栈（右边），这时它们会把 [l, i - 1] 这部分剩下的全部消掉。

  这样我们就不会在同一个栈（左边）剩东西，从而实现了 f 的转移。

  为什么 i 一定是最后消除的呢？理由同第一种情况。

  读者不妨可以模拟一下上图的具体过程。

  前提

  首先得保证存在这么一个 i，也就是存在 i 使得 p _ i > r，即 lx _ {l, r} \le r。

  其次必须满足两个条件之一：

  2. 不存在 (j, k)（l \le j < i < k \le r）满足 p _ j < p _ k <l， 也就是不存在 p _ k（i < k \le r）满足 xl _ {l, i - 1} < p _ k < l，即 ly _ {l, i - 1} > r（也可 ly _ {l, i} > r）。

  这里简要说明一下第二个条件。

  如果存在 (j, k) 满足 p _ j < p _ k < l，根据性质，p _ j, p _ k 在同一个栈中且 p _ k 在 p _ j 上面，这样 j 就无法和 p _ j 消去（p _ j 被 p _ k 卡住了）。

  总而言之就是要满足 [l, i - 1] 的「有用的数」都在同一个栈的最顶部。

  而区间 [l, r] 本身就满足「有用的数」在同一个栈的最顶部，所以可能造成干扰的是 [i + 1, r] 这一部分，而不用考虑后面的部分。

  转移

  放入 i 一定是合法的。所以只需判 g _ {l, i - 1} 和 f _ {i + 1, r} 的合法性即可。

  这时 pf 数组不需记录信息，具体见「查找每个数放入的栈」。

  if (lx[l][r] <= r) // 第二种情况
  {
    now = lx[l][r];
    if (xl[now] == l || r < ly[now])
    {
        f[l][r] = g[l][now - 1] & f[now + 1][r];
    }
  }

• 第三种：both \leftarrow f + f + both

  概念

  如上图，这种情况当前区间不会产生剩余。于是我们选择 p _ i > i 的 i。

  然后把区间分成 [l, i - 1]、i、[i + 1, p _ i - 1]、p _ i 和 [p _ i + 1, r] 五段。

  对于 [l, i - 1] 这段，把它们放入另一个栈（右边）。

  对于 i，把它放入同一个栈（左边），这时它不会产生任何消除。

  对于 [i + 1, p _ i - 1] 这段，把它们放入另一个栈（这时是左边），这时它们会把 [l, i - 1] 这部分剩下的全部消掉。

  为什么这时候另一个栈是左边呢？因为左边的栈已经被 i 堵住了，相当于是空栈（没用），但右边的栈很可能是「有用的栈」。

  对于 p _ i，把它放入另一个栈（右边），它已经和 i 配好对，等待 i 上面的数被消除即可。

  对于 [p _ i + 1, r] 这段，把它们全部消掉，这时它们会把 [i + 1, p _ i - 1] 这部分剩下的全部消掉。

  最后消掉 i 和 p _ i。这样我们就不会剩东西，从而实现了 both 的转移。

  很显然，i 和 p _ i 是最后消去的。

  读者不妨可以模拟一下上图的具体过程。

  前提

  首先要保证没有剩余，即 lx _ {l, r} > r。

  然后枚举 i 的时候，要保证 [i + 1, r] 与前面的 [1, l - 1] 无关（否则就会被 i 堵住），即 ry _ {l, r} \le i（也可 ry _ {l, r} < i）。

  还有要保证 [p _ i + 1, r] 与 [l, i - 1] 无关（否则就会被 p _ i 堵住），即 yr _ {l, i - 1} < p _ i（也可 yr _ {l, i - 1} \le p _ i）。

  转移

  放入 i, p _ i 和消除 i, p _ i 一定是合法的。

  所以只需判 f _ {l, i - 1}、f _ {i + 1, p _ i - 1} 和 both _ {p _ i + 1, r} 的合法性即可。

  这时 pboth 数组需要记录 i，具体见「查找每个数放入的栈」。

  if (lx[l][r] > r) // 第三种情况
  {
    for (int i = l, yr = l; i <= r; i ++)
    {
        if (p[i] < yr) continue;
        if (ry < i)
        {
            tmp = f[l][i - 1] & f[i + 1][p[i] - 1] & both[p[i] + 1][r];
            if (both[l][r] = tmp) {pboth[l][r] = i; goto skip;}
        }
        yr = p[i];
    }
    skip:;
  }

• 第四种：both \leftarrow g + f + both

  概念

  如上图，这种情况当前区间不会产生剩余。于是我们选择 p _ i > i 的 i。

  然后把区间分成 [l, i - 1]、i、[i + 1, p _ i - 1]、p _ i 和 [p _ i + 1, r] 五段。

  对于 [l, i - 1] 这段，把它们放入同一个栈（左边）。

  对于 i，把它放入另一个栈（右边），这时它不会产生任何消除。

  对于 [i + 1, p _ i - 1] 这段，把它们放入另一个栈（右边），这时它们会把 [l, i - 1] 这部分剩下的全部消掉。

  对于 p _ i，把它放入同一个栈（左边），它已经和 i 配好对，等待 i 上面的数被消除即可。

  对于 [p _ i + 1, r] 这段，把它们全部消掉，这时它们会把 [i + 1, p _ i - 1] 这部分剩下的全部消掉。

  最后消掉 i 和 p _ i。这样我们就不会剩东西，从而实现了 both 的转移。

  很显然，i 和 p _ i 是最后消去的。

  读者不妨可以模拟一下上图的具体过程。

  前提

  首先要保证没有剩余，即 lx _ {l, r} > r。

  其次枚举 i 的时候，类似第二种情况，必须满足两个条件之一：

  2. 不存在 (j, k)（l \le j < i < k \le r）满足 p _ j < p _ k <l， 也就是不存在 p _ k（i < k \le r）满足 xl _ {l, i - 1} < p _ k < l，即 ly _ {l, i - 1} > r（也可 ly _ {l, i} > r）。

  理由同第二种情况。

  然后要保证 [p _ i + 1, r] 与前面的 [1, l - 1] 无关（否则就会被 p _ i 堵住），即 ry _ {l, r} \le p _ i（也可 ry _ {l, r} < p _ i）。

  还有要保证 [p _ i + 1, r] 与 [l, i - 1] 无关（否则就会被 p _ i 堵住），即 yr _ {l, i - 1} < p _ i（也可 yr _ {l, i - 1} \le p _ i）。

  转移

  放入 i, p _ i 和消除 i, p _ i 一定是合法的。

  所以只需判 g _ {l, i - 1}、f _ {i + 1, p _ i - 1} 和 both _ {p _ i + 1, r} 的合法性即可。

  这时 pboth 数组需要记录 p _ i，具体见「查找每个数放入的栈」。

  if (lx[l][r] > r) // 第四种情况
  {
    for (int i = l, yr = l; i <= r; i ++)
    {
        if (p[i] < yr) continue;
        if ((xl[i] == l || r < ly[i]) && ry < p[i])
        {
            tmp = g[l][i - 1] & f[i + 1][p[i] - 1] & both[p[i] + 1][r];
            if (both[l][r] = tmp) {pboth[l][r] = p[i]; goto skip;}
        }
        yr = p[i];
    }
    skip:;
  }

• 第五种：both \leftarrow g + both

  概念

  如上图，我们选择 p _ i 最小的 i 即 p _ {xl _ {l, r}}，然后把这个序列分成 [l, i - 1]、i 和 [i + 1, r] 三段。

  对于 [l, i - 1] 这段，把它们放进同一个栈（左边）。

  对于 i，把它放进另一个栈（右边），这时它不会产生任何消除。

  对于 [i + 1, r]，把它们全部消去，这时它们会把 [l, i - 1] 这部分剩下的全部消掉。

  这样我们就不会剩东西，从而实现了 both 的转移。

  很显然，i 是最后消去的。那为什么一定是 i 呢？

  因为根据性质 p _ i < p _ j < l 的 j 肯定比它先消去（否则就堵住了），对于 p _ j \ge l 的 j 肯定存在一种方式让 j, p _ j 先消去。

  当然也可以不选择那种方式，但是这段区间就可以拆成两个 both 的区间相加了。

  读者不妨可以模拟一下上图的具体过程。

  前提

  首先要保证没有剩余，即 lx _ {l, r} > r。

  其次要保证要存在这个 i，也就是存在 p _ i < l 的 i，即 xl _ {l, r} < l（其实也可以判 ry _ {l, r} \ge l，上文的 lx 同样可以换成判 yr）。

  然后类似第二种情况，必须满足两个条件之一：

  2. 不存在 (j, k)（l \le j < i < k \le r）满足 p _ j < p _ k <l， 也就是不存在 p _ k（i < k \le r）满足 xl _ {l, i - 1} < p _ k < l，即 ly _ {l, i - 1} > r。

  理由同第二种情况。

  转移

  放入 i 一定是合法的。所以只需判 g _ {l, i - 1} 和 both _ {i + 1, r} 的合法性即可。

  这时 pboth 数组需要记录 -i，具体见「查找每个数放入的栈」。

  if (lx[l][r] > r) // 第五种情况
  {
    if (xl[r] < l)
    {
        now = p[xl[r]];
        if (xl[now - 1] == l || r < ly[now - 1])
        {
            tmp = g[l][now - 1] & both[now + 1][r];
            if (both[l][r] = tmp) pboth[l][r] = -now;
        }
    }
  }

容易发现只有这几种情况，分别转移即可。

对于第二、四、五种情况，其实如果预处理 ly _ {i, i - 1}，那么前提两个条件中的第一个条件可以略去。

因为当 xl _ {l, i} = l 时，ly _ {l, i} 一定等于无穷大，也就是满足 ly _ {l, i} > r。只是作者太懒了代码不想改 qwq。

目标状态

如果 both _ {1, n} = 1，则有解（输出 Cleared.）；否则无解（输出 No solution）。

关于 both 数组的补充说明

很显然，当 [l, r] 内没有剩余即 lx _ {l, r} > r 时，both 数组取 f 和 g 任意一个都行（相当于把空集堆在任意一个栈）。

因此我们转移时可以把 both 都换成 f，转移后再把 g \leftarrow f 就可以了。

记录上一个状态的数组 pboth 也可换成 pf，转移后再把 pg \leftarrow pf 即可。

关于性质的粗略证明

证明：

考虑用数学归纳法。命题对于 [1, n] 显然成立（都没有「有用的数」）。

设命题对于 [l, r] 成立，接下来证明命题对于由它分割的一个子区间 [l ^ \prime, r ^ \prime] 依然成立。

对于第一种情况（g = f + f），[l, r] 的「有用的数」都是 [l, i - 1] 的，命题对于 [l, i - 1] 显然成立；

而前提保证 [i + 1, r] 的「有用的数」都在 [l, i - 1] 中被堆在了另一个栈且只剩下「有用的数」，命题也成立。

对于第二种情况（f = g + f），根据我们在第二种情况时的讨论，命题对于 [l, i - 1] 显然成立；

而 [i + 1, r] 的「有用的数」要么就在之前「有用的栈」的最顶部，要么就在 [l, i - 1] 剩下的当中，命题也成立。

因为前提保证了 [l, i - 1] 只会剩下「有用的数」，所以「有用的数」仍在同一个栈的最顶部。

对于第三种情况（both = f + f + both），同第一种情况，命题对于 [l, i - 1] 显然成立；

命题对于 [i + 1, p _ i - 1] 同样成立，理由同第一种情况；

前提保证了 [1, l - 1] 和 [l, i - 1] 部分都没有 [p _ i + 1, r] 的「有用的数」，所以「有用的数」只会在 [i + 1, p _ i - 1] 当中，命题也成立。

因为前提保证了 [p _ i + 1, r] 只会剩下「有用的数」，所以「有用的数」仍在同一个栈的最顶部。

对于第四种情况（both = g + f + both），同第二种情况，命题对于 [l, i - 1] 显然成立；

命题对于 [i + 1, p _ i - 1] 同样成立，理由同第二种情况；

对于 [p _ i + 1, r] 这部分同第三种情况，命题也成立。

对于第五种情况（both = g + both），同第二种情况，命题对于 [l, i - 1] 显然成立；

命题对于 [i + 1, r] 同样成立，理由同第二种情况。

证毕。

Part 3：求具体方案

首先容易发现 op = \frac 3 2 n，因为每个数都被进行了一次加入操作，两个数一组被进行了一次消除操作。

查找每个数放入的栈

设 gt _ i 为第 i 个数应该放入的栈。gt _ i = 0 表示放入栈 1，gt _ i = 1 表示放入栈 2。

记 pre _ {l, r, w} = \begin {cases} pf _ {l, r} & (w = 1) \\ pg _ {l, r} & (w = 0) \end {cases}，可以有效简化步骤。

特别提醒：根据「关于 both 数组的补充说明」，此时 both 数组已并入 f 和 g 中， pboth 数组已并入 pf 和 pg 中。

考虑递归查找。需要传入四个参数：l, r, w, d，表示当前递归到区间 [l, r]，是第 w 种转移方式，同一个栈为栈 d。

这里 w = 1 表示转移方式 f，w = 0 表示转移方式 g；d = 0 表示栈 1，d = 1 表示栈 2。

查找的入口为区间 [1, n]，我们钦定 w = d = 0。

如果当前递归查找的区间为 [l, r]，是第 w 种转移方式，同一个栈为栈 d + 1，分几种情况：

• 第一、二种情况

  判定

  如果满足 lx _ {l, r} \le r，那么说明是第一、二种情况。

  查找分界点放入的栈

  不管是第一种情况还是第二种情况，分界点都是 lx _ {l, r}。

  然而还要考虑 w 的影响。发现 f 的分界点被放入另一个栈，而 g 的分界点被放入同一个栈。也就是说 w = 1 时要反过来。

  总结规律可以得出 gt _ {lx _ {l, r}} = w ~ \mathrm {xor} ~ d。

  递归

  第一种情况是 g = f + f，第二种情况是 f = g + f。

  发现两种情况的共同点是都只有两个子区间，其中左边子区间的转移方式与当前区间相反，且右边子区间转移方式为 f。

  而左边子区间同一个栈与当前区间相同，右边子区间同一个栈如果 w = 0 那么还要反过来。

  所以分别递归 (l, lx _ {l, r} - 1, !w, d) 和 (lx _ {l, r} + 1, r, 1, !w ~ \mathrm {xor} ~ d)。

• 第三种情况

  判定

  如果满足 lx _ {l, r} > r 且 pre _ {l, r, w} > 0 且 pre _ {l, r, w} < p _ {pre _ {l, r, w}}，那么说明是第三种情况。

  查找分界点放入的栈

  靠左的分界点 pre _ {l, r, w} 会被放入同一个栈，靠右的分界点 p _ {pre _ {l, r, w}} 会被放入另一个栈。

  令 gt _ {pre _ {l, r, w}} = d，gt _ {p _ {pre _ {l, r, w}}} = ~ !d。

  递归

  三个子区间转移方式都为 f（这里我们把右边子区间的转移方式钦定为 f）。

  左边子区间同一个栈与当前区间相同，中间子区间同一个栈与当前区间相反，右边子区间同一个栈与当前区间相同。

  所以分别递归 (l, pre _ {l, r, w} - 1, 1, d)、(pre _ {l, r, w} + 1, p _ {pre _ {l, r, w}} - 1, 1, !d) 和 (p _ {pre _ {l, r, w}} + 1, r, 1, d)。

• 第四种情况

  判定

  如果满足 lx _ {l, r} > r 且 pre _ {l, r, w} > 0 且 pre _ {l, r, w} > p _ {pre _ {l, r, w}}，那么说明是第四种情况。

  查找分界点放入的栈

  靠左的分界点 p _ {pre _ {l, r, w}} 会被放入另一个栈，靠右的分界点 pre _ {l, r, w} 会被放入同一个栈。

  令 gt _ {p _ {pre _ {l, r, w}}} = ~ !d，gt _ {pre _ {l, r, w}} = d。

  递归

  左边子区间转移方式为 g，其它子区间转移方式都为 f（这里我们把右边子区间的转移方式钦定为 f）。

  左边子区间同一个栈与当前区间相同，中间子区间同一个栈与当前区间相同，右边子区间同一个栈与当前区间相反。

  所以分别递归 (l, p _ {pre _ {l, r, w}} - 1, 0, d)、(p _ {pre _ {l, r, w}} + 1, p _ {l, r, w} - 1, 1, d) 和 (p _ {l, r, w} + 1, r, 1, !d)。

• 第五种情况

  判定

  如果满足 lx _ {l, r} > r 且 pre _ {l, r, w} < 0，那么说明是第五种情况。

  查找分界点放入的栈

  分界点 -pre _ {l, r, w} 会被放入另一个栈。

  令 gt _ {-pre _ {l, r, w}} = ~ !d。

  递归

  左边子区间转移方式为 g，右边子区间转移方式我们钦定为 f。

  左边子区间和右边子区间同一个栈都与当前区间相同。

  所以分别递归 (l, -pre _ {l, r, w} - 1, 0, d) 和 (-pre _ {l, r, w} + 1, 1, d)。

模拟具体操作

得出 gt 数组后，我们从前往后遍历每一个数。设当前遍历到位置 i，数为 A _ i。

首先如果 gt _ i = 0，那么输出 1；否则输出 2。然后把 A _ i 压入对应的栈中。

在栈顶数字相同的情况下，一直输出 0 并弹出两边栈顶。

于是我们就可以愉快地搞定一道黑题啦。下面附上 AC 代码：

AC Code

#include <cstdio>
#include <cstring>
#define inf 0x3f3f3f3f
#define N 1505
#define min(x,y) ((x)<(y)?(x):(y))
using namespace std;

int n, a[N], l[N], p[N], gt[N], pf[N][N], pg[N][N];
int lx[N][N], xl[N], ly[N], tr[N];
int top[2], st[2][N]; // 数组模拟栈
bool tmp, f[N][N], g[N][N];

int &pre (int i, int j, bool k) // 合并两个数组为一个函数
{
    return k ? pf[i][j] : pg[i][j];
}

// 这里的树状数组写法有些不同，实现的是单点修改，区间（后缀）询问

void modify (int p, int c) // 树状数组加入元素
{
    for (; p; p &= p - 1) tr[p] = min (tr[p], c);
    return ;
}

int ask (int p) // 树状数组询问
{
    int res = inf;
    for (; p <= n; p += p & -p) res = min (res, tr[p]);
    return res;
}

void dfs (int l, int r, bool w, bool d) // dfs 求具体方案
{
    if (l > r) return ;
    if (lx[l][r] <= r)
    {
        gt[lx[l][r]] = w ^ d;
        dfs (l, lx[l][r] - 1, !w, d);
        dfs (lx[l][r] + 1, r, 1, !w ^ d);
    }
    else
    {
        if (pre (l, r, w) > 0)
        {
            gt[pre (l, r, w)] = d;
            gt[p[pre (l, r, w)]] = !d;
            if (pre (l, r, w) < p[pre (l, r, w)])
            {
                dfs (l, pre (l, r, w) - 1, 1, d);
                dfs (pre (l, r, w) + 1, p[pre (l, r, w)] - 1, 1, !d);
                dfs (p[pre (l, r, w)] + 1, r, 1, d);
            }
            else
            {
                dfs (l, p[pre (l, r, w)] - 1, 0, d);
                dfs (p[pre (l, r, w)] + 1, pre (l, r, w) - 1, 1, d);
                dfs (pre (l, r, w) + 1, r, 1, !d);
            }
        }
        else
        {
            gt[-pre (l, r, w)] = !d;
            dfs (l, -pre (l, r, w) - 1, 0, d);
            dfs (-pre (l, r, w) + 1, r, 1, d);
        }
    }
    return ;
}

int main ()
{
    scanf ("%d", &n), f[1][0] = g[1][0] = 1; // 初始化
    for (int i = 1; i <= n; i ++)
    {
        scanf ("%d", &a[i]);
        if (l[a[i]]) p[l[a[i]]] = i, p[i] = l[a[i]]; // 预处理
        l[a[i]] = i, f[i + 1][i] = g[i + 1][i] = 1; // 初始化
    }
    for (int r = 1; r <= n; r ++)
    {
        lx[r + 1][r] = r + 1; // 初始化
        for (int l = r; l; l --) // 预处理
        {
            lx[l][r] = lx[l + 1][r];
            if (p[l] > r) lx[l][r] = l;
        }
    }
    for (int l = n, ry = 0; l; l --, ry = 0)
    {
        xl[l - 1] = l, memset (tr, 0x3f, sizeof tr); // 初始化
        for (int r = l; r <= n; r ++) // 预处理
        {
            xl[r] = min (xl[r - 1], p[r]);
        }
        for (int r = n; r >= l; r --) // 预处理
        {
            ly[r] = ask (xl[r]);
            if (p[r] < l) modify (p[r], r);
        }
        for (int r = l, now; r <= n; r ++) // 区间 dp
        {
            if (p[r] < l) ry = r; // 顺便预处理
            if (lx[l][r] <= r)
            {
                now = lx[l][r];
                if (ry < now) g[l][r] = f[l][now - 1] & f[now + 1][r]; // 第一种情况
                if (xl[now] == l || r < ly[now]) // 第二种情况
                {
                    f[l][r] = g[l][now - 1] & f[now + 1][r];
                }
            }
            else
            {
                for (int i = l, yr = l; i <= r; i ++)
                {
                    if (p[i] < yr) continue;
                    if (ry < i) // 第三种情况
                    {
                        tmp = f[l][i - 1] & f[i + 1][p[i] - 1] & f[p[i] + 1][r];
                        if (f[l][r] = tmp) {pf[l][r] = i; goto skip;}
                    }
                    if ((xl[i] == l || r < ly[i]) && ry < p[i]) // 第四种情况
                    {
                        tmp = g[l][i - 1] & f[i + 1][p[i] - 1] & f[p[i] + 1][r];
                        if (f[l][r] = tmp) {pf[l][r] = p[i]; goto skip;}
                    }
                    yr = p[i]; // 顺便预处理
                }
                if (xl[r] < l)
                {
                    now = p[xl[r]];
                    if (xl[now - 1] == l || r < ly[now - 1]) // 第五种情况
                    {
                        tmp = g[l][now - 1] & f[now + 1][r];
                        if (f[l][r] = tmp) pf[l][r] = -now;
                    }
                }
                skip:; g[l][r] = f[l][r], pg[l][r] = pf[l][r]; // 关于 Both 的处理
            }
        }
    }
    puts (f[1][n] ? "Cleared." : "No solution.");
    if (!f[1][n]) return 0;
    printf ("%d\n", n / 2 * 3), dfs (1, n, 0, 0);
    for (int i = 1; i <= n; i ++) // 模拟
    {
        putchar ('1' + gt[i]), st[gt[i]][++ top[gt[i]]] = a[i];
        while (top[0] && top[1] && st[0][top[0]] == st[1][top[1]])
        {
            putchar ('0'), top[0] --, top[1] --;
        }
    }
    return 0;
}

题解若有问题欢迎在评论区反馈。