1. 题目数据 (Problem Metadata)

2. 题意简述 (Problem Summary)

称一个由 $m$ 个整数组成的数组 $b$ 为「山」（hill），当且仅当存在下标 $k$（$1 \le k \le m$），使得前 $k$ 个元素严格递增（对所有 $1 \le i < k$，$b_i < b_{i+1}$），且从第 $k$ 个元素到最后严格递减（对所有 $k \le i < m$，$b_i > b_{i+1}$）。峰可以取到端点，即纯递增或纯递减的数组也是 hill。

给定一个由 $n$ 个互不相同整数组成的数组 $a$，每次操作任选下标 $i$（$1 \le i \le n-2$），交换 $a_i$ 与 $a_{i+2}$。问能否经过任意多次操作把 $a$ 变成 hill。

输入第一行为 $t$（$1 \le t \le 10^4$）；每组数据先给 $n$（$1 \le n \le 2 \times 10^5$），再给 $n$ 个互不相同的整数 $a_1, \dots, a_n$（$1 \le a_i \le n$，即 $a$ 是一个 $1$ 到 $n$ 的排列），保证 $\sum n \le 2 \times 10^5$。输出 YES 或 NO，大小写任意。

3. 朴素解法 (Brute-Force)

先把操作本身看透：$a_i \leftrightarrow a_{i+2}$ 永远在同奇偶性的两个位置之间交换，于是每个值只能待在与它初始位置同奇偶的格子里；反过来，同奇偶的位置构成两条链，链上相邻交换可以生成任意重排，所以「同奇偶格内任意重排」全部可达。解空间就此确定：奇位值集与偶位值集各自固定，答案是「两个值集各自重排后能否拼出 hill」。最朴素的枚举是对两个值集各做全排列（$\frac{n}{2}!\times\frac{n}{2}!$ 种），逐个检查是否单峰。我们在此解空间上寻找正式做法。

4. 核心解法 (Main Solution)

特殊性质

不要从操作出发想「怎么换」，只要理解了同奇偶性的两个集合内部可以任意交换即可，而从目标形状出发想「hill 长什么样」。hill 有一个关键结构性质：

值 $\ge v$ 的所有位置必然构成一段连续区间，$v \in \{1,2,\dots, n\}$。

通俗地说，从峰 $n$ 开始，值 $n, n-1, n-2, \dots$ 的位置是一个从峰不断向左右扩格的连续段。反证：若 top-$v$ 的位置不连续，中间夹了个小于 $v$ 的值，这个夹缝位置两侧都比它高，而 hill 的内部显然不能存在这种「谷」。反过来，只要每个 top-$v$ 位置集都连续，逐层往外还原就必然得到 hill。

这个结构让问题具备 DP 的两个基本性质。最优子结构：若 top-$m$ 的值恰好占满某区间 $[l, r]$，去掉其中最小的值 $v = n-m+1$——它在山形的升段起点或降段终点——剩余的 top-$(m-1)$ 个值仍占满 $[l+1, r]$ 或 $[l, r-1]$，面对的是与原问题同构的更短子问题，长度 $m$ 的可行性可以由长度 $m-1$ 的可行性在常数步内拼出。无后效性：区间 $[l, r]$ 的真假只依赖长度 $m-1$ 层的 $dp$ 值与值 $v$ 的 tag，与区间之外的位置如何安排、后续的值贴到哪里无关，逐层推进时已算定的层不会被改写。因此区间 DP 是合法的求解框架，剩下的问题只是状态规模。

关键突破

区间 DP 的状态 $dp[l][r]$ 有 $O(n^2)$ 个，单组 $n = 2\times10^5$ 时约 $4\times10^{10}$ 次转移，过不了。突破点在于盯着转移条件看：条件里出现的全部是奇偶性——值的初始位置奇偶、区间端点的位置奇偶。把整个区间 $[l, r]$ 平移 $2$ 格变成 $[l+2, r+2]$，长度不变、左端奇偶不变、转移条件逐字不变。更简单地说，反正同奇偶性的两个集合内部可以任意换，你在某个区间合法，把他们统一移动到任意一个长度相同、左端点奇偶性相同的位置肯定也合法。也就是说 $dp[l][r]$ 根本不关心 $l, r$ 具体是几，只关心长度 $m = r-l+1$ 和左端奇偶 $p = l \bmod 2$。$n^2$ 个状态由此坍缩成 $n$ 层 $\times$ 2 bit。

推导过程

先把经典区间 DP 写出来。设 $dp[l][r]$ 表示 top-$(r-l+1)$ 大的值能否恰好占满区间 $[l, r]$，值从大到小往区间里贴。记 $tag(v) = pos(v) \bmod 2$ 为值 $v$ 初始位置的奇偶性——重排只能在同奇偶格间进行，值 $v$ 想站到位置 $p$，就必须 $tag(v) = p \bmod 2$。设第 $m$ 层要贴的值为 $v = n-m+1$，转移就是把 $v$ 贴到左端或右端，有

$$ dp[l][r] = \big(dp[l+1][r] \wedge tag(v) = (l \bmod 2)\big) \vee \big(dp[l][r-1] \wedge tag(v) = (r \bmod 2)\big). $$

由平移不变性，用归纳法沿转移传播，得 $dp[l][r] \equiv f[m][p]$，其中 $m = r-l+1$，$p = l \bmod 2$。把转移逆写（从「大区间由小区间推出」改成「小区间向外扩一格生成大区间」），得到逐层演化方程

$$ f[m][p] = \big(f[m-1][p\oplus 1] \wedge tag(v) = p\big) \vee \big(f[m-1][p] \wedge tag(v) = (p+m-1) \bmod 2\big). $$

两项的几何含义分别是：向左扩时旧区间左端右移一格，奇偶翻转为 $p\oplus 1$，新值贴在新区间左端，要求 $tag(v) = p$；向右扩时旧区间左端不动，新值贴在新区间右端 $l+m-1$，其位置奇偶为 $(p+m-1)\bmod 2$，要求 $tag(v)$ 与之相等。

初值为 $f[1][tag(n)] = \text{true}$：长度 $1$ 的区间左端奇偶就是那个格子的奇偶，峰的 tag 匹配即可。答案查 $f[n][1]$——这里有个边界细节，$m = n$ 时区间 $[l, l+n-1]$ 要塞进 $[1, n]$，$l = 1$ 是奇数，只有 $p = 1$ 这个类真实存在，取 $f[n][1]$ 为答案即可。

5. 正确性证明 (Proof of Correctness)

下面总结证明要点，共三点。

  • 结构刻画：$a$ 经同奇偶重排可变成 hill，当且仅当存在一种重排使得每个 top-$v$（值 $\ge v$）的位置集合连续。必要性即峰两侧的延伸段；充分性在于 top-$v$ 集合大小为 $n-v+1$，相邻两层差恰一，连续加嵌套意味着每层恰向外扩一格，从峰逐层还原时左右两侧各自随距离严格递减，严格性自动保证。
  • 转移正确性：$f[m][p]$ 的两个转移来源穷尽了「长度 $m$ 的连续段」由「长度 $m-1$ 的连续段」扩一格的全部方式（左扩或右扩），且 tag 匹配恰好是「值 $v$ 能落在目标格」的充要条件（同奇偶格内的重排群可迁）。故逐层演化计算的是原区间 DP 的真值。
  • 坍缩正确性：对 $m$ 归纳。$m=1$ 时 $dp[l][l]$ 只依赖 $l \bmod 2$；设 $m-1$ 层已坍缩，$m$ 层的转移条件中所有量（$tag(v)$、$p$、$(p+m-1)\bmod 2$）在平移 $2$ 格下不变，故 $dp[l+2][r+2] = dp[l][r]$，$m$ 层也只依赖 $(m, p)$。边界上，$m \le n-2$ 时每个 $(m,p)$ 类都有真实区间；$m = n-1$ 与 $m = n$ 时部分代表元越界产生垃圾态，但答案查询的 $(n,1)$ 类代表元 $l=1$ 是真实区间，垃圾态不影响答案位。

综上所述，$f[n][1] = \text{true}$ 当且仅当原数组可变成 hill。

6. 复杂度分析 (Complexity)

  • 时间复杂度：$O(\sum n)$。状态复杂度 $O(n)$（$n$ 层 $\times$ 每层 2 状态），转移复杂度常数（每状态 2 个转移来源），全部是常数操作。对比 $O(n^2)$ 区间 DP，$n = 2\times10^5$ 时从 $4\times10^{10}$ 降到 $10^6$ 量级，2 秒时限充裕。
  • 空间复杂度：$O(n)$，即 $f$ 数组与 $tag$ 数组。可以用两个 bool 变量滚动到 $O(1)$，AI 给出了一个滚动数组优化的解，但是我觉得没有必要。我用 bitset 优化了 f 数组

7. 实现细节与避坑指南 (Implementation Details)

  • 两种「奇偶」别搞混：$tag(v) = pos(v) \bmod 2$ 是初始位置的奇偶，不是值的奇偶。$a$ 是排列，值的奇偶和位置的奇偶毫无关系，转移里所有奇偶比较都是「位置奇偶 vs 位置奇偶」。
  • 经典 DP 初值的坑：把 $dp[l][l]$ 的初值写成 $pos(n) = l$（「峰必须在它原来的位置」）是错的——峰可以落在区间内任何同奇偶的格子上，正确写法是 $(pos(n) \bmod 2) = (l \bmod 2)$。
  • 答案位选 $f[n][1]$：$m=n$ 时左端被逼到 $1$（奇数），$f[n][0]$ 是不可能出现的情况。虽然它的形式真值在答案意义下与 $f[n][1]$ 一致（精确刻画见 §9 官方版本的闭式），写 $f[n][0] \vee f[n][1]$ 也不会错，但不如直写语义正确的 $f[n][1]$。
  • $n=1$ 无需特判：单元素天然是 hill；此时 $c[1]=1$，初值 $f[1][1]=\text{true}$，答案 $f[1][1]$ 直接覆盖，代码自然通过。
  • 多测清空：我的写法用了 bitset 的 reset 来清多测，貌似也可以直接把 bitset 开到 solve 函数里。总之，百年 OI 一场空，不清多测见祖宗。

8. 参考代码 (Reference Code)

下面给出我自己的 $O(n)$ 写法，即区间 DP 经对称性约简后的版本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
// #define int long long

const int N = 2e5 + 5;

int n, c[N];

bitset<N> f[2];

// 设区间长度为 i, 即 n, n - 1, ... , n - i + 1
// f[x][i] 表示，区域左端点 l & 1 == x 时
// 是否存在一段连续的区间，可以合法放下这 i 个数

void solve()
{
    f[0].reset(), f[1].reset();

    cin >> n;
    for (int i = 1, a; i <= n; i++)
    {
        cin >> a;
        c[a] = i;
    }

    f[c[n] & 1][1] = 1;

    for (int i = 2; i <= n; i++)
        for (bool x : {0, 1})
        {
            f[x][i] =
                (f[!x][i - 1] && (x == (c[n - i + 1] & 1))) | (f[x][i - 1] && (((x + i - 1) & 1) == (c[n - i + 1] & 1)));
        }
    cout << (f[1][n] ? "YES" : "NO") << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Don't stop. Don't hide. Follow the light, and you'll find tomorrow.

    int T;
    cin >> T;
    while (T--)
        solve();
	return 0;
}

9. 补充说明 (Additional Notes)

  • 经典模型：本题是「受限交换可行性判定」与「单峰结构刻画」的结合，是奇偶不变量既当判定器又当状态压缩器的一次完整示范。判定器指 tag 匹配决定值 $v$ 能否站上某个格子，状态压缩器指平移 $2$ 格不变性把 $n^2$ 的区间状态压成 $n$ 层 2 bit——同一件事物在不同抽象层出现两次，通常意味着它才是问题的骨架。这个显而易见的性质，反而是问题的关键点所在。
  • 可迁移的优化框架：把区间 DP 读成一个过程（长度 $=$ 时间、端点扩张 $=$ 决策），找过程的对称群，按轨道求商，验证转移条件只含不变量，最后检查边界层。这套流程对所有「转移条件只含不变量」的区间 DP 都适用。

其他版本

官方 $O(n)$ 扫描判定，更短更直接，适合当场上正解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        vector<int> c(n + 1);
        for (int i = 1; i <= n; i++) {
            int x;
            scanf("%d", &x);
            c[x] = i;
        }
        int cnt[2] = {0, 0};
        bool ok = true;
        for (int v = n; v >= 1; v--) {        // 从峰往下逐层检查连续段奇偶配平
            cnt[c[v] & 1]++;
            if (abs(cnt[0] - cnt[1]) > 1) { ok = false; break; }
        }
        puts(ok ? "YES" : "NO");
    }
    return 0;
}

两种做法复杂度相同。扫描版胜在短，但我个人觉得，不经过 DP 推导，直接由官方题解那个想法提出这个做法，有点过于人类智慧了。DP 版胜在推导过程通用、不依赖灵光一现——可以巩固动态规划相关的知识点。

下面用数学方法证明「DP 为什么恰好等价于官方扫描」。注意到这个证明是 DeepSeek V4.1 Flash 给出的，我不太想看了，若有错误欢迎与我交流。沿用 $tag(v) = c[v] \bmod 2$ 的记号，考虑最大的 $m$ 个值 $T_m = \{n, n-1, \dots, n-m+1\}$。官方扫描到第 $m$ 层时统计的是

$$ C_m[b] = \#\{v \in T_m : tag(v) = b\}, \qquad d_m = C_m[0] - C_m[1], $$

判定条件为 $\forall m,\ |d_m| \le 1$——每加入一个值 $d_m$ 变化 $\pm1$，越界即 NO。定义前缀合法性 $A_m = \bigwedge_{j=1}^{m}\bigl(|d_j| \le 1\bigr)$，则坍缩 DP 的真值有如下闭式：

$$ f[m][p] = \begin{cases} A_m, & m \text{ 偶}, \\ A_m \wedge \big[p = \tfrac{1-d_m}{2}\big], & m \text{ 奇}. \end{cases} $$

注意 $A_m$ 成立时奇偶自动定号：$m$ 偶则 $C_m[0]+C_m[1]=m$ 为偶，$d_m$ 为偶，被 $|d_m|\le1$ 强制成 $d_m=0$；$m$ 奇则 $d_m=\pm1$，此时左端奇偶必须取 $T_m$ 中初始位置的多数类——$d_m=1$ 取 $p=0$，$d_m=-1$ 取 $p=1$，恰是 $(1-d_m)/2$。

对 $m$ 归纳证明。$m=1$ 时 $T_1=\{n\}$，$d_1=\pm1$ 由 $tag(n)$ 定号，DP 初值 $f[1][tag(n)]=1$ 恰好取到多数类，与公式一致。归纳步设 $m-1$ 层已证，加入值 $v=n-m+1$，记 $q=tag(v)$，则 $d_m = d_{m-1} + (1-2q)$——$q=0$ 时加一，$q=1$ 时减一。分两种情况。

情况一 $|d_m|>1$：首次越界必然是从 $d_{m-1}=\pm1$ 再加一个同号项变成 $\pm2$，此时 $m$ 必为偶数、$m-1$ 为奇数。由归纳假设 $f[m-1]$ 只有多数类 $p^*$ 一个真状态，而同号项意味着 $q=p^*$。代入转移检查两个来源：向左扩要求 $f[m-1][p\oplus1]$ 为真且 $tag(v)=p$，迫使 $p=p^*\oplus1$，与 $q=p^*$ 矛盾；向右扩要求 $f[m-1][p]$ 为真且 $tag(v)=(p+m-1)\bmod2$，迫使 $p=p^*$，而 $m$ 偶时 $(p^*+m-1)\bmod2=p^*\oplus1$，仍与 $q=p^*$ 矛盾。两个来源全部断掉，$f[m][0]=f[m][1]=0$，与 $A_m=0$ 一致。

情况二 $|d_m|\le1$：$A_m=A_{m-1}=1$。若 $m$ 为偶数则 $d_m=0$，$m-1$ 奇层只有多数类 $p^*$ 为真，且 $q=p^*\oplus1$（新值翻转了多数）。代入转移：$p=p^*\oplus1$ 经向左扩成立（$f[m-1][p^*]$ 为真且 $tag(v)=p$），$p=p^*$ 经向右扩成立（$f[m-1][p^*]$ 为真且 $(p^*+m-1)\bmod2=p^*\oplus1=q$），两层同真，即 $f[m][0]=f[m][1]=1$。若 $m$ 为奇数则 $d_m=\pm1$，$m-1$ 偶层 $f[m-1][0]=f[m-1][1]=1$ 全真，此时两个来源殊途同归：向左扩要求 $p=q$（前一状态恒真、$tag(v)=p$），向右扩也要求 $p=q$（前一状态恒真，且 $m-1$ 为偶使 $(p+m-1)\bmod2=p$）。于是 $p=q$ 层两个来源同时成立、$p=q\oplus1$ 层同时断掉，只有 $p=q$ 一层为真。而 $d_m$ 的符号恰由 $q$ 决定（$q=0\Rightarrow d_m=1$，$q=1\Rightarrow d_m=-1$），故 $p=(1-d_m)/2$，即多数类。引理得证。

最后收敛到答案位。$T_n$ 是全部 $n$ 个值，初始位置为奇的有 $\lceil n/2\rceil$ 个、为偶的有 $\lfloor n/2\rfloor$ 个，故

$$ d_n = \begin{cases} 0, & n \text{ 偶}, \\ -1, & n \text{ 奇}. \end{cases} $$

代入闭式：$n$ 偶时两层同值 $f[n][1]=A_n$；$n$ 奇时多数类恰为 $1$，仍有 $f[n][1]=A_n$。综上所述，

$$ f[n][1] = \bigwedge_{m=1}^{n}\bigl(|d_m|\le1\bigr), $$

即坍缩 DP 输出 YES 当且仅当官方扫描全程未越界，两版判定完全等价。顺带一提，这条闭式把 $f[n][0]$ 的问题也一并说清了：$f[n][0]$ 的形式真值在 $n$ 偶时与 $f[n][1]$ 同为 $A_n$、在 $n$ 奇时恒为假，无论哪种都与答案位无关。

一句话总结：坍缩 DP 逐层记录的是「前 $m$ 大值的奇偶计数是否始终没有失衡，以及当前连续段左端该取哪个奇偶」；官方扫描把这两件事压缩进一个计数器 $d_m$——只要每步 $|d_m|\le1$，连续段就能一层层嵌套地扩出来；一旦某步 $|d_m|>1$，长度 $m$ 的连续段里怎么都塞不下 $T_m$。

类似题推荐：

  • CF1545A - AquaMoon and Strange Sort —— 方向约束下的相邻交换排序，核心同样是「每个值的移动距离为偶数 $\Leftrightarrow$ 奇数位/偶数位出现次数守恒」的不变量分析。
  • CF1638B - Odd Swap Sort —— 只许交换奇偶性不同的相邻元素，判能否排序；不变量是「同奇偶元素的相对顺序不变」，与本题主视角完全同构。
  • CF1251C - Minimize The Integer —— 奇偶链上贪心归并，同款「奇偶性相同的数字相对顺序不变」观察。
  • CF1620F - Bipartite Array —— 目标结构是本题 hill 的镜像（单谷），拆两段加 DP 或贪心构造，可对照体会「单峰/单谷结构刻画」的通用套路。
动态规划Codeforces区间DP构造分治
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

本站由 zaochen 使用 Stellar 2.0.0 主题创建。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
全站访问量 - 次 · 访客数 - 人 · 本页面浏览 - 次

站内搜索

没有找到内容！