就离谱,再次被语文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"); } }