记录编号	583153	评测结果	AAAAAAAAAA
题目名称	[CTSC 1999] BUG修复	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.380 s
提交时间	2023-10-05 14:51:33	内存使用	2.88 MiB

#include <bits/stdc++.h> 
using namespace std;
//搜索 
typedef unsigned long long ll;
const int N = 110,p = 1e9+10;
int n,m,ans = INT_MAX;
int b[31];
map<ll,bool>q;
struct made{
    int m;
    int la[31],ne[31];
}a[N]; 
ll hash_(int s[31]){//hash不能为函数名 
    ll su = 0,p1 = 1;
    for(int i = 1;i <= n;i++){
        su += p1 * s[i];
        p1 *= p;
    }
    return su;
}//hash 
bool can(int x[31],int y[31]){
    for(int i = 1;i <= n;i++)
        if(x[i] != y[i] && y[i] != 0)return 0;
    return 1;
}
bool check(int s[31]){
    for(int i = 1;i <= n;i++)
        if(s[i] != 1)return 0;
    return 1;
}
void dfs(int x,int u[31]){
    if(x >= ans)return;//剪枝 
    int s[31] = {0};
//    memcpy(s,u,sizeof(s)); 
    for(int i = 1;i <= n;i++)s[i] = u[i];//一样
    if(check(s)){
        ans = min(ans,x);
        return;
    }//深搜到答案 
    for(int i = 1;i <= m;i++){
        int f = 0;
        if(can(s,a[i].la) && q[hash_(s)] == 0){//能用补丁且未被搜过 
            q[hash_(s)] = 1;
            for(int j = 1;j <= n;j++)
                if(a[i].ne[j] != 0)s[j] = a[i].ne[j];//更新 
            dfs(x+a[i].m,s);
            for(int i = 1;i <= n;i++)s[i] = u[i];// 
            q[hash_(s)] = 0;//回溯 
        }
    }
}
int main(){
    freopen("bug.in","r",stdin);
    freopen("bug.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++)b[i] = 2;//初始都有病毒 
    for(int i = 1;i <= m;i++){
        char c1[21],c2[21];
        scanf("%d%s%s",&a[i].m,c1+1,c2+1);
        for(int j = 1;j <= n;j++){
            if(c1[j] == '0')a[i].la[j] = 0;// 
            if(c1[j] == '-')a[i].la[j] = 1;
            if(c1[j] == '+')a[i].la[j] = 2;
            if(c2[j] == '0')a[i].ne[j] = 0;
            if(c2[j] == '-')a[i].ne[j] = 1;
            if(c2[j] == '+')a[i].ne[j] = 2;//变为int数组 
        }
    }
    dfs(0,b);
    if(ans == INT_MAX)printf("0");//！！ 
    else printf("%d\n",ans);
    
    return 0;
}