题解：P13093 [FJCPC 2025] 卡牌游戏

· · 题解

性质挖掘 + 前缀和 + 贪心 + STL set + STL 二分查找

首先要能手玩样例发现出一个性质：对于区间 [l,r]，若区间长度为偶数，区间 [l,r] 内的数的位置奇偶互换；若为奇数，区间 (l,r] 内的数的位置奇偶互换。

由于考虑区间长度为奇数时等价于修改一个区间 (l,r]。所以实际上我们只需考虑长度为偶数的区间。

在知道了上面那个性质之后，就可以考虑枚举长度为偶数的区间 [l,r] 作为修改的区间，当确定了 [l,r] 时，其实当前整个序列的答案就确定出来了，结合前缀和快速计算。因为 [l,r] 中的奇偶性反转了，以奇数下标元素之和为例，当操作 [l,r] 后奇数下标的元素之和为：

res\_odd=prefix\_odd_{l-1}+(prefix\_even_{r}-prefix\_even_{l-1})+prefix\_odd_{2n}-prefix\_odd_{r}

偶数下标元素之和同理，但其实可以直接通过 \displaystyle \sum _{i=1}^n a_i - res\_odd 得到，不需要再考虑其计算式。

但上面这个枚举 [l,r] 区间做法是 O(n^2) 的，显然会 TLE，考虑优化。

对于前面当操作 [l,r] 后奇数下标的元素之和，其实你可以对式子移项进行简单转化，把下标相同的放一起：

(prefix\_odd_{l-1}-prefix\_even_{l-1})-(prefix\_odd_{r}-prefix\_even_{r})+prefix\_odd_{2n}

定义 diff_i=prefix\_odd_i-prefix\_even_i。则当操作 [l,r] 后，奇数下标的元素之和为：

res\_odd=diff_{l-1}-diff_{r}+prefix\_odd_{2n}

根据贪心的考虑，要让最坏情况下得到的数字之和最大，即考虑让当前操作 [l,r] 区间后奇数下标的元素之和与偶数下标的元素之和最大，即最大化下式：

\min \Big(res\_odd,\displaystyle \sum _{i=1}^n a_i- res\_odd \Big)

那么显然两者尽可能接近，即考虑让 res\_odd 尽可能接近 \dfrac{\sum _{i=1}^n a_i}{2}。

即让 diff_{l-1}-diff_{r}+prefix\_odd_{2n} 尽可能接近 \dfrac{\sum _{i=1}^n a_i}{2}。

那么可以考虑每次枚举右端点 r，从前面的位置中找值尽可能接近 \dfrac{\sum _{i=1}^n a_i}{2}+diff_r-prefix\_odd_{2n} 的 diff_{l-1}，考虑经典处理方式二分查找即可。

具体地说：记 val=\dfrac{\sum _{i=1}^n a_i}{2}+diff_r-prefix\_odd_{2n}，则可以通过找 \ge val 的第一个值，其迭代器为 \operatorname{it}，那么 \operatorname{it} 和 \operatorname{it}-1 这两个迭代器可以作为备选答案。在保证迭代器合法性的基础上打擂台比较即可。

细节一：用 STL set 维护 diff 值。

细节二：由于 [l,r] 长度是偶数，那么 l,r 奇偶性相异，但是我们要找的下标为 l-1，而 l-1 和 r 奇偶性相同。所以我们在 set STL 上二分查找时需要从与 r 的奇偶性相同的 diff 值中查找，于是 STL set 需要分下标的奇偶来维护 diff 值。

细节三：在 STL set 上查找 \ge val 的值时，可能找不到，迭代器可能不存在，需要特判，避免计算错误。

代码如下：

#define rep(x,y,z) for(int x=y;x<=z;x++)
typedef long long LL;
const int N=2e5+5;
int n;
int a[N];
LL diff[N];
void solve(){
    cin>>n;
    rep(i,1,n*2) cin>>a[i];
    LL sum=0;
    LL odd_sum=0,even_sum=0;
    rep(i,1,n*2){
        sum+=a[i];
        if(i&1) odd_sum+=a[i];
        else even_sum+=a[i];
        diff[i]=odd_sum-even_sum;
    }
    set<LL> se[2];
    LL ans=0;
    rep(r,0,n*2){
        if(r){
            LL val=sum/2+diff[r]-odd_sum;
            auto it=se[r&1].lower_bound(val);
            if(it!=se[r&1].end()){
                LL res_odd=*it-diff[r]+odd_sum;
                ans=max(ans,min(res_odd,sum-res_odd));
            }
            if(it!=se[r&1].begin()){
                it--;
                if(it!=se[r&1].end()){
                    LL res_odd=*it-diff[r]+odd_sum;
                    ans=max(ans,min(res_odd,sum-res_odd));
                }
            }
        }
        se[r&1].insert(diff[r]);
    }
    cout<<ans;
}