Problem - C - Codeforces
大致意思:
找前缀,排序后使得本位之前数字和等于该位
(以下代码超时了)
#include<bits/stdc++.h>
typedef long long ll;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const ll N=1e2+1;
using namespace std;int main()
{IOS;int t;cin>>t;while(t--){int n;cin>>n;int k=n+2;ll m[k],b[k];for(int i=1;i<=n;i++){cin>>m[i];b[i]=m[i];}m[0]=0;b[0]=0;int ans=0;for(int j=1;j<=n;j++){ll sum=0;sort(b+1,b+j+1);for(int i=0;i<j;i++) sum+=b[i];//cout<<"jian"<<sum<<endl;if(sum==b[j]) {ans++;}}cout<<"here"<<ans;cout<<endl;}return 0;
}
正确思路
计算数组前缀和,并检查当前前缀和的一半是否已经出现过。如果前缀和的一半在前缀中出现过,那么这个前缀就是“好”的。
ac代码
#include<bits/stdc++.h>
typedef long long ll;#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const ll N=1e2+1;
using namespace std;int main()
{IOS;int t;cin>>t;while(t--){int n;cin>>n;ll s=0,ans=0;map<ll,int> mp;for(int i=1,x;i<=n;i++){cin>>x;mp[x] = 1;s+=x;if(s%2==0) ans+=mp[s/2];}cout<<ans;cout<<endl;}return 0;
}