「JOI 2013 Final」彩灯 题解

问题分析

我们有一个长度为 $N$ 的 $0/1$ 序列，表示彩灯的亮灭状态。可以最多翻转一个连续区间（$0$ 变 $1$，$1$ 变 $0$），目标是最大化最长的交替序列的长度。

交替序列定义为相邻元素不同的连续子序列。

关键观察

1. 交替序列的性质

对于一个序列，如果它是交替的，那么相邻元素必须不同。用差分的方式思考：

• 定义 $b[i] = a[i] \oplus a[i-1]$（异或运算）
• 在交替序列中，$b[i]$ 应该全为 $1$（除了边界）

2. 翻转操作的影响

翻转一个区间 $[l, r]$ 会：

• 改变 $b[l]$ 和 $b[r+1]$ 的值（如果存在）
• 区间内部的 $b$ 值不变

这是因为翻转操作只影响区间的两个边界处的相邻关系。

算法思路

1. 预处理差分数组

for (int i = 1; i <= n; i++)
    b[i] = (a[i] ^ a[i - 1]);

这里 $b[i]$ 表示 $a[i]$ 和 $a[i-1]$ 是否相同：

• $b[i] = 1$ 表示 $a[i] \neq a[i-1]$
• $b[i] = 0$ 表示 $a[i] = a[i-1]$

2. 找到所有"断裂点"

vector<int> w;
for (int i = 2; i <= n; i++)
    if (!b[i])
        w.push_back(i);

$w$ 存储所有不满足交替条件的位置，即 $a[i] = a[i-1]$ 的位置。

3. 特殊情况处理

if (sz <= 1) {
    printf("%d\n", n);
    return 0;
}

如果断裂点少于 $2$ 个，说明原序列几乎就是交替的，翻转一个区间后可以使得整个序列变成交替序列，答案为 $N$。

4. 计算每个位置的左右交替长度

for (int l = 2, r; l <= n; l = r + 1) {
    r = l;
    if (!b[r]) continue;
    
    while (r <= n && b[l] == b[r])
        r++;
    r--;
    R[l - 1] = r - l + 1;
    L[r + 1] = r - l + 1;
}

这里计算：

• $L[i]$：以位置 $i$ 为右端点的最长交替序列长度
• $R[i]$：以位置 $i$ 为左端点的最长交替序列长度

5. 寻找最优翻转位置

for (int i = 1; i < sz; i++)
    ans = max(ans, L[w[i - 1]] + R[w[i - 1]] + R[w[i]] + 3);

考虑翻转包含两个相邻断裂点 $w_{i-1}$ 和 $w_i$ 的区间，这样可以将它们连接起来。

算法正确性证明

1. 翻转操作的分析

当我们翻转区间 $[l, r]$ 时：

• 边界 $l-1$ 和 $l$ 的关系改变：$b[l]$ 翻转
• 边界 $r$ 和 $r+1$ 的关系改变：$b[r+1]$ 翻转
• 区间内部的相邻关系不变

因此，翻转操作实际上只改变了两个位置的 $b$ 值。

2. 连接策略

假设我们有两个断裂点 $p$ 和 $q$（$p < q$），翻转区间 $[p, q]$：

• $b[p]$ 翻转：可能修复 $p$ 处的断裂
• $b[q+1]$ 翻转：可能修复 $q+1$ 处的断裂
• 这样可以将 $p$ 左侧的交替段和 $q$ 右侧的交替段连接起来

3. 长度计算

对于断裂点 $w_{i-1}$ 和 $w_i$：

• $L[w_{i-1}]$：$w_{i-1}$ 左侧的交替段长度
• $R[w_{i-1}]$：$w_{i-1}$ 右侧的交替段长度（实际上这里代码可能有误，应该是 $R[w_i]$）
• 连接后的总长度 = 左段 + 中间修复的部分 + 右段

复杂度分析

• 预处理差分数组：$O(N)$
• 寻找断裂点：$O(N)$
• 计算左右交替长度：$O(N)$
• 寻找最优解：$O(K)$，其中 $K$ 是断裂点数量

总复杂度：$O(N)$

示例验证

样例 1

输入：

10
1 1 0 0 1 0 1 1 1 0

处理过程：

1. 原序列：1 1 0 0 1 0 1 1 1 0
2. 差分 $b$：? 0 1 0 1 1 1 0 0 1（第一个位置无意义）
3. 断裂点：位置 $2, 4, 8, 9$ 处 $b[i] = 0$
4. 计算左右交替段长度
5. 找到最优连接方案，得到长度 $7$

样例 3

输入：

5
1 1 0 1 1

处理过程：

1. 原序列：1 1 0 1 1
2. 差分 $b$：? 0 1 1 0
3. 断裂点：位置 $2, 5$
4. 翻转区间 $[2, 4]$ 得到：1 0 1 0 1
5. 整个序列变成交替序列，长度 $5$

总结

本题的关键在于：

1. 差分转换：将交替序列问题转化为寻找连续 $1$ 的问题
2. 翻转分析：理解翻转操作只影响两个边界
3. 连接策略：通过翻转连接相邻的交替段

这种方法在 $O(N)$ 时间内解决了问题，适用于 $N \leq 10^5$ 的大规模数据。