Global Warming
unknown
c_cpp
22 days ago
2.1 kB
1
Indexable
Never
output #include <iostream> using namespace std; int oo = 2000000000; int T, n, m; int total, nn; int str[55][27], vsW[55], choose[27], vs[27]; int result; int Len(char a[]){ int ll = 0; while(a[ll] != '\0') ll++; return ll; } bool checkWord(int index, bool isChoose){ for(int j = 0; j < 27; j++){ if(!isChoose && str[index][j] == 1 && vs[j] == 1) return false; else if(isChoose && str[index][j] == 1 && vs[j] == 0) return false; } return true; } void backtrack(int index, int from, bool isChoose){ if((isChoose && index == m) || (!isChoose && index == total - m)){ int cnt = 0; for(int i = 0; i < n; i++){ if(vsW[i] == 0 && checkWord(i, isChoose)) cnt++; } if(cnt > result) result = cnt; return; } for(int i = from; i < 27; i++){ if(choose[i] == 1 && vs[i] == 0){ vs[i] = 1; backtrack(index + 1, i+1, isChoose); vs[i] = 0; } } } int main(){ cin >> T; for(int tc = 1; tc <= T; tc++){ // input and initial char temp[55]; total = 0, nn = 0; for(int j = 0; j < 27; j++) choose[j] = 0, vs[j] = 0; cin >> n >> m; for(int i = 0; i < n; i++){ vsW[i] = 0; for(int j = 0; j < 27; j++) str[i][j] = 0; cin >> temp; int cnt = 0; int l = Len(temp); for(int j = 0; j < l; j++){ if(str[i][temp[j]-'a'] == 0){ str[i][temp[j]-'a'] = 1; cnt++; } } if(cnt <= m){ for(int j = 0; j < 27; j++){ if(str[i][j] == 1 && choose[j] == 0){ choose[j] = 1; total++; } } }else{ vsW[i] = 1; nn++; } } result = 0; // solve problem if(m >= total){ result = n - nn; }else{ if(total / 2 < m) backtrack(0, 0, false); else backtrack(0, 0, true); } // output cout << "#" << tc << " " << result << endl; } return 0; } #1 1 #2 3 #3 3 #4 3 #5 2 #6 2 #7 2 #8 0 #9 1 #10 1 #11 4 #12 2 #13 2 #14 1 #15 1 #16 1 #17 5 #18 12 #19 1 #20 3 #21 6 #22 4 #23 4 #24 7 #25 11 #26 0 #27 14 #28 4 #29 2 #30 1 #31 9 #32 8 #33 13 #34 0 #35 5 #36 50 #37 5 #38 3 #39 5 #40 7 #41 4 #42 5 #43 4 #44 1 #45 50 #46 1 #47 9 #48 24 #49 1 #50 3
Leave a Comment