题解：P15651 [省选联考 2026] 夜空 / night
本文深受 这份题解 启发，拜谢 zjy2008！
观察操作的本质，不难发现两种操作都是将相邻两个元素合并起来，然后在环上将起始位置移动一位。因此，目标序列中每个元素对应原序列在环上的一个区间（下面称为块）。
接下来，不妨从特殊性质 B 入手考虑问题。
::::info[特殊性质 B]{open} 此时原序列和目标序列的最左侧都恰好包含了 3 个 1，而剩余的数字都是偶数。不难发现，除了两侧的 1 可以和 0 合并之外，其余情况下 1 不应该参与到合并流程中。接下来，从 1 所在的位置将序列断成两半，左侧可以看作一个空的栈，而右侧可以看作一个包含所有偶数的栈。
在这个背景下，考虑对偶数进行操作，考虑过程中每个元素对应的块，可以注意到如下事实：在左侧栈的元素对应的块大小总是模 3 余 2，而在右侧栈的元素对应的块大小总是模 3 余 1。因此，最终的目标就是将所有偶数断成若干个长度模 3 余 1 的段，并且需要处理块长度为 1 的特殊情况（因为它不能被操作）。
在构造时，若需要将一整个块将右侧放到左侧，则可以先通过 2 2 1 操作将最右边的四个值合并为一个，直到块长度被缩减到 4 时，通过 2 2 操作将其移动到左侧；若需要将一整个块从左侧放到右侧，考虑到此时块长度恰好为 2，通过 1 操作即可实现。在这一构造下，所有大块都只需要恰好两次整体移动就能正确合并。
::::
上面的讨论实际上具有一定的启发意义：几乎所有的块都可以被分成三类：
- 长度为 1 的块，不应该被移动；
- 长度模 3 余 2 的块，需要整体移动奇数次（根据后面的分析，可以等价于 1 次）；
- 长度不为 1 且模 3 余 1 的块，需要整体移动偶数次（根据后面的分析，可以等价于 2 次）。
接下来继续考虑特殊性质 C。
::::info[特殊性质 C]{open} 此时原序列和目标序列中都出现了连续 3 个 1，不妨假设它们都出现在序列的中间，而不是左右两侧。此时依然可以使用两个栈的思路考虑，但会出现两个问题：
- 首先，和特殊性质 B 不同，左侧栈并不一定是空的，在特殊性质 B 中只需要将大块同时移到左边，再同时移到右边，而在特殊性质 C 中则需要考虑块的整体移动能不能通过某种规划连接起来；
- 其次，因为左侧栈不一定是空的，某一个块可能会同时出现在左侧栈顶部和右侧栈顶部。考虑到初始步骤无论怎么操作都只能对这个块内部进行调整，因此第一步应该是尽快将跨栈的块元素全部移动到左侧栈或右侧栈，从而为后续操作留足空间。
假设所有块被通过如下方式编号：
| k | k+1 | ... | m | "1 1 1" | 1 | 2 | ... | k' |下面使用
接下来考虑第
- 如果需要将其整体从右边移到左边，那么相当于状态从
(k + 1, k) 变为(k, k - 1) ，也即从状态k+1 变为状态k ； - 如果需要将其整体从左边移到右边，那么相当于状态从
(k, k - 1) 变为(k + 1, k) ，也即从状态k 变为状态k+1 。
因此，每个块的整体移动次数需求就被转化为状态
- 所有边的两端都可以从初始状态到达，也就是连通性要求；
- 整张图必须存在一条从起点到终点的欧拉路径，除了连通性要求之外，如果额外添加一条起点到终点的无向边，它还要求所有点的度数都是偶数。
使用动态规划进行分块，在考虑第
- 状态
k 是否能通过边到达结束状态； - 状态
k 是否为起点状态； - 状态
k-1 向状态k 连接的边数。
如果第
另外，考虑到欧拉回路判定只和度数奇偶性与连通性相关，所以移动
上述动态规划在没有任何优化的情况下时间复杂度是大常数
在解决了特殊性质 C 之后，回到原问题，可以发现所需的大多数性质已经在特殊性质 C 部分讨论过了。状态设计是类似的，只是在原问题中，双栈的概念已经不复存在了，因此状态的定义需要稍加修改：
- 设状态
(k, k') 表示序列最左侧元素属于b_k 对应的块，而最右侧元素属于b_{k'} 对应的块。此时不难发现在大多数情况下依然有k' = k - 1 ，而只有在跨环块或块移动的中途会出现k' = k 的情况。不难发现，状态整体对应的性质和特殊性质 C 中给出的性质是高度相似的。在这一设计下，结束状态必须是状态1 。
2026/3/11 补充：下面的状态设计较为复杂，文末给出了一个更简单的设计，但最后依然需要使用“只取最短长度”的方式降低复杂度。
接下来是精细化的状态设计。状态设计可以表示为一个六元组
- 当前已经考虑了前
k 个块，在连通性和度数上没有出现问题； - 第一个块的左端点对应元素
a_l ，而第k 个块的右端点对应元素a_r ； - 从状态
k-1 向状态k 连接了\text{link} 条边； - “仅通过目前已经添加的边，状态
k 能到达状态1 ” 问题的结果是\text{access} ； - “在考虑的所有状态（也就是编号在
[1, k] 范围内的状态）中，包含了起始状态”问题的结果是\text{start} 。
状态空间为
接下来考虑状态的转移。对于
如果在枚举时考虑的是所有区间异或和等于
- 如果在同一个类型下选择了较长的一个块，则在这块的右侧会形成一段长度为
3 的倍数，而异或和为0 的“气泡”。这个气泡可以从当前块的末尾移动到下一个块的开头，直到气泡消失或回到第一个块。因此，只要在第一个块时枚举所有可能的区间，就能处理掉气泡回到第一个区间的情况，也就能保证剩下的块都是极小的。
因此，第一个块对应的转移是 1 1 2 和 2 2 1 将块长度压缩到 1、2 和 4 之一，此时再进行整体移动就很方便了。
最终的时间复杂度就是
::::info[代码]
// https://qoj.ac/submission/2107883
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <bitset>
#include <set>
using namespace std;
int t, n, m;
int a[510], b[260];
int pa[510];
int que(int l, int r) {
return pa[r] ^ pa[l - 1];
}
/*
(u, v) 表示中间状态中最左侧值属于 b[u]，而最右侧值属于 b[v]
第 k 块可以切换状态 (k, k-1) 和 (k+1, k)
最开始可能位于 (u, u) 或 (u, u - 1)，需要经过变换到达 (1, m)
下面将状态 (i, i - 1) 简称为状态 i。
以下状态设计的结果是布尔的（也就是只关心能不能到达这个状态）
l - 第 1 块的起始位置（使用 bitset 表示）
k - 当前枚举的块号
r - 第 k 块的结束位置
lnk - 当前的图结构中，状态 k+1 包含的边数
acc - 当前的图结构中，状态 1 能否到达状态 k+1
这个状态用于处理中间断开的连通块
odd - 奇偶性是否受到过干预
为了将欧拉回路和欧拉路径一起处理，
可以将起始状态和最终状态之间连边
在加上这条边之后，所有状态必须是偶度数的。
在代码中，我们并不在于状态 1 的奇偶性，其他状态是偶度数即可。
在处理第 k (k > 1) 块时，会处理状态 k 的奇偶性。
如果第 k 个块的起始位置恰好是 a[1]，
那么状态 k 一定是起始状态，
因此它立刻受到这条边的干预，度数需求逆转
否则，如果第 k 个块同时包含 a[n] 和 a[1]：
- 如果其转移到状态 k，那么需要立马实行干预；
- 如果其转移到状态 k+1，则干预会在下一个块执行，
下一个块的触发条件是：
“已经绕了一周（l > n），而没有受过干预（odd = false）”
*/
struct State {
int r; // [1, 2 * n]
int k; // [1, m]
int lnk; // [0, 2]
bool acc; // [0, 1]
bool odd; // [0, 1]
// 状态空间为 24 n m
int id() const {
int res = k - 1;
res = res * (2 * n) + r - 1;
res = res * 3 + lnk;
res = res * 2 + acc;
res = res * 2 + odd;
return res;
}
};
bitset<251> dp[1500000];
vector<State> from[1500000];
void from_to(State dest, State src) {
dp[dest.id()] |= dp[src.id()];
from[dest.id()].push_back(src);
}
/*
状态的更新函数
k 是当前块的编号
nl 是第 k 块的开始位置
nr 是第 k 块的结束位置
lnk 表示受到第 k 块影响，从状态 k 到状态 k+1 的边数
start 表示状态 k 是不是起始状态
*/
void update(int k, int nl, int nr, int lnk, bool start) {
if (k == 1) {
dp[State(nr, k, lnk, lnk != 0, start).id()][nl] = 1;
return;
}
int pr = nl - 1;
for (int plnk : {0, 1, 2})
for (bool pacc : {false, true})
for (bool podd : {false, true}) {
// 形成了不连通的部分
if (!pacc && plnk != 0 && lnk == 0) continue;
// 状态 k 是否受到干预
bool infected = start || (nl > n && !podd);
// 在干预下，状态 k 的奇偶性是否正确
if ((infected + plnk + lnk) & 1) continue;
State pre(pr, k - 1, plnk, pacc, podd);
State nxt(
nr, k, lnk,
pacc && (lnk != 0),
podd || infected
);
from_to(nxt, pre);
}
}
int target_l;
int st_state;
pair<int, int> blocks[260];
int len[260];
multiset<int> g[260];
void dfs(State st) {
int u = st.k, v = st.k % m + 1;
for (int _ = 0; _ < st.lnk; _ ++) {
g[u].insert(v);
g[v].insert(u);
}
if (st.k == 1) {
if (st_state == 0)
st_state = 1;
blocks[1] = {target_l, st.r};
return;
}
for (auto pre : from[st.id()]) if (dp[pre.id()][target_l]) {
blocks[st.k] = {pre.r + 1, st.r};
if (st.odd && !pre.odd) st_state = st.k;
dfs(pre);
return;
}
}
int main() {
int _;
scanf("%d%d", &_, &t);
while (t --) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++)
scanf("%d", &a[i]), a[i + n] = a[i];
for (int i = 1; i <= 2 * n; i ++)
pa[i] = pa[i - 1] ^ a[i];
for (int i = 1; i <= m; i ++)
scanf("%d", &b[i]);
if (m == 1) {
if (pa[n] != b[1]) {
puts("No");
} else {
puts("Yes");
for (int i = 1; i < n; i ++)
printf("1 ");
puts("");
}
continue;
}
for (int i = 0; i < 24 * n * m; i ++)
dp[i].reset(), from[i].clear();
for (int k = 1; k <= m; k ++) {
for (int bl = k; bl <= (k == 1 ? n : 2 * n); bl ++) {
// 需要注意，在 k > 1 的时候，只需要选取同情况下最短的区间
// 如果有多个区间，则长区间会在最后形成
// 长度为 3 的倍数，而异或和为 0 的“气泡”
// 气泡可以传递到下一个块，过程不断持续到气泡消失或者回到第一个块
// 回到第一个块的情况通过在 k = 1 时枚举所有可能的区间处理
// 第一部分：不同时包含 a[n] 和 a[1]
int targ = (bl > n) ? 2 * n : n;
for (int dlen : {0, 1}) {
for (int br = bl + dlen; br <= targ; br += 3) {
if (que(bl, br) != b[k]) continue;
if (bl == br)
update(k, bl, br, 0, bl == 1 || bl == n + 1);
else if (dlen == 0) {
update(k, bl, br, 2, bl == 1 || bl == n + 1);
if (k != 1) break;
} else {
update(k, bl, br, 1, bl == 1 || bl == n + 1);
if (k != 1) break;
}
}
}
if (bl <= n) {
// 第二部分：同时包含 a[n] 和 a[1]，并选择先放在左边
// 这会导致起始状态为状态 k
// 这一部分的长度最多为 n - m + 1
// 另外，这里不需要考虑 br 的奇偶性，所以枚举 mod 3 即可
for (int dlen : {0, 1, 2}) {
for (int br = n + dlen + 1; br <= bl + n - m; br += 3) {
if (que(bl, br) != b[k]) continue;
int lhs = br - n, rhs = n - bl + 1;
if (rhs & 1) rhs ++, lhs -= 2;
if (lhs < 0) continue;
lhs += rhs / 2;
if (lhs == 1) {
update(k, bl, br, 0, true);
} else if (lhs % 3 == 1) {
update(k, bl, br, 2, true);
if (k != 1) break;
} else if (lhs % 3 == 2) {
update(k, bl, br, 1, true);
if (k != 1) break;
}
}
}
// 第三部分：同时包含 a[n] 和 a[1]，并选择先放在右边
// 这会导致起始状态为状态 k + 1
// 另外，这里需要考虑 br 的奇偶性，所以需要枚举 mod 6
for (int dlen : {0, 1, 2, 3, 4, 5}) {
for (int br = n + dlen + 1; br <= bl + n - m; br += 6) {
if (que(bl, br) != b[k]) continue;
int lhs = br - n, rhs = n - bl + 1;
if (lhs & 1) lhs ++, rhs -= 2;
if (rhs < 0) continue;
rhs += lhs / 2;
if (rhs == 1) {
update(k, bl, br, 0, false);
} else if (rhs % 3 == 1) {
update(k, bl, br, 2, false);
if (k != 1) break;
} else if (rhs % 3 == 2) {
update(k, bl, br, 1, false);
if (k != 1) break;
}
}
}
}
}
}
st_state = 0;
for (int i = 1; i <= m; i ++)
g[i].clear();
bool flg = false;
for (int l = 1; l <= n; l ++) {
for (int lnk : {0, 1, 2}) if (!flg)
for (bool acc : {false, true}) if (!flg)
for (bool odd : {false, true}) if (!flg) {
State p(l + n - 1, m, lnk, acc, odd);
if (dp[p.id()][l]) {
flg = true;
target_l = l;
dfs(p);
}
}
}
if (!flg) {
puts("No");
continue;
}
puts("Yes");
for (int i = 1; i <= m; i ++)
len[i] = blocks[i].second - blocks[i].first + 1;
auto comb_left = [&] () {
printf("1 1 2 ");
};
auto comb_right = [&] () {
printf("2 2 1 ");
};
// 进入起始状态
for (int i = 1; i <= m; i ++) if (blocks[i].second > n && blocks[i].first <= n) {
int lhs = blocks[i].second - n;
int rhs = n - blocks[i].first + 1;
if (st_state == i) {
if (rhs & 1)
rhs ++, lhs -= 2, printf("1 ");
while (rhs)
lhs ++, rhs -= 2, printf("2 ");
len[i] = lhs;
} else {
if (lhs & 1)
lhs ++, rhs -= 2, printf("2 ");
while (lhs)
rhs ++, lhs -= 2, printf("1 ");
len[i] = rhs;
}
}
// 搜索欧拉路径
int cur_state = st_state;
bool first = true;
auto node = [&] (int nw) -> void {
if (first) {
first = false;
return;
}
// 这里对 m = 2 的情况进行了隐式的特殊处理
if (nw == cur_state % m + 1 && len[cur_state] > 1) {
int x = cur_state;
// 从左到右
while (len[x] > 4)
len[x] -= 3, comb_left();
if (len[x] == 4)
len[x] -= 2, printf("1 1 ");
else
len[x] --, printf("1 ");
} else {
int x = cur_state == 1 ? m : cur_state - 1;
// 从右到左
while (len[x] > 4)
len[x] -= 3, comb_right();
if (len[x] == 4)
len[x] -= 2, printf("2 2 ");
else
len[x] --, printf("2 ");
}
cur_state = nw;
};
auto dfs = [&] (auto self, int x) -> void {
while (!g[x].empty()) {
int v = *g[x].begin();
g[x].extract(v);
g[v].extract(x);
self(self, v);
}
node(x);
};
dfs(dfs, 1);
puts("");
}
return 0;
}::::
2026/3/11 更新：
实际上，考虑到这张图上相邻两个点之间的连边不超过两条，为了保证图中存在欧拉回路，不难发现只会出现类似“双边 - 单边 - 双边 - 无边”的类型。在这一情况下，钦定终止状态在靠左的“双边 - 单边”边界，而初始状态在靠右的“单边 - 双边”边界，将序列反转即可处理另一半可能性。
在这一设计上，状态转移的辅助参数只需要一个范围在
- 只有单边的段，此时的块长度只能为
3k - 1 类型； - 第一个双边的段，此时的块长度只能为
3k + 1 类型，并且与上一个段的间隔恰好为跨环块； - 无边的段，此时的快长度只能为
1 ； - 第二个双边的段，此时的块长度只能为
3k + 1 类型。
转移则需要根据下一个块的长度确定是否需要跳转到下一个段，以及中间的段是否出现退化情况等。这个写法的常数会比上一个写法小一些，而对于构造，在已知终止状态方位的情况下可以进行贪心构造，具体方式请查看下面的代码。
::::info[更新后的代码]
// https://qoj.ac/submission/2121975
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <bitset>
#include <set>
#include <deque>
using namespace std;
int t, n, m;
int a[510], b[260];
int pa[510];
int que(int l, int r) {
return pa[r] ^ pa[l - 1];
}
/*
状态：
l: 第 1 个块的左端点（bitset）
i：考虑的块数量
j: 第 i 个块的右端点
k: 目前所在的状态
- 0 = 单边状态，允许的长度有 3k - 1
这里经过了环上 n 到 1 的部分
- 1 = 前双边状态，允许的长度有 3k + 1
- 2 = 无边状态，允许的长度只有 1
- 3 = 后双边状态，允许的长度有 3k + 1
*/
bitset<260> dp[260][510][4];
vector<pair<int, int>> pre[260][510][4];
int move_l(int l, int r) {
int lhs = n - l + 1, rhs = r - n;
// 无法放在一侧
if (rhs % 3 == lhs % 3) return -1;
return lhs + rhs / 2 - rhs % 2;
}
int move_r(int l, int r) {
int lhs = n - l + 1, rhs = r - n;
// 无法放在一侧
if (rhs % 3 == lhs % 3) return -1;
return rhs + lhs / 2 - lhs % 2;
}
inline void transfer(int i, int pj, int pk, int nj, int nk) {
if (i == 1) {
dp[i][nj][nk][pj] = 1;
return;
}
dp[i][nj][nk] |= dp[i - 1][pj - 1][pk];
pre[i][nj][nk].push_back({pj, pk});
}
vector<int> solve() {
for (int i = 1; i <= n; i ++)
a[i + n] = a[i];
for (int i = 1; i <= 2 * n; i ++)
pa[i] = pa[i - 1] ^ a[i];
for (int i = 1; i <= m; i ++)
for (int j = 1; j <= 2 * n; j ++)
for (int k : {0, 1, 2, 3})
dp[i][j][k].reset(), pre[i][j][k].clear();
for (int i = 1; i <= m; i ++) {
for (int l = 1 + (i != 1); l <= (i == 1 ? n + 1 : 2 * n); l ++) {
for (int d = 0; d < 3; d ++) {
for (int r = l + d; r <= (l <= n ? n : 2 * n); r += 3) {
if (que(l, r) != b[i]) continue;
int len = r - l + 1;
if (l <= n) {
if (len % 3 == 2) {
transfer(i, l, 0, r, (r == n));
if (i != 1) break;
} else if (len > 1)
break;
} else {
if (len == 1) {
transfer(i, l, 1, r, 2);
transfer(i, l, 2, r, 2);
}
else if (len % 3 == 1) {
transfer(i, l, 1, r, 1);
transfer(i, l, 2, r, 3);
transfer(i, l, 3, r, 3);
if (i != 1) break;
} else
break;
}
}
}
if (l > n)
continue;
for (int d = 0; d < 6; d ++) {
for (int r = n + 1 + d; r <= l + n - m; r += 6) {
if (que(l, r) != b[i]) continue;
int bl = move_l(l, r);
if (bl == -1)
break;
if (bl % 3 == 2) {
transfer(i, l, 0, r, 1);
if (i != 1) break;
} else
break;
}
}
for (int d = 0; d < 6; d ++) {
for (int r = n + 1 + d; r <= l + n - m; r += 6) {
if (que(l, r) != b[i]) continue;
int br = move_r(l, r);
if (br == -1)
break;
if (br == 1)
transfer(i, l, 0, r, 2);
else if (br % 3 == 1) {
transfer(i, l, 0, r, 1);
if (i != 1) break;
} else
break;
}
}
}
}
bool flg = false;
vector<pair<int, int>> segs;
for (int l = 1; l <= n + 1 && !flg; l ++) {
for (int p : {0, 1, 2, 3})
if (dp[m][l + n - 1][p][l]) {
flg = true;
int cur = l + n - 1, cp = p;
for (int it = m; it >= 2; it --) {
for (auto [pj, pk] : pre[it][cur][cp]) if (dp[it - 1][pj - 1][pk][l]) {
segs.push_back({pj, cur});
cp = pk; cur = pj - 1;
break;
}
}
segs.push_back({l, cur});
break;
}
}
if (!flg)
return {-1};
reverse(segs.begin(), segs.end());
vector<int> res;
vector<int> pre, suf;
deque<int> dq;
for (int i = 1; i <= m; i ++) {
int l = segs[i - 1].first, r = segs[i - 1].second;
if (r <= n)
suf.push_back(r - l + 1);
else if (l > n)
pre.push_back(r - l + 1);
else {
int lhs = n - l + 1, rhs = r - n;
if (move_r(l, r) >= move_l(l, r)) {
while (lhs >= 2)
lhs -= 2, ++ rhs, res.push_back(2);
if (lhs == 1)
-- rhs, res.push_back(1), res.push_back(2);
pre.push_back(rhs);
} else {
while (rhs >= 2)
rhs -= 2, ++ lhs, res.push_back(1);
if (rhs == 1)
-- lhs, res.push_back(2), res.push_back(1);
suf.push_back(lhs);
}
}
}
for (int ele : pre) dq.push_back(ele);
for (int ele : suf) dq.push_back(ele);
auto LEFT = [&] () {
while (dq.front() != 1) {
int x = dq.front();
dq.pop_front();
while (x > 4)
x -= 3, res.push_back(1), res.push_back(1), res.push_back(2);
if (x == 4)
x = 2, res.push_back(1), res.push_back(1);
else
x = 1, res.push_back(1);
dq.push_back(x);
}
};
auto RIGHT = [&] () {
while (dq.back() != 1) {
int x = dq.back();
dq.pop_back();
while (x > 4)
x -= 3, res.push_back(2), res.push_back(2), res.push_back(1);
if (x == 4)
x = 2, res.push_back(2), res.push_back(2);
else
x = 1, res.push_back(2);
dq.push_front(x);
}
};
LEFT(); RIGHT(); LEFT(); RIGHT();
return res;
}
int main() {
int _;
scanf("%d%d", &_, &t);
while (t --) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++)
scanf("%d", &a[i]);
for (int i = 1; i <= m; i ++)
scanf("%d", &b[i]);
auto vec = solve();
if (vec != vector<int>{-1}) {
puts("Yes");
for (int ele : vec) printf("%d ", ele);
puts("");
continue;
}
reverse(a + 1, a + n + 1);
reverse(b + 1, b + m + 1);
vec = solve();
if (vec != vector<int>{-1}) {
puts("Yes");
for (int ele : vec) printf("%d ", 3 - ele);
puts("");
continue;
}
puts("No");
}
return 0;
}::::