P1039 [NOIP2003 提高组] 侦探推理

小h这不是小学的经典题目吗？

小h然而，计算机不能像人一样各种判断：谁和谁的话存在矛盾……

小h但是，计算机算力强大，不会出错，因此可以暴力枚举guilty和日期是什么，然后进行判断是否合法。如果多个guilty都合法，就无法判断；一个的话就是他了；都不合法或者某人的话语自相矛盾，则输出不可能。注意大小写敏感，注意名字可能是I，另外如果某人没有有效发言，那么他既可以诚实又可能撒谎。

小h至于处理输入，我是全部用的getline，第一行就转字符串然后用sscanf提取数字。sscanf是用来从字符串而非stdin来输入的。

小h处理的话，对于每一行证词，去掉冒号、换行和回车，然后按照空格分成几部分，进行判断，并且用自己喜欢的方式修改一下格式即可。

小h本来吧，我是可以一次通过的。可是评测机的编译器居然认为getline会输入行尾回车，导致我调试了一下午。所以整行读入的时候一定谨慎。

小h另外，今天上午做了一道题，他说n小于1000，我吓一跳，以为会tle，一直不敢提交。后来发现最大的数据才500。所以比赛时一定先暴力骗分，数组在不mle的情况下开大，万一就过了呢？

正解#include<bits/stdc++.h> defineN 102 using namespace std; struct WORD{ int flag; string person; void fuzhi(int x,string y){ flag=x; person=y; } }; vector<string> v; void splitStr(string x){ v.clear(); string s1; int i=0; while(i<x.length()){ s1=""; while(i<x.size() && x[i]!=' ' && x[i]!=':' && x[i]!='\n' && x[i]!='\r') s1+=x[i++]; v.push_back(s1); while(i<x.size() && (x[i]==' ' || x[i]==':' || x[i]=='\n' || x[i]=='\r')) i++; } } const string I("I"),am("am"),guilty("guilty."),is("is"),bushi("not"),Today("Today"), mon("Monday."),tue("Tuesday."),wed("Wednesday."),thu("Thursday."), fri("Friday."),sat("Saturday."),Sun("Sunday."); const string riqi[7]={mon,tue,wed,thu,fri,sat,Sun}; string line1,speaker,ans,name[N],words[N]; map<string,int> mp; WORD zhengci[N][N]; int n,m,p,ansnum,lenz[N]; bool check(string x,string date){ int huang=0,shi=0,i=1,j,zhen,jia; for(;i<=n;i++){ if(!lenz[i]) continue; zhen=0; jia=0; for(j=0;j<lenz[i];j++){ if(zhengci[i][j].flag==-1){ if(zhengci[i][j].person==date) zhen++; else jia++; } if(zhengci[i][j].flag==0){ if(zhengci[i][j].person!=x) zhen++; else jia++; } if(zhengci[i][j].flag==1){ if(zhengci[i][j].person==x) zhen++; else jia++; } } if(zhen && jia) return false; if(zhen) shi++; else huang++; } if(huang>m || shi>n-m) return false; return true; } int main(){ getline(cin,line1); sscanf(line1.c_str(),"%d%d%d",&n,&m,&p); int i,j,k; for(i=1;i<=n;i++){ getline(cin,name[i]); name[i].erase(name[i].end()-1); mp[name[i]]=i; } for(i=1;i<=p;i++) getline(cin,words[i]); for(i=1;i<=p;i++){ splitStr(words[i]); speaker=v[0]; j=mp[speaker]; if(v.size()==5){ if(v[1]==I && v[2]==am && v[3]==bushi && v[4]==guilty) zhengci[j][lenz[j]++].fuzhi(0,speaker); if(v[2]==is && v[3]==bushi && v[4]==guilty && mp.find(v[1])!=mp.end()) zhengci[j][lenz[j]++].fuzhi(0,v[1]); } else if(v.size()==4){ if(v[1]==I && v[2]==am && v[3]==guilty) zhengci[j][lenz[j]++].fuzhi(1,speaker); if(v[2]==is && v[3]==guilty && mp.find(v[1])!=mp.end()) zhengci[j][lenz[j]++].fuzhi(1,v[1]); if(v[1]==Today && v[2]==is && (v[3]==mon || v[3]==tue || v[3]==wed || v[3]==thu || v[3]==fri || v[3]==sat || v[3]==Sun)) zhengci[j][lenz[j]++].fuzhi(-1,v[3]); } } for(i=1;i<=n;i++){ k=0; for(j=0;j<7;j++) if(check(name[i],riqi[j])) k=1; ansnum+=k; if(k) ans=name[i]; } if(ansnum) printf("%s\n",ansnum==1 ? ans.c_str() : "Cannot Determine"); else puts("Impossible"); return 0; }

小h

小h这道题的样例10好奇怪啊。