CF2140C

DDF_ · 2025-09-16 13:12:19 · 题解

题解

首先，如果 Alice 操作后，Bob 操作了，那么 Alice 可以把他的操作反走一遍，这时 f(a) 的值便会比第一次 Alice 操作后还大，所以对 Bob 来说，他最好在第一次就结束游戏。

所以决定权在 Alice 手中。

Alice 第一次操作肯定要找对答案贡献最大的 l,r 操作。这时候就有两种方案。

设没做任何操作时 f(a) 为 S。

将奇数位和偶数位互换，此时对于要换的两个位 x 和 y（x 为奇数位，y 为偶数位），此时 f(a) 为 S+|x-y|+2 \times a_{y}-2 \times a_{x}，所以我们要求上式的最大值。

可以枚举每一个奇数位。此时若 y<x，就要求 x-y+2 \times a_{y} - 2 \times a_{x} 最大值，把有关 x 的剥离出来，可以用前缀和数组维护 2 \times a_{i} -i 的最大值（i 为偶数），然后就可以 O(1) 求；若 y>x，同理，可以维护后缀 2 \times a_{i} +i 的最大值。

将奇偶性相同的位互换，此时对答案的贡献为两个位置相减，贪心去想，可得答案为最后一个奇数位减 1。

时间复杂度 O(n)。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
int _;
ll n,a[N],s1[N],s2[N],ans,sum;
void solve() {
    scanf("%lld",&n),sum=0,s2[n+1]=0,ans=(n&1)?(n-1):(n-2);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),sum+=(2*(i%2)-1)*a[i];
    for(int i=1;i<=n;i++) {
        if(i&1) s1[i]=s1[i-1];
        else s1[i]=max(s1[i-1],2*a[i]-i);
    }
    for(int i=n;i;i--) {
        if(i&1) s2[i]=s2[i+1];
        else s2[i]=max(s2[i+1],2*a[i]+i);
    }
    for(int i=1;i<=n;i+=2) ans=max(ans,max(s1[i]+i,s2[i]-i)-2*a[i]);
    printf("%lld\n",ans+sum);
    return;
}
int main() {
    scanf("%d",&_);
    while(_--) solve();
    return 0;
}