题目理解

这是 BalticOI 2015 Hacker 问题的解决方案。题目是一个环形结构上的对抗游戏，Byteasar 要最大化自己的得分，而系统操作者采用最优策略。

代码思路解析

1. 问题转化

通过分析游戏规则，可以发现：

• 一旦 Byteasar 黑掉某台电脑，操作者会立即保护相邻的电脑
• 游戏实际上变成了在环上选择不相邻的电脑集合
• Byteasar 能黑掉的电脑形成一个独立集

2. 关键观察

对于环上的问题，可以转化为链上处理：

for (int i = 1; i <= n; i++) {
    v[i + n] = v[i + 2 * n] = v[i];
}

将环展开成3倍长度的链，便于处理环形边界。

3. 滑动窗口最大值

代码的核心是使用单调队列求滑动窗口最大值：

for (int i = 1; i <= 2 * n; i++)
    a[i] = s[i + len - 1] - s[i - 1];  // 计算窗口和

// 单调队列维护最大值
while (a[b[t - 1]] < a[j] && h < t)
    t--;
b[t] = j;
t++, j++;

4. 算法逻辑

1. 预处理前缀和：s[i] = s[i-1] + v[i]
2. 计算窗口和：a[i] 表示从位置 i 开始长度为 len 的区间和
3. 单调队列：维护当前窗口内的最大值
4. 计算答案：res = max(res, s[n] - a[b[h]])

其中 len = n/2 是因为在环上最多能选择 n/2 台不相邻的电脑。

关键技巧

1. 环形展开

将环展开成3倍链，避免复杂的环形边界处理

2. 窗口长度选择

int len = n / 2;

因为环上最大独立集的大小为 ⌊n/2⌋

3. 单调队列优化

用 O(n) 时间求出所有固定长度窗口的最大值

4. 答案计算

res = max(res, s[n] - a[b[h]]);

总价值减去操作者能保护的最大价值

复杂度分析

• 前缀和预处理：O(n)
• 单调队列处理：O(n)
• 总复杂度：O(n)

总结

这个解法巧妙地将对抗游戏转化为环形最大独立集问题，然后通过：

1. 环形展开：将环转化为链
2. 滑动窗口：利用固定窗口大小特性
3. 单调队列：高效求解窗口最大值
4. 补集思想：用总价值减去对手最优策略的价值

体现了竞赛中问题转化和数据结构优化的高级技巧。