这题直接隐式图 + 位运算暴力搜出来的，2.5s险过，不是正法，做完这题做的最大收获就是学会了一些位运算的处理方式。

1.将s中二进制第k位变成0的处理方式：

s = s & (~(1 << pos));

将s中二进制第k位变成1的处理方式：

s = s | (1 << pos);

2.二进制运算：

[1] & ： 1 & 1 = 1 ， 1 & 0 = 0 ， 0 & 0 = 0;

高速推断奇偶性：

    if(a & 1);//为奇数

    if(!(a & 1));//为偶数

[2] |  ： 1 | 1 = 1 ， 0 | 1 = 1 ， 0 | 0 = 0;

[3] ~ ： （按位取反） 比方 10011 取反后为 01100;

[4] ^  :  
假设參加运算的两个二进制同号，结果为0，异号结果为1，比方 1 ^ 1 = 0 , 0 ^ 0 = 0 ,1 ^ 0 = 1 , 0 ^ 1 = 1;

使用方法的话：比方101010100 将后4位翻转，那么能够让它 ^ 000001111 （相当于对指定的一段二进制位取反了）

交换2个值不运用暂时变量：

    a = a ^ b;

    b = b ^ a;

    a = a ^ b;

资料:http://www.cnblogs.com/qkhhxkj/archive/2011/06/29/2093894.html

14062589

658

It's not a Bug, it's a Feature!

Accepted

C++

2.525

2014-08-19 03:16:25

AC代码:

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<vector>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<list>

#include<cmath>

#include<string>

#include<sstream>

#include<ctime>

using namespace std;

#define _PI acos(-1.0)

#define INF (1 << 10)

#define esp 1e-9

#define MOD 100000007

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int,int> pill;

/*===========================================

===========================================*/

#define MAXD 100 + 10

int n,m;

struct Bug{

    vector<int>s[2];

    vector<int>c[2];

    int cost ;

}bug[MAXD];

int Judge(int s,int cur){

    for(int i = 0 ; i < bug[cur].s[0].size(); i++){

        int pos = bug[cur].s[0][i];  /*必须有bug的位置*/

        if(!((s >> pos) & 1))

            return -1;

    }

    for(int i = 0 ; i < bug[cur].s[1].size(); i++){

        int pos = bug[cur].s[1][i];   /*必须没bug的位置*/

        if((s >> pos) & 1)

            return -1;

    }

    for(int i = 0 ; i < bug[cur].c[0].size(); i++){

        int pos = bug[cur].c[0][i];  /*改完之后存在BUG的地方*/

        s = s | (1 << pos);

    }

    for(int i = 0 ; i < bug[cur].c[1].size(); i++){

        int pos = bug[cur].c[1][i];  /*改完之后不存在BUG的地方*/

        s = s & (~(1 << pos));

    }

    return s;

}

int solve(){

    int s = (1 << n) - 1;

    map<int,int>vis;

    priority_queue<pill,vector<pill>,greater<pill> >q;

    q.push(make_pair(0,s));

    while(!q.empty()){

         pill temp = q.top(); q.pop();

         int dist = temp.first;

         int node = temp.second;

         vis[node] = 1;

         if(node == 0) /*全部bug都弥补了*/

         return dist;

         for(int i = 0 ; i < m ; i++){

             int ans = Judge(node,i);

             if(ans >= 0 && !vis[ans]){

                 q.push(make_pair(dist + bug[i].cost,ans));

             }

         }

    }

    return -1;

}

int main(){

    int Case = 1;

    while(scanf("%d%d",&n,&m)){

        if(!n && !m)

            break;

        for(int i = 0 ; i < m ; i++){

            char str[MAXD];

            scanf("%d%s",&bug[i].cost,str);

            bug[i].s[0].clear(); bug[i].s[1].clear();

            bug[i].c[0].clear(); bug[i].c[1].clear();

            int L = strlen(str);

            for(int j = 0 ; j < L; j++)

                if(str[j] == '+')

                    bug[i].s[0].push_back(L - j - 1);  /*必须有补丁的位置*/

                else if(str[j] == '-')

                    bug[i].s[1].push_back(L - j - 1);  /*必须没补丁的位置*/

            scanf("%s",str);

            L = strlen(str);

            for(int j = 0 ; j < L; j++)

                if(str[j] == '+')

                    bug[i].c[0].push_back(L - j - 1);  /*打完后有补丁的位置*/

                else if(str[j] == '-')

                    bug[i].c[1].push_back(L - j - 1);  /*打完没补丁的位置*/

        }

        int ans = solve();

        printf("Product %d\n",Case ++);

        if(ans < 0)

            printf("Bugs cannot be fixed.\n");

        else

            printf("Fastest sequence takes %d seconds.\n",ans);

            printf("\n");

    }

    return 0;

}