CF #672 (Div. 2)部分

总是错想一些思想，很亏。

C2.Pokémon Army (hard version)

ps：因为$c1$和$c2$的区别就在于有没有交换操作，所以不放了

题意：

你现在有$n$个 宝可梦，每个宝可梦有能量值$a_i$（互不相同），你现在要按顺序从中选出任意个$(k)$宝可梦，构成一个数组$b$，令$ans$等于$b_1-b_2+b_3-b_3+\dots $，要使$ans$最大，并输出$ans$；接下来有$q$，次操作，每次操作调换$l$和$r$的位置，并输出$ans$。

题解：

如果你先做$c_1$，你可以想到一个贪心的策略，那就是选一个位置$i$，若$a[i]$满足$a[i]>max(a[i+1],a[i-1])$则加上他，若满足$a[i]<min(a[i+1],a[i-1])$则减去他，最后一个操作如果是减的话则不进行，相当于这个$b$数组的长度是奇数。说白了就是找波峰波谷，很久前也做过这种题。然后$q$次操作，每次都先撤销$l,r$左右包括自己对$ans$的贡献，然后交换后再加上（注意不要让$l,r$的操作重复）。

AC代码：

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define _for(i,a,b) for(int i = (a);i<(b);++i)
#define endl '\n'
using namespace std;
typedef long long ll;


ll ans;
int a[300005];
void solve(int i,int x){
  if(a[i]>max(a[i+1],a[i-1]))ans+=x*a[i];
  else if(a[i]<min(a[i+1],a[i-1]))ans-=x*a[i];
}
signed main() {
  FIO;
  int T;cin>>T;
  while(T--){
    ans=0;
    int n,q;cin>>n>>q;
    a[0]=a[n+1]=0;
    _for(i,1,n+1)cin>>a[i];
    _for(i,1,n+1)solve(i,1);
    cout<<ans<<endl;
    while(q--){
      int l,r;cin>>l>>r;
      _for(i,-1,2){
        solve(l+i,-1);
        if(r+i>l+1)solve(r+i,-1);
      }
      swap(a[l],a[r]);
      _for(i,-1,2){
        solve(l+i,1);
        if(r+i>l+1)solve(r+i,1);
      }
      cout<<ans<<endl;
    }
  }
  return 0;
}

• 本文作者： baddog
• 本文链接： https://katoli.github.io/2020/09/25/CF-672-Div-2-部分/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！