UVa 552 Filling the Gaps

题目描述题目要求判断给定的二进制模式集合是否满足“*\texttt{*}*的模式互不相同”的条件并计算将所有*\texttt{*}*替换为000和111后得到的不同字符串的数量。字符串长度L≤15L \le 15L≤15。输入格式输入包含多个测试用例。每个测试用例的第一行包含两个整数单词长度LLL和单词数量NNN。接下来NNN行每行一个长度为LLL的字符串由0、1和*组成。输入以0 0结束。输出格式对于每个测试用例若所有单词中*的位置模式互不相同输出YES和一个空格然后输出替换后得到的不同二进制字符串的数量。否则输出NO。样例输入3 3 10* *0* *00 4 3 1100 1101 110* 0 0输出YES 4 NO YES 0题目分析本题的核心是检查模式唯一性并计算所有可能的填充结果。模式互异性判断将每个单词中的*映射为10和1映射为0得到一个二进制掩码。若所有掩码互不相同则条件满足。填充结果计数对每个单词枚举所有可能的填充*替换为0或1使用布尔数组标记所有得到的二进制数。最后统计标记的数量。复杂度分析每个单词最多有2L2^{L}2L种填充但L≤15L \le 15L≤15总枚举量O(N×2L)O(N \times 2^L)O(N×2L)可接受。代码实现// Filling the Gaps// UVa ID: 552// Verdict: Accepted// Submission Date: 2017-05-11// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intvisited[65536];voidbacktrack(inti,intv,stringpattern){if(ipattern.length())visited[v]1;else{v*2;if(pattern[i]*){backtrack(i1,v,pattern);backtrack(i1,v1,pattern);}else{vpattern[i]-0;backtrack(i1,v,pattern);}}}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intlength,n;while(cinlengthn){if(length0n0){coutYES 0\n;break;}vectorstringwords;vectorintids;string word;for(inti1;in;i){cinword;intid0;for(intj0;jword.size();j){id*2;if(word[j]*)id1;}words.push_back(word);ids.push_back(id);}sort(ids.begin(),ids.end());boolduplicatedfalse;for(inti0;iids.size()-1;i)if(ids[i]ids[i1]){duplicatedtrue;break;}if(duplicated){coutNO\n;continue;}memset(visited,0,sizeof(visited));for(inti0;iwords.size();i)backtrack(0,0,words[i]);inttotalpow(2,length),appeared0;for(inti0;itotal;i)appearedvisited[i];coutYES appeared\n;}return0;}