2011-09-09 19:20:07Morris
d272. 11583 - Alien DNA
d272. 11583 - Alien DNA
/**********************************************************************************/
/* Problem: d272 "11583 - Alien DNA" from UVA11583 */
/* Language: C */
/* Result: AC(16ms, 232KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-09-09 19:17:01 */
/**********************************************************************************/
#include<stdio.h>
main() {
int t, n;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
int i, j, Ans = 0, letter, tmp;
char DNA[27];
letter = (1<<27) - 1;
for(i = 0; i < n; i++) {
scanf("%s", DNA);
for(j = 0, tmp = 0; DNA[j]; j++)
tmp |= 1<<(DNA[j]-'a');
if(tmp&letter) {
letter &= tmp;
} else {
Ans++, letter = tmp;
}
}
printf("%d\n", Ans);
}
return 0;
}
內容 ：
外星人的DNA 比人類的DNA複雜很多。例如 外星人的DNA 不只是單單的固定的序列而是這個序列的各種集合，簡而言之，一個小寫字串的每一個字母都是不同的集合。
人類的只是單純A ,T, C, G在配對組合。
因為外星人的DNA比人類的DNA複雜很多，所以關於用在外星人的演算法也相對的比較複雜，然而你剛進去一家公司三天而已，不太能處理太複雜的工作。
你的工作很簡單。你必須發展出一套軟體來切外星人的DNA，並使切的刀數越少越好 ，每一個認定相同的DNA必須要只少有一個相同的集合。
輸入說明
：
第一行代表有t(t ≤ 100)組測試資料，每一組測試資料有一個N(1 ≤ n ≤ 10,000) 代表有幾個DNA序列，接下來有N行包含一行字串小寫字母，代表一個序列，每一行的字串的字母都不會重複出現。每一個字串都只少有一個字母，有可能出現相同的字串。
輸出說明
：
對於每一個測試資料，輸出一個所需最小的切的次數。
範例輸入 ：
2 5 as sd df fg gh 3 plum orange plum
範例輸出 ：
2 2
提示
：
as sd | df fg | gh 切兩刀
as |sd df| fg gh 切兩刀
as |sd | df| fg | gh 切四刀
plum | orange | plum
所以 最小要切兩刀
出處
：
/**********************************************************************************/
/* Problem: d272 "11583 - Alien DNA" from UVA11583 */
/* Language: C */
/* Result: AC(16ms, 232KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-09-09 19:17:01 */
/**********************************************************************************/
#include<stdio.h>
main() {
int t, n;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
int i, j, Ans = 0, letter, tmp;
char DNA[27];
letter = (1<<27) - 1;
for(i = 0; i < n; i++) {
scanf("%s", DNA);
for(j = 0, tmp = 0; DNA[j]; j++)
tmp |= 1<<(DNA[j]-'a');
if(tmp&letter) {
letter &= tmp;
} else {
Ans++, letter = tmp;
}
}
printf("%d\n", Ans);
}
return 0;
}