uva 565 - Pizza Anyone?(暴力枚舉 + 二進制）

題目：uva 565 - Pizza Anyone?(暴力枚舉 + 二進制）

題目大意：題目是說有一個人要幫他的朋友們定批薩，然後每個朋友都有自己的口味要求，問能不能定一個批薩然後滿足每個朋友的至少一個要求。

能就輸出所定批薩裡面加的東西，，輸出要求按字典序；

不能就輸出：No pizza can satisfy these requests.

解題思路：這題裡面有16種材料，每種材料只有取與不取的可能，這樣就有 2^16 種（ 0 - 2^16 - 1），枚舉出每種情況然後在分別看是否能滿足每個朋友的至少的一個要求，可以就輸出。不用再往後找了。但是這題的數據量不是很小，65535 * 100 （t） * 12 = 78642000,但是這種狀況畢竟很少很極端，但是這樣時間也很緊迫，所以可以用二進制來優化一下時間。

代碼：

#include 
#include 

const int N = 100;
const int M = 16;
char str[M * 2];
int t;
int result[M];
bool flag;

struct TOPPING {

	char need[M];//需要的
	char omit[M];//不要的
	int cnt1, cnt2;//前面兩個數組內元素的個數
} topping[N];

void init () {

	t = flag = 0;
	memset (topping, 0, sizeof (topping));
}
//把每個字符串分解出需要和不需要的東西
void handle () {

	for (int i = 0; i < strlen (str); i++) {

		if (str[i] == '+') {

			topping[t].need[topping[t].cnt1++] = str[i + 1];
			i ++;
		} else if (str[i] == '-') {

			topping[t].omit[topping[t].cnt2++] = str[i + 1];
			i ++;
		}
	}
	t++;
}
//判斷result當前情況下是否可以滿足每個朋友的至少一個請求
bool judge() {

	bool tag;
	for (int j = 0; j < t; j++) {	
		tag = 0;
		for (int k = 0; k < topping[j].cnt2; k++) 
			if (result[topping[j].omit[k] - 'A'] == 0) {

				tag = 1;
				break;
			}
		if (tag)
			continue;
		for (int k = 0; k < topping[j].cnt1; k++)
			if (result[topping[j].need[k] - 'A'] == 1) {

				tag = 1;
				break;
			}
		if (!tag)
			return false;
	}
	return true;
}
//將每個十進值數所對應的二進制數表示為材料的取否
void solve (int n) {

	int pos = 0;
	while (pos < M) {

		result[pos++] = n & 1;
		n >>= 1;
	}
	if (judge())
		flag = 1;
}

int main () {

	while (scanf ("%s", str) != EOF) {

		init ();
		while (str[0] != '.') {

			handle ();
			scanf ("%s", str);
		}

		int m = 1<<17 - 1;	
		int n = 0;
		//		printf ("%d\n", m);	
		while (n < m) {

			solve (n);
			if (flag)
				break;
			n++;
		}
		if (!flag)
			printf ("No pizza can satisfy these requests.\n");
		else {

			printf ("Toppings: ");
			for (int i = 0; i < M; i++)
				if (result[i])
					printf ("%c", i + 'A');
			printf("\n");

		}
	}
	return 0;
}