NOIP 2003 侦探处理（字符串大模拟） HQG_AC的博客

$luogu 1039$

一看题面就是大模拟。。最讨厌这样的题了。搞了1天AC了

脑抽没用$string$。。$char$ $a[]$ 真的麻烦啊

还有，题面有不少坑点没跟你说，我真

想告了出题者。。

好了好了，不吐槽了，说正事

题解：

1.读入，说话者的姓名后多一个空格，把他改成’\0’ （坑点1）

2.输入每一句话，取出说话者的名字 ##（注意这个名字很奇怪，有叫 $GUILTY$ 的，还有 $SUNDAY$ 的,判断要判断好）

3，判断说话者的内容

构造了10种可能的说话内容，分别是

    "Today is Monday.",    //0"Today is Tuesday.",   //1"Today is Wednesday.", //2"Today is Thursday.",  //3"Today is Friday.",    //4"Today is Saturday.",  //5 "Today is Sunday.",    //6"I am guilty.",        //7"I am not guilty.",    //8"is guilty.",          //9"is not guilty.",      //10

前8种可以直接判断是否相等，后两种需要取出人名再判断是否相等

4.对于每个人，$vec[i]$表示他说的话的集合，$pair <int,int>$ 存储

对于每句话$j$

1）$0<=vec[i][j].first<=8,$则是前8种，$vec[i][j].first$表示他是第几种

2）$9<=vec[i][j].first<=10$,则是后两种，$vec[i][j].second$存储它说明的对象

前面都是读入和预处理！！！

之后才是正事！！

在看完题目之后，不少$OIer$肯定有一个疑问：这个星期有什么用呢？

你会发现，星期可以判断该人有没有说谎话！！（坑点2）

于是，我们既要枚举罪犯是谁，还要枚举星期几。

对于每个罪犯，如果判断星期i是可行的，应跳出循环，

因为可能其他的星期也是对的，这样会报 $Cannot$ $Determine$（坑点3）

我们用$judge(d,x)$表示对于星期为$d$，罪犯为$x$的情况是否可行。

$judge$也是坑洞无数…

1.如果有些人没说话或说的都是废话，该怎么处理呢？（是判他是说谎还是不说谎？）

结论证明要么都判说谎，要么都不判。（坑点4）

2.如果一个人先说了谎，那他后面都必须说谎！（坑点5）

之后就没有难度了。。（~^…………^~）

还有一些烦人的细节，总之是一道好题。

之后有几组烦人的数据给大家提供一下：

1.
input

2 2 4
HELLO
GUILTY
HELLO: What is your name?
GUILTY: I am GUILTY.
GUILTY: Are you guilty?
HELLO: I am not guilty.

output

HELLO

2

input

5 1 5
A
B
C
D
E
A: Today is Monday.
B: Today is Thursday.
C: Today is Monday.
B: D is not guilty.
E: I am not guilty.

output

D

3.

input

7 3 10
MONDAY
TUESDAY
WEDNESDAY
THURSDAY
FRIDAY
SATURDAY
SUNDAY
MONDAY: Today is Monday.
TUESDAY: Today is Tuesday.
WEDNESDAY: Today is Wednesday.
THURSDAY: Today is Thursday.
FRIDAY: MONDAY is not guilty.
FRIDAY: TUESDAY is not guilty.
FRIDAY: WEDNESDAY is not guilty.
FRIDAY: THURSDAY is not guilty.
SATURDAY: SUNDAY is not guilty.
SUNDAY: SATURDAY is not guilty.

output

FRIDAY

代码（请大佬勿喷，自己都觉得挫）

#include 
using namespace std ;
const int M = 20 ;
const int P = 100 ;
const int L = 300 ;
char Says[30][300]=
{ //一共11中说话类型 "Today is Monday.",    //0"Today is Tuesday.",   //1"Today is Wednesday.", //2"Today is Thursday.",  //3"Today is Friday.",    //4"Today is Saturday.",  //5 "Today is Sunday.",    //6"I am guilty.",        //7"I am not guilty.",    //8"is guilty.",          //9"is not guilty.",      //10
} ;
char talk[P],name[M][L],who[P][L],guilty[P][L],sayswhat[P][L] ;
bool liar[M] ;
vectorint,int> > vec[M] ;
int m,n,p ;
bool same(char a[],char b[]) { //判断两个字符串是否相同 if (strlen(a)!=strlen(b)) return false ;for (int i=0;i<strlen(a);i++) if (a[i]!=b[i]) return false ;return true;    
}
int search(char s[],char b){for (int i=0;i<strlen(s);i++) if (s[i]==b) return i ;
}
bool lie(int i,int j,int d,int x){if (vec[i][j].first>=0 && vec[i][j].first<=6){if (vec[i][j].first!=d) return true ;}else if (vec[i][j].first==7){if (i!=x) return true  ;}else if (vec[i][j].first==8){if (i==x) return true ;}else if (vec[i][j].first==9){if (vec[i][j].second!=x) return true  ;}else if (vec[i][j].first==10){if (vec[i][j].second==x) return true ;}return false ;
}
bool judge(int d,int x){int nosay=0 ;memset(liar,false,sizeof(liar)) ;//所有人都不是liar  for (int i=1;i<=m;i++){if (vec[i].empty()) nosay++ ; else{liar[i]=lie(i,0,d,x) ;for (int j=1;jbool bf=lie(i,j,d,x);if (bf!=liar[i]) return false ;liar[i]=bf ;}} }int liesum=0;for (int i=1;i<=m;i++) if (liar[i]) liesum++ ;if (liesum+nosay==n || liesum==n) return true ;else return false ;
}
int main(){scanf("%d%d%d\n",&m,&n,&p) ;for (int i=1;i<=m;i++) {gets(name[i]);//他的名字 name[i][strlen(name[i])-1]='\0' ;}for (int i=1;i<=p;i++){int id ;gets(talk) ;talk[strlen(talk)-1]='\0' ;int pos;pos=search(talk,':') ;//先查询，每个人的名字 strncpy(who[i],talk,pos) ;for (int j=1;j<=m;j++) //说话者的编号 if (same(who[i],name[j])){ id=j ;break ;}strncpy(sayswhat[i],talk+pos+2,strlen(talk)) ;int f=false ;for (int j=0;j<=8;j++){ //他说的话的种类 if (same(sayswhat[i],Says[j])){if (j>=0 && j<=6) vec[id].push_back(make_pair(j,0)) ;//星期 else if (j==7 || j==8) vec[id].push_back(make_pair(j,0)) ;//我的信息 f=true ;break ;}}if (!f)for (int j=9;j<=10;j++){char *pos ;pos=strstr(sayswhat[i],Says[j]) ;if (pos!=NULL){strncpy(guilty[i],sayswhat[i],pos-sayswhat[i]-1) ;int ID ;for (int k=1;k<=m;k++) //说话者的编号 if (same(guilty[i],name[k])){ ID=k ;break ;}vec[id].push_back(make_pair(j,ID)) ;//别人的信息 }}}int ans=-1 ;for (int j=1;j<=m;j++){bool f=false;for (int i=0;i<=6;i++){bool ok=judge(i,j) ;if (ok){if (ans==-1 && !f) {ans=j ;f=true; break;}else if (ans!=-1) {printf("Cannot Determine\n") ;return 0 ;}}}}if (ans==-1) printf("Impossible\n") ;else printf("%s\n",name[ans]) ;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！