2025-10-24 学习日记

今日学习记录

1. Problem-2140C-codeforces

关键词：贪心 问题分析： 题目给定f(a) = cost +(a[1]-a[2]+a[3]-a[4]...a[n]),cost 为初始值 0 题目给出 n 长度为 n 的数组 a,轮流玩游戏,Alice 先手,bob 后手,每一轮可以这样选择

• 直接结束整场游戏
• 交换数组中的两个数,同时使 cost 增加这两个数在数组中的距离 Alice 要使 f(a)最大化,bob 要使 f(a)最小化 都是最佳的方法下棋

核心思路: 先要想到一个小优化,这个优化再自己模拟几次就差不多能看出来了,Alice 先手,而 bob 后手,Alice 一定会让 f(a)变大,而 bob 要使其变小,即要做出 Alice 的逆操作,但是 Alice 又可以撤销 bob 的操作(把 bob 换过的再换过来),这样就一直僵持不下,但是 cost 会一直增加,所以 bob 的操作是无效的,最优就是 bob 直接结束,所以这个题就是 Alice 做出一次操作使 f(a)最大 为什么不先确定鲍勃是选择还原爱丽丝的贡献大还是另一组数字贡献大? 在我这个角度看,是最优方案,在对方角度看就是反对自己的最优方案,既然对面是最优,那么我只有反转抵消对面的操作才是最优的 还有个提醒,这场博弈最多进行 10 的 100 次方,显然这个数字是不可能,一定有什么规律在中间能使整场博弈提前结束

实现(枚举右维护左)

看到 bob 的结束条件才真正开始这个题目, 后面只对 Alice 讨论就简单了

1. 如果选择交换符号相同的元素,则越远越好
2. 如果选择不同的符号元素,则要记录看哪两个元素交换使 f(a)最大,再仔细想想,是不就是枚举右维护左这个经典问题
   • 对于负数 v,要与之前的正数 a 交换,会使 f(a)增加i-j+2*v-2*a,为什么乘 2,因为负数已经加到 ans 中,要实现成 ans+v -> ans-v+2Xv 这样
   • 对于正数 v,要与之前的负数 a 交换,会使 f(a)增加i-j-2*a-2*v 所以我们发现 i 和之前的 a 是在一起的,即捆绑信息,所以可以记录每次遍历的 i 和 v,发现都是减,于是枚举右,维护左最小 **最终代码：

#include <bits/stdc++.h>

using namespace std;

#define ve vector

using ll = long long;

using ull = unsigned long long;

using sr = string;  

using db = double;

ll T,n,v;

int main() {

    ios_base::sync_with_stdio(false);

    cin.tie(nullptr);

    cin>>T;

    while(T--){

        cin>>n;

        ll ans =  0;

        ll l = INT_MAX,r = INT_MAX,mx = n-2+n%2;

        for(ll i = 0;i<n;i++){

            cin>>v;

            if(i%2>0){

                ans -= v;

                mx = max(mx,i+2*v-r);

                l = min(l,i-2*v);

            }else{

                ans += v;

                mx = max(mx,i-2*v-l);

                r = min(i+2*v,r);

            }

        }

        cout<<ans+mx<<endl;

    }

    return 0;

}

学到的点：

1. 思维