CF47D Safe(dfs)

给你一堆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

91 发布于 2019-09-10 21:23 评论(0) 阅读(10)
发表评论(最多500字):

推荐博客排行

统计信息

  • 博客[ 8281 ]
  • 评论[ 4 ]
  • 阅读[ 247271 ]