给你一堆01串s，每个01串s都有一个对应的数字k
你需要找到有多少个01串满足与每个s不同的数字个数都是k
一开始写了个bitset异或乱搞，结果T了，改成dfs暴力往下搜就完事了
枚举每一位上的数字，有不相同的数字超过了k则剪枝，甚至加了map去重
代码：
#include <bits/stdc++.h> using namespace std; int n,m,k[15],dif[15]; char s[15][40]; string tmp="0000000000000000000000000000000000000000"; map<string,int> mp; void dfs(int p,char c){ if(p==n+1){ for(int i=1;i<=m;++i) if(dif[i]!=k[i]) return; mp[tmp]=1; return; } if(c==‘1‘) tmp[p]=‘1‘; for(int i=1;i<=m;++i){ if(tmp[p]!=s[i][p]){ dif[i]++; if(dif[i]>k[i]){ for(int j=1;j<=i;++j){ if(tmp[p]!=s[j][p]) dif[j]--; } if(c==‘1‘) tmp[p]=‘0‘; return; } } } dfs(p+1,‘0‘); dfs(p+1,‘1‘); for(int i=1;i<=m;++i){ if(tmp[p]!=s[i][p]) dif[i]--; } if(c==‘1‘) tmp[p]=‘0‘; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;++i) scanf("%s%d",s[i]+1,&k[i]); dfs(1,‘0‘); dfs(1,‘1‘); printf("%d",(int)mp.size()); return 0; }
原文：https://www.cnblogs.com/oneman233/p/11503017.html