【題解】ZeroJudge d272: 11583 – Alien DNA

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d272
【解題想法】字串比對,位元操作

  • 只要有一個(或以上)相同的集合,就可認定為相同的DNA。
  • 【例】五個序列:as sd df fg gh
    • as sd:有交集 s,可認定為相同的DNA
    • df 與 [as sd] 無交集,as sd | df fg gh
    • df fg:有交集 f,可認定為相同的DNA
    • gh 與 [df fg] 無交集,as sd | df fg | gh
#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T, N, pre_s, cur_s, ans;
    string s;

    cin >> T;
    while (T--) {
        cin >> N;
        ans = 0;
        pre_s = (1<<27) - 1; // z, y, x, ..., c, b, a 各一個
        for (int i=0; i<N; i++) {
            cin >> s;
            cur_s = 0;
            for (int j=0; j<s.size(); j++) {
                cur_s |= (1 << (s[j] - 'a')); // 標示出現過的字母的位置
            }
            if (pre_s & cur_s) {
                // 有交集 -> 取交集
                pre_s = pre_s & cur_s;
            } else {
                // 無交集 -> 重置
                ans++;
                pre_s = cur_s;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}
分享本文 Share with friends