vijos 1106 & NOIP2003 提高組 偵探推理 題解

【原題】

P1106偵探推理 Accepted 标簽： [顯示标簽]

描述

明明同學最近迷上了偵探漫畫《柯南》并沉醉于推理遊戲之中，于是他召集了一群同學玩推理遊戲。遊戲的内容是這樣的，明明的同學們先商量好由其中的一個人充當罪犯（在明明不知情的情況下），明明的任務就是找出這個罪犯。接着，明明逐個詢問每一個同學，被詢問者可能會說：

證詞中出現的其他話，都不列入邏輯推理的内容。

明明所知道的是，他的同學中有N個人始終說假話，其餘的人始終說真。

現在，明明需要你幫助他從他同學的話中推斷出誰是真正的兇手，請記住，兇手隻有一個！

格式

輸入格式

輸入由若幹行組成，第一行有二個整數，M（1≤M≤20）、N（1≤N≤M）和P（1≤P≤100）；M是參加遊戲的明明的同學數，N是其中始終說謊的人數，P是證言的總數。接下來M行，每行是明明的一個同學的名字（英文字母組成，沒有主格，全部大寫）。往後有P行，每行開始是某個同學的名宇，緊跟着一個冒号和一個空格，後面是一句證詞，符合前表中所列格式。證詞每行不會超過250個字元。

輸入中不會出現連續的兩個空格，而且每行開頭和結尾也沒有空格。

輸出格式

如果你的程式能确定誰是罪犯，則輸出他的名字；如果程式判斷出不止一個人可能是罪犯，則輸出 Cannot Determine；如果程式判斷出沒有人可能成為罪犯，則輸出 Impossible。

樣例1

樣例輸入1[複制]

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??      

樣例輸出1[複制]

MIKE      

限制

每個測試點1s

提示

有說一句話的末尾無空格的麼？..

來源

NOIP2003第二題

【分析】神題刷的太多了，感覺怪怪的。如果再沒有水題來調節，真的是渾身不爽！。然後就滾粗去VJ水了一道碼農題。感覺思路還是比較簡潔的，初步縮行後（這樣更美觀吧）才69行。人名可以用MAP來搞搞。

講一下思路。開始很傻×的認為去C(20，10)枚舉每個人是否講假話。這個的時間效率。。。後來發現，隻要枚舉了罪犯和今天是星期幾，很容易判斷每個人是否講假話，然後看看人數是否是給定的數目就行了。

讀入要注意一下。開始我被樣例坑了，以為冒号後面就沒有空格，覺得超麻煩：我如果把每句話的每個單詞都截取出來，第一個單詞還要分冒号~~交了後WA了，才在輸入格式裡發現有空格。。。不是更水嗎？

然後判斷5句話的話，我把1,2兩句和3,4兩句結合在了一起判斷，更省代碼和思維。

還有一個值得注意的地方就是：有些人可能不說真話也不說假話（就是說的是那種無關緊要的話），我們可以算作真話，也可以算作假話，主要是為了更靠近答案。

對了，對于名字的字元串要開的大一點。我記得最後一個點的名字有很長的一串，然後我就直接爆了。

【代碼】

#include<cstdio>
#include<cstring>
#include<map>
#include<string>
using namespace std;
map<string,int>Map;
char s[105][25][525],name[105][525],ans[105][525],a[25][525];
int num[105],f[25],n,m,i,j,k,P,Today,flag,now,lie,Len,cnt,T;
char day[8][25]={"","Monday.","Tuesday.","Wednesday.","Thursday.","Friday.","Saturday.","Sunday."};
inline int equal(char *s1,char *s2)
{
  int l1=strlen(s1),l2=strlen(s2);if (l1!=l2) return 0;
  for (int i=0;i<l1;i++) if (s1[i]!=s2[i]) return 0;return 1;
}
inline int check_1(int k)
{
  if (!equal(s[k][num[k]],"guilty.")||num[k]<3||num[k]>4) return 2;
  if (s[k][1][0]!='I'||s[k][1][1]!='\0'||!equal(s[k][2],"am")) return 2;
  if (num[k]==4) if (!equal(s[k][3],"not")) return 2;
  if (Map[name[k]]==now) {if (num[k]==3) return 0;return 1;}
  if (num[k]==3) return 1;return 0;
}
inline int check_2(int k)
{
  if (!equal(s[k][num[k]],"guilty.")||num[k]<3||num[k]>4) return 2;
  if (!equal(s[k][2],"is")) return 2;
  if (num[k]==4) if (!equal(s[k][3],"not")) return 2;
  if (Map[s[k][1]]==now) {if (num[k]==3) return 0;return 1;}
  if (num[k]==3) return 1;return 0;
}
inline int check_3(int k)
{
  if (num[k]!=3||!equal(s[k][1],"Today")||!equal(s[k][2],"is")) return 2;
  return equal(day[Today],s[k][3])^1;
}
inline int work()
{
  now=Map[a[P]];int res=0,another=0;memset(f,0,sizeof(f));
  for (int i=1;i<=m;i++)
  {
    int T1=check_1(i),T2=check_2(i),T3=check_3(i),pre=Map[name[i]];
    if (!T1||!T2||!T3) {if (f[pre]==2) return 0;f[pre]=1;}
    if (T1&1||T2&1||T3&1) {if (f[pre]==1) return 0;f[pre]=2;}
  }
  for (int i=1;i<=n;i++)
    if (f[i]==2) res++;else if (!f[i]) another++;
  return (res<=lie&&res+another>=lie);
}
inline int OK(char ch){return (ch>='A'&&ch<='Z'||ch>='a'&&ch<='z');}
int main()
{
  scanf("%d%d%d",&n,&lie,&m);
  for (i=1;i<=n;i++) scanf("%s",a[i]),Map[a[i]]=i;
  for (i=1;i<=m;i++) 
  {
    scanf("%s",name[i]);name[i][strlen(name[i])-1]='\0';
    scanf("%s",s[i][num[i]=1]);
    while (OK(s[i][num[i]][strlen(s[i][num[i]])-1])) scanf("%s",s[i][++num[i]]);
  }
  for (P=1;P<=n;P++)
  {
    flag=0;for (Today=1;Today<=7&&!flag;Today++) flag=work();
    if (flag) memcpy(ans[++cnt],a[P],sizeof(a[P]));
  }
  if (!cnt) printf("Impossible");
  else if (cnt==1) printf("%s",ans[cnt]);
  else printf("Cannot Determine");
  return 0;
}