Global Warming

mail@pastecode.io avatar
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