题意:订购一个披萨,披萨有'A'到'P'共16种配料,你有若干个朋友,每个朋友都有若干个要求,形如"+A-B+E-P"的字符串,表示该朋友的要求为披萨加A,E,不加B,P.当然一个披萨不可能满足每个朋友的所有要求,所以你只需要订购一个披萨,满足每个朋友至少一个要求即可(某朋友喜欢A,披萨里有A即算满足了TA的要求;某朋友不喜欢B,披萨里没有B也算满足了TA的要求).如果能订到符合题意的披萨,输出"Toppings:",然后同一行按照字典序从小到大输出该披萨要加的配料,形如"CELP"(当然也可以什么都不输出,表示什么配料都不用加)(如果有多种方案,输出字典序最小的方案).如果不能订到符合题意的披萨,输出一行"No pizza can satisfy these requests."注意:题目有多组数据,每组数据以单独一行'.'表示结束.
分析:只有16配料,那就把每个要求看做二进制数.设(f[i][0/1])分别表示第i个要求的不要添加的配料和要添加的配料分别构成的二进制数(存int整型).首先对于每个字符串先预处理出它的f数组,然后直接从小到大(保证合法方案的字典序最小)枚举0到(2^{15}-1)判断是否合法即可.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=(1<<16)-1;
int n,bj,f[1005][2];
char ch[1005];
inline void add(char ch[]){
int len=strlen(ch);
for(int i=0;i<len-1;++i){
if(ch[i]=='+')f[n][1]+=1<<(ch[++i]-'A');
else f[n][0]+=1<<(ch[++i]-'A');
}
}
inline bool pd(int x){
for(int i=0;i<n;++i)
if((x&f[i][1])||((x^N)&(f[i][0])))continue;
else return false;
return true;
}
int main(){
while(~(scanf("%s",ch))){
if(ch[0]!='.'){
add(ch);++n;
continue;
}
for(int i=0;i<=N;++i)
if(pd(i)){
bj=1;n=i;
break;
}
if(bj){
printf("Toppings: ");
for(int i=0;i<=15;++i)
if(n&(1<<i))printf("%c",i+'A');
printf("
");
}
else printf("No pizza can satisfy these requests.
");
n=0;bj=0;memset(f,0,sizeof(f));
}
return 0;
}