ZeroJudge 解題筆記：k851. P5.辨識碼 (Identification)

作者：王一哲
日期：2025年5月9日



ZeroJudge 題目連結：k851. P5.辨識碼 (Identification)

解題想法

我是用字串分割的方式，按照題目要求的長度分割字串，將每個子字串的數字加總存入集合 isum 之中，如果 isum 之中已經有同樣的值就是國民，不需要再檢查後面的子字串。

Python 程式碼

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

import sys

for line in sys.stdin:
    x = int(line)  # 分組數字 x 個
    n = sys.stdin.readline().strip()  # 身分證號
    m = len(n)  # 長度
    isum = set()  # 各組的加總
    flag = False  # 是否為國民，預設為 False
    for i in range(m-x, -1, -x):  # 從最後往前取長度為 x 的子字串
        s = n[i:i+x]  # 子字串
        tot = sum([int(c) for c in s])  # 加總
        if tot in isum:  # 如果 isum 之中已經有 tot
            flag = True; break  # 是國民，中止迴圈
        isum.add(tot)  # tot 加入 isum
    print("Yes" if flag else "No")  # 印出答案

C++ 程式碼

使用時間約為 3 ms，記憶體約為 348 kB，通過測試。

#include <iostream>
#include <string>
#include <set>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int x;  // 分組數字 x 個
    while(cin >> x) {
        string n; cin >> n;  // 身分證號
        int m = (int)n.size();  // 長度
        set<int> isum;  // 各組的加總
        bool flag = false;  // 是否為國民，預設為 False
        for(int i=m-x; i>=0; i-=x){  // 從最後往前取長度為 x 的子字串
            string s = n.substr(i, x);  // 子字串
            int tot = 0;  // 加總
            for(auto c : s) tot += c-'0';
            if (isum.count(tot) == 1) {  // 如果 isum 之中已經有 tot
                flag = true; break;  // 是國民，中止迴圈
            }
            isum.insert(tot);  // tot 加入 isum
        }
        cout << (flag ? "Yes\n" : "No\n");  // 印出答案
    }
    return 0;
}