【Luogu1039】侦探推理

Source and Judge

NOIP2003 提高组 T2
Luogu1039
Caioj1513

Problem

【Brief description】
明明的同学们先商量好由其中的一个人充当罪犯(在明明不知情的情况下),
明明的任务就是找出这个罪犯。
接着,明明逐个询问每一个同学,被询问者可能会说:

证词中出现的其他话,都不列入逻辑推理的内容。
明明所知道的是,他的同学中有N个人始终说假话,其余的人始终说真。
现在,明明需要你帮助他从他同学的话中推断出谁是真正的凶手,请记住,凶手只有一个!
【Input】
输入由若干行组成,第一行有三个整数,M、N和P;
M是参加游戏的明明的同学数,N是其中始终说谎的人数,P是证言的总数。

接下来M行,每行是明明的一个同学的名字(英文字母组成,没有空格,全部大写)。

往后有P行,每行开始是某个同学的名宇,紧跟着一个冒号和一个空格,
后面是一句证词,符合前表中所列格式。证词每行不会超过250个字符。

输入中不会出现连续的两个空格,而且每行开头和结尾也没有空格。
【Output】
如果你的程序能确定谁是罪犯,则输出他的名字;
如果程序判断出不止一个人可能是罪犯,则输出 Cannot Determine;
如果程序判断出没有人可能成为罪犯,则输出 Impossible。
【Limited conditions】
1≤M≤20
1≤N≤M
1≤P≤100
【Sample input】
3 1 5
MIKE
CHARLES
KATE
MIKE: I am guilty.
MIKE: Today is Sunday.
CHARLES: MIKE is guilty.
KATE: I am guilty.
KATE: How are you??
【Sample output】
MIKE
【Sample explanation】

Record

30min

Analysis

请先思考后再展开

真有意思的题面嘿嘿
然后又去看了看数据
没有极限数据是意料之中【取而代之的是恶心数据,不知道满分的都是什么人……】的了,但居然还有这个hh
I love you!
If there must be a deadline,
I hope it is 10000 years!!!
然后他的名字是拼音,翻译过来就是:
曾经有一段真挚的感情。芳,在我面前,我没有珍惜。等到失去了以后,才追悔莫及。人世间最痛苦的事莫过于此。如果上天能给我一个再来一次的机会,我会对那个女孩子说三个字

好了讲正事,暴力枚举判断可行性即可
就是这个输入麻烦……
大小写敏感
测试点#2:有一位同志,既承认自己有罪,又承认自己无罪。
【然后答案居然是Impossible,辣鸡题面没说清】
测试点#9:“I is not guilty.”,I是人名

woc,这道题大家别写了……虽然我已经把代码尽量精炼,依然是毒瘤题,特别是输入
对了,理论上判断废话的时候,前面和后面可能会有废话,而中间重要,
但没有这种数据就不打了,太恶心了这种题……

UP:
弃坑了
可能以后也不会填了
贴一个别人的代码吧哎【灰常优质】

Code

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
map<string,int> name;
string s,ss;
string names[25];
string testimony[25][105];
int num[25];
int n,m,p;
bool crap(string tmp)
{
if(tmp==" I am guilty.") return 0;
if(tmp==" I am not guilty.") return 0;
if(tmp==" Today is Monday.") return 0;
if(tmp==" Today is Tuesday.") return 0;
if(tmp==" Today is Wednesday.") return 0;
if(tmp==" Today is Thursday.") return 0;
if(tmp==" Today is Friday.") return 0;
if(tmp==" Today is Saturday.") return 0;
if(tmp==" Today is Sunday.") return 0;
for(int i=1;i<=m;i++)
if(tmp==" "+names[i]+" is guilty."||tmp==" "+names[i]+" is not guilty.") return 0;
return 1;
}
bool judge(int guilty,int day)
{
int ans;
for(int i=1;i<=m;i++)
{
ans=0;
for(int j=1;j<=num[i];j++)
{
if(testimony[i][j]==" I am guilty."&&guilty!=i) {ans++;}
if(testimony[i][j]==" I am not guilty."&&guilty==i) {ans++;}
if(testimony[i][j]==" Today is Monday."&&day!=1) {ans++;}
if(testimony[i][j]==" Today is Tuesday."&&day!=2) {ans++;}
if(testimony[i][j]==" Today is Wednesday."&&day!=3) {ans++;}
if(testimony[i][j]==" Today is Thursday."&&day!=4) {ans++;}
if(testimony[i][j]==" Today is Friday."&&day!=5) {ans++;}
if(testimony[i][j]==" Today is Saturday."&&day!=6) {ans++;}
if(testimony[i][j]==" Today is Sunday."&&day!=7) {ans++;}
for(int k=1;k<=m;k++)
{
if(testimony[i][j]==" "+names[k]+" is guilty."&&guilty!=k) {ans++;}
if(testimony[i][j]==" "+names[k]+" is not guilty."&&guilty==k) {ans++;}
}
}
if(ans!=num[i]&&ans!=0) return 0;
}
return 1;
}
int check(int guilty,int day)
{
int ans=0;
bool twice;
for(int i=1;i<=m;i++)
for(int j=1;j<=num[i];j++)
{
twice=0;
if(testimony[i][j]==" I am guilty."&&guilty!=i) {ans++;break;}
if(testimony[i][j]==" I am not guilty."&&guilty==i) {ans++;break;}
if(testimony[i][j]==" Today is Monday."&&day!=1) {ans++;break;}
if(testimony[i][j]==" Today is Tuesday."&&day!=2) {ans++;break;}
if(testimony[i][j]==" Today is Wednesday."&&day!=3) {ans++;break;}
if(testimony[i][j]==" Today is Thursday."&&day!=4) {ans++;break;}
if(testimony[i][j]==" Today is Friday."&&day!=5) {ans++;break;}
if(testimony[i][j]==" Today is Saturday."&&day!=6) {ans++;break;}
if(testimony[i][j]==" Today is Sunday."&&day!=7) {ans++;break;}
for(int k=1;k<=m;k++)
{
if(testimony[i][j]==" "+names[k]+" is guilty."&&guilty!=k) {ans++;twice=1;break;}
if(testimony[i][j]==" "+names[k]+" is not guilty."&&guilty==k) {ans++;twice=1;break;}
}
if(twice==1) break;
}
if(ans!=n)
for(int i=1;i<=m;i++)
{
if(num[i]==0) ans++;
if(ans==n) break;
}
return ans;
}
int read()
{
char c=getchar();
int ans=0;
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9')
{
ans=ans*10+c-48;
c=getchar();
}
return ans;
}
string gl()
{
string sss,c;
do
{
cin>>c;
sss=sss+" "+c;
}
while(c[c.size()-1]!='.'&&c[c.size()-1]!='?'&&c[c.size()-1]!='!'&&c[c.size()-1]!=',');
return sss;
}
int main()
{
m=read();n=read();p=read();
for(int i=1;i<=m;i++)
{
cin>>s;
name[s]=i;
names[i]=s;
}
for(int i=1;i<=p;i++)
{
cin>>s;
s=s.substr(0,s.size()-1);
ss=gl();
if(crap(ss)) continue;
num[name[s]]++;
testimony[name[s]][num[name[s]]]=ss;
}
int flag=0;
for(int i=1;i<=m;i++)
for(int j=1;j<=7;j++)
if(check(i,j)==n&&judge(i,j))
{
if(flag!=0)
{
cout<<"Cannot Determine"<<endl;
return 0;
}
else
{
flag=i;
break;
}
}
if(flag==0) cout<<"Impossible"<<endl; else cout<<names[flag]<<endl;
return 0;
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/9061.html
转载请注明出处,谢谢!