AGC026F Sol || 你谷终于把这题传了

· · 题解

一行 a_i，先后手轮流操作。每次要选择一个和上一次选择相邻的位置，同一个位置只能被选一次，如果是第一次操作或者没有这样的位置就可以任选。双方都希望自己选到的 a_i 之和尽量大，求双方同时使用最优策略的情况下两人的 a_i 和分别是多少。n\le 3\times 10^5。

神仙博弈。

双方交替取，自然地想到把序列黑白染色一下。那么博弈过程形如一轮一轮的操作：先手挑一个位置，后手挑一个方向，然后往死里走，双方分别取这一段相同颜色的数，然后在没有取过的那段开始下一轮。每一轮的先后手可能发生变换。

题目要求的东西换句话说就是，在后手拼命阻止先手拿到高分的情况下，先手答案最大是多少。想一下会发现 n 在奇数和偶数的情况出现了区别。

设黑格和为 B，白格和为 W。

先手明显可以做到 \max(B,W) 的下界（挑其中一端开始把这个颜色全部取完），问题就是黑白都取一些的情况会不会更优。

但先手落完第一步，下一步的方向是由后手决定的，只要先手选的位置不在两端，因为 n 是偶数，一定有一个方向使得后手会变成下一轮的先手，同时让下一轮的 n 也是偶数。所以后手两轮下来肯定能把先手开局没取的颜色全部取完，先手没法比 \max(B,W) 更多了。

先手可以做到 B 的下界。由上一种情况，我们知道先手第一个取非端点黑格是没有用的，后手可以直接在下一轮倒反天罡。所以先手要么取白格让后手挑两边其中一个子问题进去，要么取当前轮的端点（一定都是黑的）不演了直接结束。

所以先手最终答案一定由前缀内白格+区间内黑格+后缀内白格组成。设这个区间为 [l,r]。

考虑二分答案，称上述对应答案达到 mid 的区间 [l,r] 为好区间，可能为空。那么变成了一个更直接的问题：先手每次在序列中选一个白格，后手每次选择保留序列中这个位置左/右侧的部分，后手要防止序列缩成任何一个好区间。考虑什么条件下后手阻止不了先手。

当且仅当，原序列中可以找到若干个特殊的白格，使得相邻每一对特殊白格之间格子组成的区间，以及在所有特殊白格左侧/右侧的格子组成的区间（均可能为空），都为好区间。称这样的序列为好序列。

（这个条件我认为只能先感受到再证。）

好序列 = [好区间]W[好]W[好]...W[好]

这时先手的策略非常简单，就是每一轮在序列里随便挑一个这样的特殊白格，任后手随便选方向。如果已经没有特殊白格，那这个序列就对应了一个好区间，显然其一定两端都是黑的，直接把黑的选完结束就行。

相应的，如果原序列不是好序列，每一轮后手能选的两个方向里一定至少有一侧的序列也不是好序列，后手直接选择进去，递归到最后先手肯定没办法了。

考虑如何实现此判定。转化成先把全部白格算上，后续计算时把白格值取负，让区间 [l,r] 对应的答案变成单纯的区间和。区间和拆成 sum_r-sum_{l-1}\ge mid。从左到右扫这个序列，过程中维护，满足 [1,l-2] 为好序列的 sum_{l-1} 最小值。就可以判定了。

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std; bool MEM;
using ll=long long; using ld=long double;
using pii=pair<int,int>; using pll=pair<ll,ll>;
const int I=1e9;
const ll J=1e18,N=3e5+7;
ll n,a[N],sm,sum[N],dp[N];
bool chk(ll mid) {
    dp[0]=1; ll mnn=0;
    for (ll i=1;i<=n+1;i++) {
        if (dp[i-1]) mnn=min(mnn,sum[i-1]);
        dp[i]=sm+sum[i-1]-mnn>=mid;
    }
    return dp[n+1];
}
void mian() {
    scanf("%lld",&n);
    for (ll i=1;i<=n;i++) scanf("%lld",&a[i]);
    for (ll i=2;i<=n;i+=2) sm+=a[i],a[i]=-a[i];
    for (ll i=1;i<=n+1;i++) sum[i]=sum[i-1]+a[i];
    if (n%2==0) return cout<<max(sm,sum[n]+sm)<<" "<<min(sm,sum[n]+sm),void();
    ll l=0,r=3e8,mid,res=-1;
    while (l<=r) {
        mid=l+r>>1;
        if (chk(mid)) res=mid,l=mid+1;
        else r=mid-1;
    }
    cout<<res<<" "<<sum[n]+sm*2-res;
}
bool ORY; int main() {
    // while (1)
    // int t; for (scanf("%d",&t);t--;)
    mian();
    cerr<<"\n"<<abs(&MEM-&ORY)/1048576<<"MB "<<clock()<<"ms\n";
    return 0;
}