UVa11583 - Alien DNA(設計解題、位元運算)

題目大意

我們發現外星人的 DNA 片段了！但我們必須要將這些 DNA 的片段組裝成一組 DNA。(注意：一組 DNA 是我定義的名詞)
而組裝的方式則是只要 DNA 片段中有一個小寫字母與另一個 DNA 片段小寫字母組在一起即可。
P.S. 如果想要讓一組 DNA 有三個或以上的片段組成時，則新進來的 DNA 必須都跟其他 DNA 片斷有一個以上的小寫字母連接。

其中一組 DNA 是連續的，因此不可以拿第一個片段 DNA 與第三個片段 DNA 組成一個新的 DNA。
而題目要求則是，我們最少需要切幾次可以讓裡面的片段 DNA 們都是一組 DNA。

UVa 11583 Alien DNA

重點觀念

• 英文閱讀
  • 對很重要 least one common base. 我看不出來他是指說組裝的方式則是只要 DNA 片段中有一個小寫字母與另一個 DNA 片段小寫字母組在一起即可。
  • 然後我也看不出來一組 DNA 是連續的，這個題目要求…
• 程式編寫
  有效率、簡潔的程式碼

分析

這個問題如果有理解英文後就很好解。

• 我們用 int 的 2 進位位數來表示每個字母是否在這組 DNA 中
  • 這組 DNA 預設情況 000...0
  • 這組 DNA 有了 Z 之後 100...0
• 上面這種方式透過數字表達的 DNA 我稱為數字 DNA
• 之後我們讓片段 DNA 先產生出數字 DNA
• 判斷片段數字 DNA 是否跟現在這組數字 DNA 有共同的地方，如果有就讓 (片段數字 DNA & 這組數字 DNA
  • 如果沒有就讓當前這組 DNA 升級成一組 DNA
• 輸出共有幾組 DNA

因為題目有說明片段 DNA 只能夠跟左右片段連接，因此如果是不同種的組裝方式，組合數量也不會不一樣。
一組內的片段 DNA 都必須有一個數字相同，所以往往切斷點就是無法組合的片段 DNA

參考連結

【題解】ZeroJudge d272: 11583 – Alien DNA by YUI HUANG 演算法學習筆記

心得

這題的英文不知道是不是我邏輯差，我怎麼一直看不懂RRRRR。

知道了邏輯後，稍微學習了優秀大神的程式碼編寫方法，太棒了太棒了。又被教到了一課
用二進位來編寫真的很不賴。

不愧是竹女阿太秀了

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define int long long
#define LOCAL
#define DEBUG
#define MAXN 10020
using namespace std;
int t, n ;
int segment, dna;
string s;

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> n;
        segment = (1 << 27) - 1; //產生出一組 A~Z 都是 1 的數字 DNA，才一定能跟第一組做組合 
        int ans = 0;
        for(int i = 0; i < n; i++){
            cin >> s;
            dna = 0; //片段數字 DNA
            for(int j = 0; j < s.size(); j++){
                dna |= (1 << (s[j] - 'a'));
                //數字 DNA 表達方式 0 表示沒有 1 表示有
                //a 是 個位數、b 是十位數... 以此類推
            }

            //如果可以成為一組，那就一組八!
            //注意必須用 and，因為要每個片段 DNA 都有一個小寫字母相同
            if(dna & segment ) segment &= dna; 
            else{
                segment = dna; //與前面的一組 DNA 不同，這個片段 DNA 升級成一組 DNA 
                ans++; //找到切斷點了! 
            }
        }
        cout << ans << '\n';
    }
    return 0;
}