Codeforces 156B. Suspects

Codeforces 156B. Suspects

題目大意：

福爾摩斯正在處理一件案子。此時已經抓捕了n個嫌疑人，裡面只可能有一個是真正的犯人。福爾摩斯正在審問這些嫌疑人。每個嫌疑人的回答只有兩種，一種表明他說編號為i的嫌疑人不是犯人，用-i表示；另一種表明他說編號為i的嫌疑人是犯人，用+i表示。聰明的福爾摩斯已經知道了其中有m個人說的是真話。要求那些人說的是真話，那些人說的是假話。

做法：

這的確是個很有意思的題啊。但是放在這裡的話，我們就不能還想以前一樣，只用嚴謹的邏輯推理去得出答案（或者有大牛真的能這樣。。。），我們利用計算機的話，就可以暴力的去判斷哪些人說的一定是真話，假話，或者不確定。 很簡單，我們假設第i號嫌疑人是犯人，那麼我們掃描一遍所有嫌疑人說的話，就可以知道mi個人說了真話，如果mi恰好等於m，那麼將i號嫌疑犯記錄到ans數組（記錄可能為犯人的人的數組）中。當i從0到n掃完之後，如果ans數組裡面只有一個元素，那麼說明記錄的這個嫌疑犯就是真正的犯人，那麼就能確定哪些人說的是真話，哪些人說的是假話。 如果ans數組裡面有很多元素，那麼也能確定哪些人說的一定是真話，哪些人說的是假話，哪些人說的話是不確定的。
這樣看來，我們的復雜度是O（n^2）咯？這不超時了嗎？。。。難道要重新想方法？。。 其實不用，上文中描紅加粗的部分其實不用每次都掃一遍數組，我們可以再輸出的時候，維護一個a[i](代表說i是犯人的有多少人),一個b[i](代表說i不是犯人的有多少人)就行，那麼前面說的mi就可以這樣計算：mi=a[i]+bn-b[i], 其中bn為說某人不是犯人的人的總數。這樣的話，上述遍歷的過程就可以變為O(1)時間完成，那這樣就可以過啦~
代碼：

#include 
#include 
#define N 100010
using namespace std;
int a[N],b[N],ans[N],say[N],numa,numb,numans;
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i0) numa++,a[say[i]]++;
        else numb++,b[-say[i]]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]+numb-b[i]==m) ans[i]=1,numans++;
    }
    for(int i=0;i0 && !ans[say[i]]) cout<<"Lie"<0 && ans[say[i]] && numans==1) cout<<"Truth"<0 && ans[say[i]]) cout<<"Not defined"<







縮減版：
#include 
const int N=100010;
int n,m,a[N],b[N],as[N],s[N],nb,nans;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i0) a[s[i]]++;
        else nb++,b[-s[i]]++;
    for(int i=1;i<=n;i++)if(a[i]+nb-b[i]==m) as[i]=1,nans++;
    nans=nans==1?1:0;
    for(int i=0;i0) puts(!as[s[i]]?"Lie":nans?"Truth":"Not defined");
        else puts(!as[-s[i]]?"Truth":nans?"Lie":"Not defined");
}