G3011 [GESP202409 三级] 平衡序列 题解

知识点：前缀和、序列划分、整数范围。

解题思路

求总和sum，再扫描前n-1项的前缀和p。若某处2p==sum，就可分成和相等的两个非空部分。

为什么正确

任意合法切分都位于相邻元素之间，前后和相等等价于p=sum-p。

易错点

不能在最后一项之后切分；使用long long计算总和和倍增前缀和。

复杂度

每组时间O(n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--) {
        int n;
        cin>>n;
        vector<int>a(n);
        long long sum=0,p=0;
        for(int &x:a) {
            cin>>x;
            sum+=x;
        }
        bool ok=false;
        for(int i=0;i<n-1;i++) {
            p+=a[i];
            if(p*2==sum)ok=true;
        }
        cout<<(ok?"Yes":"No")<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。