题解 P8002 【Alice and Bob are playing a Normal Game】

VinstaG173 · 2022-01-04 08:51:05 · 题解

一个挺有意思的题。

注意到当目前的总和绝对值是 t，新加入的数在 [-x,x] 中的时候我们能够得到的值只能在 [-x-t,x-t] \cup [-x+t,x+t] 中且能取遍其中任意整数。这个值域是关于 0 对称的。

因此无论谁是最后操作者都想要最终绝对值最大，只要按照自己的要求取正负就可以了。故我们知道最后一个人肯定会选择 -x_k-t 或 x_k+t，而其对手希望让这个绝对值尽可能小。由于 x_k 给定，因此只要让 t 尽可能小。这样讨论下去我们就会发现最后一个人会一直选择将绝对值从 t 变成 t+x_i，其对手会一直选择将绝对值从 t 变成 \max\{t-x_i,0\}。因此我们只要照此模拟即可。时间复杂度 O(n)。

Code:

#include<cstdio>
#define rg register
#define ll long long
int n,k,x,t;ll r;
int main(){
    n=read(),t=k=read();for(rg int i=0;i<n;++i){
        x=read(),r+=((i&1)?-x:x);
    }if(r<0)r=-r;while(k--){
        x=read(),r=(k&1)?((r>x)?(r-x):0):(r+x);
    }return 0&printf("%lld\n",(t&1)?r:-r);
}