UVa 565 Pizza Anyone

题目描述题目要求为每个人准备一个披萨使得每个人至少有一个要求被满足。每个人给出若干要求每个要求是需要某种配料或-不需要某种配料。配料共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.样例输入ABCD-E-F-G-H; -A-BCD-E-FGH; -AB-CD-EF-GH; ABCD; EFFH; AB-G; OJ-F; HIC; P; OML; M-LP; ABCD; EFFH; AB-G; P-O; OJ-F; HIC; P; O; OML; -O-P; M-LP; .输出Toppings: Toppings: CELP No pizza can satisfy these requests.题目分析本题的核心是查找满足所有约束的配料组合。由于配料只有161616种可以枚举所有216655362^{16} 6553621665536种可能组合检查是否满足每个人至少一个要求。约束表示对于每个人将其要求表示为两个位掩码like\textit{like}like需要该配料的集合和unlike\textit{unlike}unlike不需要该配料的集合。设披萨配料组合为iii161616位掩码则第jjj个人的要求被满足的条件为(ilike[j])≠0或(∼iunlike[j])≠0 (i \ \text{like}[j]) \neq 0 \quad \text{或} \quad (\sim i \ \text{unlike}[j]) \neq 0(ilike[j])0或(∼iunlike[j])0枚举枚举所有iii从000到216−12^{16}-1216−1检查是否满足所有人。找到的第一个解即为答案按题意输出字母顺序但枚举顺序已保证字母顺序实际上需要按字母顺序输出但枚举时iii的二进制位顺序对应字母A\texttt{A}A到P\texttt{P}P输出时按位输出即可得到字母顺序。复杂度分析216655362^{16} 6553621665536每人检查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//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intlike[12],unlike[12],counter0;voidsetConstraint(string data){data.erase(data.end()-1);bitset16like_pizza(0),unlike_pizza(0);for(inti0;idata.length();i2){if(data[i])like_pizza.set(data[i1]-A);elseunlike_pizza.set(data[i1]-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);boolsuccessfalse;for(inti0;i65536;i){boolgoodtrue;for(intj0;jcounter;j)if((ilike[j])||(~iunlike[j]))continue;else{goodfalse;break;}if(good){coutToppings: ;bitset16pizza(i);for(inti0;i16;i)if(pizza.test(i))cout(char)(Ai);cout\n;successtrue;break;}}if(!success)coutNo pizza can satisfy these requests.\n;counter0;}return0;}