题解：P11344 [KTSC 2023 R1] 会议室（无法评测）

NTT__int128 · 2026-04-28 21:44:01 · 题解

HN 省队学长好题分享的。

不难发现，一开始 n 个数是互不相同的，尝试强化一下，使得每次操作后，都有相邻两个数互不相同。

考虑对于相邻两个数 x,y，取最大的 i，满足 x 的第 i 位为 1 且 y 的第 i 位为 0。

但是这么做是没有道理的，因为可能不存在。考虑对于每一个 v，给定其一个权值 s_v，然后用 s 来计算上面的那个东西。

然后，为了让每次 i 都存在，对于每个 s，都给定其一个两两不同的 20 位二进制数，且其在二进制下 1 的个数为 10 个。这样就做完了 morning，成功把值域降到了 [0,19]。

对于 afternoon，用类似的方法，先假装自己只知道右边的数，用 morning 的方式维护，再“预测”出左边的人想改成什么，用同样的方式维护。这么做可以将值域降到 [0,3]。

尝试对 evening 用同样的方法处理，发现不可行。但由于值域只有 [0,3]，因此，对于 \le2 的不动，3 就改成任意（策略需要一样）左右两边没有出现的数。

代码：https://qoj.ac/submission/2295188。