UVa 565：Pizza Anyone？

UVa 565：Pizza Anyone？2014-10-11 shuangde800 题目链接：

类型：暴力枚举，搜索

题目：

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;

URL：http://www.bianceng.cn/Programming/sjjg/201410/45699.htm

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 LOCALfreopen（"input.txt", "r", stdin）;#endifwhile（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.
"） ;else{int pos=0;printf（"Toppings: "）;while（pos <16）{if（status & 1） printf（"%c", pos+"A"）;++pos; status >>= 1;}printf（"
"）;} }return 0;}