题解：CF2267D Backrooms Hill

super_wyh · 2026-09-28 11:35:17 · 题解

关键性质：只有位置的奇偶性相同才能交换。

并且注意到 1\le a_i \le n，且 a_i 互不相同。

所以 a 是 1\dots n 的一个排列，此时最大值只有一个，为 n。

这样我们就好做了，原题目转化为：重新排列奇数和偶数位置上的数字，使得能找到一个 p，让 a_1<a_2<\cdots<a_{p-1}，a_p=n 且 a_{p+1}>\cdots>a_n。

考虑动态规划。

先把 a 升序排列，并记录原下标（奇偶性）。

我们令 dp_{i,j} 左右两侧分别填原下标奇偶性为 i,j，能否符合原题目的条件（即能分成左侧单调递增，右侧单调递减），符合为 1，不符合为 0。

我们令 0 为偶数，1 为奇数，即奇偶性用 n\&1 代替。

初始化：dp_{1,n\&1}=1，即一个填左边，一个填右边。

考虑转移：这个转移很明显了，只有奇偶性相同的情况下，才能转移（因为数组已经排好序了嘛，所以不用看数组了）。令 c 为原下标的奇偶性，则有以下转移（令 dp2 为上一次的 dp 结果，然后把 dp 清空）：

• 如果 dp2_{i,j}=1，并且 i=c，则 dp_{i\oplus 1,j}=1。
• 如果 dp2_{i,j}=1，并且 j=c，则 dp_{i,j\oplus 1}=1。

然后，就是求答案了。

我们发现，在 a 数组中，原来值等于 n 的下标和重拍后值等于 n 的下标奇偶性相同，所以答案的下标就是（令 k 为原来下标的奇偶性）：dp_{k,0} 和 dp_{k,1}，由于这两个值都可以，所以只要其中一个值为 1，就可以输出 YES，否则输出 NO。

赛时代码