ZeroJudge 解題筆記：d563. 等值首尾和

作者：王一哲
日期：2025年8月31日


ZeroJudge 題目連結：d563. 等值首尾和

解題想法

題目敘述有兩個問題：

1. 題目雖然說有兩行測資，第一行為一個數字 N，代表第二行有 N 個用空格分隔的數字，但實際上只有一行，如果用 Python 解題會出事。
2. 範例的寫法看起來好像從左、右加總的數量要一樣，但其實不需要，只要前綴和、後綴和相等就好，不看數量。

Python 程式碼

使用時間約為 0.1 s，記憶體約為 16.4 MB，通過測試。

arr = list(map(int, input().split()))[1:]  # 讀取一行資料轉成串列，不取首項
psum = 0  # 前綴和
cand = set()  # 可能的加總
for a in arr:  # 依序讀取 arr 的資料
    psum += a  # 更新 psum
    cand.add(psum)  # psum 加入 cand
ssum = 0  # 後綴和
cnt = 0  # 答案
for a in arr[::-1]:  # 反向讀取 arr 的資料
    ssum += a  # 更新 ssum
    if ssum in cand: cnt +=1  # 如果 ssum 在 cand 之中，cnt 加 1
print(cnt)  # 印出 cnt

C++ 程式碼

使用時間約為 38 ms，記憶體約為 5.2 MB，通過測試。

#include <cstdio>
#include <set>
using namespace std;

int main () {
    int n; scanf("%d", &n);  // 接下來有 n 項
    int arr[n], psum = 0;  // 陣列，前綴和
    set<int> cand;  // 可能的加總
    for(int i=0, a; i<n; i++) {  // 讀取 n 個數字
        scanf("%d", &a);
        arr[i] = a;  // 更新 arr
        psum += a;  // 更新 psum
        cand.insert(psum);  // psum 加入 cand
    }
    int ssum = 0, cnt = 0;  // 後綴和，答案
    for(int i=n-1; i>=0; i--) {  // 反向讀取 arr 的資料
        ssum += arr[i];  // 更新 ssum
        if (cand.count(ssum) == 1) cnt++;  // 如果 ssum 在 cand 之中，cnt 加 1
    }
    printf("%d\n", cnt);  // 印出 cnt
    return 0;
}