D. Cleaning(思维好题+前缀）

51 阅读 0 评论 34 点赞

我是靠谱客的博主简单皮皮虾，最近开发中收集的这篇文章主要介绍D. Cleaning(思维好题+前缀），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

https://codeforces.com/contest/1474/problem/D

题意:n个数，现在你可以取出相邻的都不为0的数，使得他们同时减1，如果一个堆为0了，它并不会消失掉，此时我们有至多一次机会操作，交换相邻两个数的位置，问能不能使得全部的数都变为0.

思路:首先发现,端点一定要<=后面的值，不然肯定不成立。

于是a2>=a1,减了之后a2=a2-a1;此时a2变成端点，同理可知a3>=此时的a2才能成立.

那么对于从尾巴开始也是这个道理。

那么中间的过程用一个前缀去记录。也就是用前缀表示前后相邻能相减，那么此时后面的这个数变成了多少。后缀同理。

如果中途碰到了pre[i-1]>a[i]的，那么此时意味着如果将这两个相邻的减了，就将导致a[i-1]变成一个“空岛"，不能满足题目的要求。对于这种情况，记录为pre[i]=inf/2;【为什么/2，因为后端开始也有这个情况，在交换相邻项的时候需要判前后缀是否相等。而如果suf[]=inf/2的话，本不能相等的两个数变成了inf=inf——导致错判]

然后枚举判断前后缀pre[i]和suf[i+1]是否一样。一样就可以。不一样尝试交换，看可不可以。

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=2e5+1000;
typedef long long LL;
LL a[maxn],pre[maxn],suf[maxn];
const LL inf=1e18;
int main(void)
{
  cin.tie(0);std::ios::sync_with_stdio(false);
  LL t;cin>>t;
  while(t--){
    LL n;cin>>n;
    for(LL i=0;i<=n+10;i++) pre[i]=suf[i]=0;
    for(LL i=1;i<=n;i++) cin>>a[i];
    for(LL i=1;i<=n;i++){
        if(a[i]>=pre[i-1]){
            pre[i]=a[i]-pre[i-1];
        }
        else pre[i]=inf/2;
    }
    for(LL i=n;i>=1;i--){
        if(a[i]>=suf[i+1]){
            suf[i]=a[i]-suf[i+1];
        }
        else suf[i]=inf;
    }
    bool flag=1;
    for(LL i=1;i<=n-1;i++){
        if(pre[i]==suf[i+1]){
            flag=0;
            break;
        }
        else{
            ///交换相邻石堆
            LL A=a[i];LL B=a[i+1];
            if(A>=suf[i+2]&&B>=pre[i-1]){
                A-=suf[i+2];B-=pre[i-1];
                LL cnt=A-B;
                if(cnt==0){
                    flag=0;
                    break;
                }
            }
        }
    }
    if(flag==0){
        cout<<"YES"<<endl;
    }
    else cout<<"NO"<<endl;
  }
return 0;
}