類型： 暴力枚舉，搜索
題目：
You are responsible for ordering a large pizza for you and your friends. Each of them has told you what he wants on a pizza and what he does not; of course they all understand that since there is only going to be one pizza, no one is likely to have all their requirements satisfied. Can you order a pizza that will satisfy at least one request from all your friends?
The pizza parlor you are calling offers the following pizza toppings; you can include or omit any of them in a pizza:
Input Code Topping
A Anchovies
B Black Olives
C Canadian Bacon
D Diced Garlic
E Extra Cheese
F Fresh Broccoli
G Green Peppers
H Ham
I Italian Sausage
J Jalapeno Peppers
K Kielbasa
L Lean Ground Beef
M Mushrooms
N Nonfat Feta Cheese
O Onions
P Pepperoni
Your friends provide you with a line of text that describes their pizza preferences. For example, the line
+O-H+P;
reveals that someone will accept a pizza with onion, or without ham, or with pepperoni, and the line
-E-I-D+A+J;
indicates that someone else will accept a pizza that omits extra cheese, or Italian sausage, or diced garlic, or that includes anchovies or jalapenos.
題目大意：
你負責去訂購一個大比薩， 但是你的朋友們對於要添加什麼或者不添加什麼都有不同的要求。 但是你的朋友們也知道不可能滿足全部的要求。所以你要選擇一個訂購方案，讓所有人至少滿足其中一個要求。 注意，如果某人不想要哪個，那麼不添加那個也算是滿足了他的一個要求。
分析與總結：
題目只有16種東西選擇， 對於每種東西之是選擇或者不選澤兩種狀態。那麼用暴力枚舉法完全可以做出。
用一個數字，它的各個二進制位表示定或者不定。枚舉0 ～ (1<<16)-1即可。
代碼：
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char str[100][100];
int nIndex;
int main(){
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
while(gets(str[0])){
nIndex = 1;
while(gets(str[nIndex]), str[nIndex++][0]!='.') ;;
int status=0;
bool flag=true;
int maxNum = (1<<16)-1;
while(status <= maxNum){
flag = true;
for(int i=0; i<nIndex-1; ++i){
bool ok = false;
int pos=0;
while(pos < strlen(str[i])){
if(str[i][pos]=='+'){
if((status >> (str[i][pos+1]-'A')) & 1 ){
ok = true; break;
}
}
else if(str[i][pos]=='-'){
if( !((status >> (str[i][pos+1]-'A')) & 1)){
ok = true;
break;
}
}
pos += 2;
}
if(!ok){flag=false ; break; }
}
if(flag) break;
++status;
}
if(!flag) printf("No pizza can satisfy these requests.\n") ;
else{
int pos=0;
printf("Toppings: ");
while(pos <16){
if(status & 1) printf("%c", pos+'A');
++pos; status >>= 1;
}
printf("\n");
}
}
return 0;
}
