题目描述

题目要求为每个人准备一个披萨，使得每个人至少有一个要求被满足。每个人给出若干要求，每个要求是+（需要某种配料）或-（不需要某种配料）。配料共161616种（A\texttt{A}A到P\texttt{P}P）。需要找到一个配料组合，使得对于每个人，至少有一个要求被满足。输出满足条件的配料（按字母顺序），若无解则输出No pizza can satisfy these requests.

输入格式

输入包含多个测试用例。每个测试用例由若干行组成，每行是一个人的要求列表（由若干+X或-X组成，以分号结束），最后以一行单独的.结束。输入以文件结束符（EOF\texttt{EOF}EOF）终止。

输出格式

对于每个测试用例，输出一行Toppings:后跟字母列表（按字母顺序），若无解则输出No pizza can satisfy these requests.

样例

输入

+AB+C+D-E-F-G-H; -A-B+C+D-E-F+G+H; -A+B-C+D-E+F-G+H; +AB+C+D; +E+F+F+H; +AB-G; +O+J-F; +H+I+C; +P; +O+M+L; +M-L+P; +AB+C+D; +E+F+F+H; +AB-G; +P-O; +O+J-F; +H+I+C; +P; +O; +O+M+L; -O-P; +M-L+P; .

输出

Toppings: Toppings: CELP No pizza can satisfy these requests.

题目分析

本题的核心是查找满足所有约束的配料组合。由于配料只有161616种，可以枚举所有216=655362^{16} = 65536216=65536种可能组合，检查是否满足每个人至少一个要求。

约束表示

对于每个人，将其要求表示为两个位掩码：like\textit{like}like（需要该配料的集合）和unlike\textit{unlike}unlike（不需要该配料的集合）。设披萨配料组合为iii（161616位掩码），则第jjj个人的要求被满足的条件为：
(i&like[j])≠0或(∼i&unlike[j])≠0 (i \& \text{like}[j]) \neq 0 \quad \text{或} \quad (\sim i \& \text{unlike}[j]) \neq 0(i&like[j])=0或(∼i&unlike[j])=0

枚举

枚举所有iii从000到216−12^{16}-1216−1，检查是否满足所有人。找到的第一个解即为答案（按题意，输出字母顺序，但枚举顺序已保证字母顺序？实际上需要按字母顺序输出，但枚举时iii的二进制位顺序对应字母A\texttt{A}A到P\texttt{P}P，输出时按位输出即可得到字母顺序）。

复杂度分析

216=655362^{16} = 65536216=65536，每人检查O(1)O(1)O(1)，总O(65536×人数)O(65536 \times \text{人数})O(65536×人数)，可接受。

代码实现

// Pizza Anyone// UVa ID: 565// Verdict: Accepted// Submission Date: 2016-08-18// UVa Run Time: 0.220s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intlike[12],unlike[12],counter=0;voidsetConstraint(string data){data.erase(data.end()-1);bitset<16>like_pizza(0),unlike_pizza(0);for(inti=0;i<data.length();i+=2){if(data[i]=='+')like_pizza.set(data[i+1]-'A');elseunlike_pizza.set(data[i+1]-'A');}like[counter]=like_pizza.to_ulong();unlike[counter]=unlike_pizza.to_ulong();counter++;}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;while(getline(cin,line)){setConstraint(line);while(getline(cin,line),line!=".")setConstraint(line);boolsuccess=false;for(inti=0;i<=65536;i++){boolgood=true;for(intj=0;j<counter;j++)if((i&like[j])||(~i&unlike[j]))continue;else{good=false;break;}if(good){cout<<"Toppings: ";bitset<16>pizza(i);for(inti=0;i<16;i++)if(pizza.test(i))cout<<(char)('A'+i);cout<<'\n';success=true;break;}}if(!success)cout<<"No pizza can satisfy these requests.\n";counter=0;}return0;}