题解：P4734 [BalticOI 2015] Hacker

· · 题解

题意

有一个长度为 n 的 v 序列。其中每个 v_i 和 v_{i+1} 之间有一个通道。特别的 v_1 和 v_n 之间有一个通道。现在有两个人 Alice 和 Bob 要在这个序列上移动且两个人都不能经过被其中任意一人经过的位置（起点也算）。由 Alice 先选择起点位置，然后 Bob 选择一个与 Alice 不同的位置作为起点。接下来两人按 Alice 先手，Bob 后手的顺序移动，每次两人可以选择移动到任意一个与自己经过的位置有通道相连的位置上面。Alice 希望自己经过的 v 之和最大，而 Bob 希望这个值最小。试问 Alice 能取到的最大值为多少。

思路

不难发现 Alice 和 Bob 最终都会取到两端连续的区间且正好将整个 v 序列覆盖。最终 Alice 取到的区间长度为 \lceil \frac{n}{2}\rceil，Bob 取到的区间长度为 \lfloor \frac{n}{2}\rfloor。两人的每次操作等价于将原本的区间向左或向右扩张一个位置。

首先肯定要破环为链，直接复制两倍。

然后考虑他们的最优策略。Alice 选择起点时我们显然没有什么好的策略，我们考虑 Bob 选什么起点能使 Alice 取到最小值。我们假设 Alice 的起点为 i，我们找到一个包含 v_i 的 v 值总和最小且长度为 \lceil \frac{n}{2}\rceil 的区间。其左端点为 l，右端点为 r。我们发现，Bob 一定能找到一个起点使得 Alice 只能取到 l\sim r 这个最小区间。为什么呢，我们考虑让 Bob 选择一个起点使得 Alice 的起点与 l 的距离等于 Bob 的起点与 l - 1 的距离且 Bob 的起点不在 l 到 r 的区间内。由于 Alice 的区间长度大于等于 Bob 的区间长度，所以 Bob 的起点距离 r + 1 一定不会比 Alice 的起点距离 r 更远。于是 Bob 只需要在 Alice 向 l 扩展一步时向 l - 1 扩展一步，Alice 向 r 扩展一步时向 r + 1 扩展一步就一定能使得 Alice 最终选择的区间为 l\sim r。不难证明这是 Bob 的最优策略。

因此我们只需要枚举每个 i 找到包含这个点的最小区间，最后给这些区间的值取个 \max 即可。

代码

这里选择的是单调队列搭配前缀和实现。其他很多数据结构也可以维护，但不建议使用线段树。

#include<bits/stdc++.h>//代码很丑，轻喷
#define int long long//_______,________.
#define N 3 * 500000 + 39
using namespace std;
int n, v[N], qzh[N], w[N], ans;
deque<int>q;
signed main()
{
    ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> v[i];
        v[n + i] = v[i];
        v[2 * n + i] = v[i];//为什么要复制三倍，因为作者写太丑了qwq
    }
    for(int i = 1; i <= 3 * n + 1; i ++)//前缀和
    {
        qzh[i] = qzh[i - 1] + v[i]; 
    }
    for(int i = 1; i + (n + 1) / 2 - 1 <= 3 * n + 1; i ++)//处理出以每个节点为左端点长度为ceil(n/2)的区间的和
    {
        w[i] = qzh[i + (n + 1) / 2 - 1] - qzh[i - 1];
    }
    for(int i = 1 - (n + 1) / 2 + 1 + n; i != n + 1; i ++) //单调队列，不会的可以去看滑动窗口（当然换成ST表等好理解的也可以）
    {
        while(!q.empty() && w[i] <= w[q.back()]) 
        {
            q.pop_back();
        }
        q.push_back(i);
    }
    for(int i = n + 1; i <= 2 * n; i ++)
    {
        while(!q.empty() && w[i] <= w[q.back()])
        {
            q.pop_back(); 
        }
        if(!q.empty() && q.front() + (n + 1) / 2 - 1 < i)
        {
            q.pop_front();
        }
        q.push_back(i);
        ans = max(ans, w[q.front()]);//虽然单调队列里是递减的，但是这里要取max
    }
    cout << ans;
    return 0;
}

AC 记录。