题目描述

精确覆盖问题

C++ 代码

/*
64*5>300
*/


#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
struct data1
{   
    int cnt;
    unsigned int a[6];
    void date()    
    {
        cnt = 0;
        memset(a,0,sizeof a);
    }
}bt[17];

//将这个二进制数的位数进行拆分

int aa,m,n;
bool dfs(int pos,data1 jtu)
{
    if(jtu.cnt == n) return true;
    if(pos==m) return false; 

    if(dfs(pos+1,jtu)) return true;  //这个是没有选择当前的这个pos位置所对应的二进制数

    //这个是去尽力去选择这个pos所对应的二进制数,结果失败了就去返回false
    int i;
    for(i=0;i<5;i++)    //分别去判断每一个小部分
    {
        if((jtu.a[i]&bt[pos].a[i])==0) jtu.a[i] ^=  bt[pos].a[i];
        else break; 
    }
    if(i!=5) return false;  

    //这个是选择成功了,故去直接对jtu进行更新,进行下一层的递归
    jtu.cnt += bt[pos].cnt;   
    if(dfs(pos+1,jtu)) return true;

    return false;
}


//储存方式
//将其的位数进行分割,之后再去进行简便判断
int main()
{
    while(cin>>m>>n)
    {
        for (int i=0;i<m;i++)
        {
            bt[i].date();
            for (int j=0;j<n;j++)
            {
                scanf("%1d",&aa);
                if(aa==1) 
                {
                    bt[i].a[j/64] ^= 1LL<<(j>64 ? j%64:j);   //二进制中1的增加就是靠着这种^运算符号
                    bt[i].cnt++;
                }
            }
        }
        data1 jtc;jtc.date();
        if(dfs(0,jtc)) cout<<"YES\n";
        else cout<<"NO\n";  
    }
    return 0;
}