ZeroJudge 解題筆記：d272. 11583 - Alien DNA

作者：王一哲
日期：2026年5月20日


ZeroJudge 題目連結：d272. 11583 - Alien DNA

解題想法

依序檢查每個 DNA 序列，取新序列與舊序列的交集，如果交集是空集合，要切一刀。

Python 程式碼

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

t = int(input())  # t 組測資
for _ in range(t):  # 執行 t 次
    n = int(input())  # 這組測資有 n 個序列
    common = set(list(input()))  # 共同的鹼基字母，預設為第 1 個序列
    cut = 0  # 切幾刀
    for _ in range(1, n):  # 讀取 n-1 個序列
        dna = set(list(input()))  # 新的序列包含的鹼基字母
        common.intersection_update(dna)  # 取交集更新 common
        if not common:  # 如果 common 是空的
            cut += 1  # cut 加 1
            common = dna  # 更新 common 為 dna
    print(cut)  # 印出答案

C++ 程式碼

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

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int T; cin >> T;
    for(int t=0; t<T; t++) {
        int n; cin >> n;
        string dna; cin >> dna;
        set<char> common (dna.begin(), dna.end());
        int cut = 0;
        for(int i=1; i<n; i++) {
            cin >> dna;
            set<char> tmp;
            for(char c : dna) {
                if (common.count(c) == 1) tmp.insert(c);
            }
            if (tmp.size() == 0) {
                cut++;
                common.clear();
                for(char c : dna) common.insert(c);
            } else {
                common = tmp;
            }
        }
        cout << cut << "\n";
    }
    return 0;
}