[NOIP2003]侦探推理

描述明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中，于是他召集了一群同学玩推理游戏。游戏的内容是这样的，明明的同学们先商量好由其中的一个人充当罪犯（在明明不知情的情况下），明明的任务就是找出这个罪犯。接着，明明逐个询问每一个同学，被询问者可能会说：

证词中出现的其他话，都不列入逻辑推理的内容。
明明所知道的是，他的同学中有N个人始终说假话，其余的人始终说真。
现在，明明需要你帮助他从他同学的话中推断出谁是真正的凶手，请记住，凶手只有一个！输入输入由若干行组成，第一行有二个整数，M（1≤M≤20）、N（1≤N≤M）和P（1≤P≤100）；
M是参加游戏的明明的同学数，N是其中始终说谎的人数，P是证言的总数。接下来M行，
每行是明明的一个同学的名字（英文字母组成，没有主格，全部大写）。
往后有P行，每行开始是某个同学的名宇，紧跟着一个冒号和一个空格，后面是一句证词，符合前表中所列格式。证词每行不会超过250个字符。
输入中不会出现连续的两个空格，而且每行开头和结尾也没有空格。输出如果你的程序能确定谁是罪犯，则输出他的名字；如果程序判断出不止一个人可能是
罪犯，则输出 Cannot Determine；如果程序判断出没有人可能成为罪犯，则输出 Impossible。

我算法时间复杂度是O(m*p*2^n),若取 m,n,p最大，则就有了 2097152000 之巨，肯定会超时，但幸运的是该题实际数据范围 n<=8,m<=10,p<=10; 哈哈！这件事告诉我们在考场上依据自己实力能拿分就拿分，不要太好高。

  1 #include<iostream>
  2 #include<string.h>
  3 #include<fstream>
  4 using namespace std;
  5 
  6 int n,m,p,guilty=0;
  7 string tool[5];
  8 bool real[22]={0};
  9 struct{string name;string say[101];int n;}a[22];
 10 
 11 void Init(){
 12      cin>>n>>m>>p;
 13      tool[0]="I am guilty.";
 14      tool[1]="I am not guilty.";
 15      tool[2]="is guilty.";
 16      tool[3]="is not guilty.";
 17      tool[4]="Today is";
 18     
 19      m=n-m;
 20      
 21      for(int i=1;i<=n;++i)
 22      cin>>a[i].name,a[i].n=0;
 23     
 24      string sa,na;
 25      getline(cin,sa,'\n');
 26      for(int i=1;i<=p;++i)
 27      {
 28        getline(cin,sa,'\n');
 29        na=sa;
 30        int l=0;
 31        while(sa[l]!=':') l++;
 32       
 33        na.erase(l,sa.size()-l);
 34        sa.erase(0,l+2);
 35       
 36        for(int j=1;j<=n;++j)
 37        if(a[j].name==na)
 38        { 
 39          a[j].n++;
 40          a[j].say[a[j].n]=sa;
 41          break;
 42                }
 43              }
 44      }
 45 
 46 
 47 
 48 int check(){
 49     string day="0";
 50     for(int i=1;i<=n;++i)
 51     {
 52       if(real[i])
 53       {
 54         for(int j=1;j<=a[i].n;++j)
 55         {
 56           string say=a[i].say[j];
 57           
 58           if(say.size()<11) continue;
 59           
 60           if(say==tool[0]&&guilty!=i) return 0;
 61           if(say==tool[1]&&guilty==i) return 0;
 62           if(say==tool[0]||say==tool[1]) continue;
 63           
 64           string s=say;
 65           
 66           int k=say.size()-1,l=tool[2].size()-1;
 67           while(say[k]==tool[2][l]&&l>=0) {--k;--l;}
 68           if(l<0)
 69           {
 70             s.erase(k,s.size()-k);
 71             if(s!=a[guilty].name) return 0;
 72                  }
 73 
 74           k=say.size()-1,l=tool[3].size()-1;
 75           while(say[k]==tool[3][l]&&l>=0) {--k;--l;}
 76           if(l<0)
 77           {
 78             s.erase(k,s.size()-k);
 79             if(s==a[guilty].name) return 0;
 80                  }
 81           
 82           s=say;
 83           
 84           s.erase(8,s.size()-8);
 85           if(s==tool[4])
 86           {
 87             say.erase(0,9);
 88             if(day!="0"&&day!=say) return 0;
 89             day=say;    
 90                         }
 91                 }
 92                  }
 93 
 94       else if(!real[i])
 95       {
 96         for(int j=1;j<=a[i].n;++j)
 97         {
 98           string say=a[i].say[j];
 99           
100           if(say.size()<11) continue;
101           
102           if(say==tool[0]&&guilty==i) return 0;
103           if(say==tool[1]&&guilty!=i) return 0;
104           if(say==tool[0]||say==tool[1]) continue;
105           
106           string s=say;
107           
108           int k=say.size()-1,l=tool[2].size()-1;
109           while(say[k]==tool[2][l]&&l>=0) {--k;--l;}
110           if(l<0)
111           {
112             s.erase(k,s.size()-k);
113             if(s==a[guilty].name) return 0;
114                  }
115 
116           k=say.size()-1,l=tool[3].size()-1;
117           while(say[k]==tool[3][l]&&l>=0) {--k;--l;}
118           if(l<0)
119           {
120             s.erase(k,s.size()-k);
121             if(s!=a[guilty].name) return 0;
122                  }
123                  
124           s=say;
125           
126           s.erase(8,s.size()-8);
127           if(s==tool[4])
128           {
129             say.erase(0,9);
130             if(day==say) return 0; 
131                         }
132                 }
133           
134                 }
135             }
136     return 1;
137     }
138 
139 
140 int Dfs(int d,int tot){
141     if(d>n||tot>m||n-d<m-tot) return 0;
142     if(tot==m&&d==n) 
143     {
144       if(check())
145       return 1;
146       return 0;      
147                      }
148     
149     if(Dfs(d+1,tot)) return 1;
150     
151     real[d+1]=1;
152     if(Dfs(d+1,tot+1)) return 1;
153     real[d+1]=0;
154     return 0;
155     
156     }
157 
158 int main()
159 {
160     Init();
161     
162     int ans=0,sum=0;
163     for(int i=1;i<=n;++i)
164     {
165       guilty=i;
166       if(Dfs(0,0))
167       {sum++;ans=i;}
168             }
169     if(sum==0) {cout<<"Impossible"<<endl;return 0;}
170     if(sum>=2) {cout<<"Cannot Determine"<<endl;return 0;}
171     cout<<a[ans].name<<endl;return 0;
172     }