移动元素

本文主要是介绍移动元素，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

移动元素

就离谱，再次被语文AK，顺便学了点unordered_set

移动元素后

分四种情况
假设元素原位置为\(i\)，移动后为\(j\)
\(pre[]\)为序列前缀和,suf为序列后缀和
1.\(j<i\) 且此时可能存在 \(k<j ，pre[k]=pre[n]/2;\)

2.\(j<i\) 且此时可能存在 \(j<k<i ，pre[k]-sum[n]/2=a[i];\)

3.\(i<j\) 且此时可能存在$ k>j ，suf[k]=suf[n]/2;$

4.\(i<j\) 且此时可能存在$ i<k<j ， suf[k]-suf[n]/2=a[i];$

判断一个数存不存在就可以用哈希
用unordered_set实现，内置哈希表，

t.insert(x)//插入一个数x
t.count(x)//x是否存在,存在返回1，不存在返回0

（其实后缀和，完全可以改变序列顺序变为前缀和)
如果总和为奇数，那就不能分为两个和完全相等的序列

#include<cstdio>
#include<cstring>
#include<iostream>
#include<unordered_set>
#include<algorithm>
using namespace std;
int n;
const int maxn=1e5+10;
int a[maxn],b[maxn];
long long sum[maxn];
bool check(int w[]){
    for(int i=1;i<=n;++i) sum[i]=sum[i-1]+w[i];
    if(sum[n]%2) return false;//总和为奇数
    unordered_set<int> t;
    t.insert(0);
    for(int i=1;i<=n;++i){
        t.insert(w[i]);
        if(t.count(sum[i]-sum[n]/2))return 1;//这个数存在
    }  
    return 0;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1,j=n;i<=n;++i,--j) cin>>a[i],b[j]=a[i];//反转序列，后缀和变前缀和
        if(check(a) || check(b))puts("YES");
        else puts("NO");
    }
}

这篇关于移动元素的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！