题解

思路

把序列从左到右的第 $2,4,6,\ldots$ 个元素翻转，记变换后的当前序列为 $y$，并对目标序列 $A$ 做同样的变换得到 $B$。

做法

原操作 A 在 $y$ 上恰好变成在开头加入 $0$；原操作 B 则在末尾加入一个只由操作前长度奇偶性决定的数，原长度为偶数时加入 $0$，为奇数时加入 $1$。所以 $B_1$ 必须为 $0$；若 $B$ 全为 $0$，显然可以构造。否则设 $B_z$ 是第一个 $1$，那么从 $B_z$ 开始的后缀必须是长度为 $N$ 的交替序列 $(0,1,0,1,\ldots)$ 的子序列：这些被选中的位置对应操作 B，其余位置对应在开头补 $0$ 的操作 A。反过来，只要这个子序列关系成立，按此对应选择两类操作就一定能构造出 $B$，进而构造出原序列 $A$。

用一个指针在交替序列中从左到右贪心匹配该后缀，每个元素都取当前能匹配它的最早位置；这个选择给后续元素留下的空间最多，因此贪心匹配成功当且仅当存在所需子序列。

复杂度

两个指针都只向右移动，总时间复杂度为 $O(N)$，空间复杂度为 $O(N)$。