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;
}