UVa 565 - Pizza Anyone?
题目链接：
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=109&page=show_problem&problem=506
类型： 暴力枚举，搜索
题目：
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:
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即可。
代码：
#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;}—— 生命的意义，在于赋予它意义。
原创 http://blog.csdn.net/shuangde800 ， By D_Double (转载请标明)