題目鏈接：點(diǎn)擊查看

題目大意：給出n和m，代表有n個(gè)人，每個(gè)人說一句話，指認(rèn)一個(gè)人是無辜還是罪犯，總共有m個(gè)人說了真話，問每個(gè)人說話的真實(shí)性

題目分析：一拿到這個(gè)題目我是懵逼的。。因?yàn)閚給到了1e5，肯定沒法暴力跑，而且如果用算法至多也只能用到n*logn的時(shí)間復(fù)雜度，真的是束手無策，想了有一會(huì)之后去看了一眼題解，發(fā)現(xiàn)這就是個(gè)簡單的模擬題，用n的時(shí)間開銷模擬出誰是犯罪嫌疑人，然后再用n跑一遍就能確定每個(gè)人說話的真假性了，一共是n+n的時(shí)間復(fù)雜度，原來只是一個(gè)簡單模擬。。我給想復(fù)雜了，不過這個(gè)題目判斷誰是犯罪嫌疑人也是有技巧的，不是那么明擺著讓判斷。

首先我們可以知道每個(gè)人被指控了多少次，也就是被多少人指控為罪犯，我們用數(shù)組a記錄，也能知道每個(gè)人被洗白了多少次，也就是被多少人證明為無辜，我們用數(shù)組b記錄，這樣一來我們可以順便記錄一下一共有多少個(gè)人為其他人證明無辜，我們用變量cnt記錄，如果當(dāng)前我們遍歷到了第i個(gè)人，如果這個(gè)人是嫌疑犯，那么a[i]個(gè)指控他為罪犯的人說了真話，b[i]個(gè)證明他是無辜的人說了假話，相對(duì)應(yīng)的，cnt-b[i]個(gè)證明其他人是無辜的人說了真話，那么到此為止說真話的人一共就是a[i]+cnt-b[i]，用這個(gè)值和m判斷一下就能知道當(dāng)前這個(gè)人是不是犯罪嫌疑人了，我們先用n把所有的犯罪嫌疑人跑出來，因?yàn)轭}目中也說了犯罪嫌疑人至少有一個(gè)

接下來就是判斷每個(gè)人說話的真假性了，如果犯罪嫌疑人只有一個(gè)人的話，那么很簡單了，每個(gè)人說的話不是真話就是假話，這里不多贅述了，按照要求模擬即可

然后就是如果犯罪嫌疑人有多個(gè)的話該怎么辦，假如一個(gè)人的論述中包括了其中任意一個(gè)犯罪嫌疑人，那么都輸出不確定，因?yàn)槲覀円膊恢滥膫€(gè)犯罪嫌疑人是真的罪犯，相反，如果一個(gè)人的論述中沒有包括犯罪嫌疑人，那么不是真話就是假話，根據(jù)規(guī)則模擬就行

這個(gè)題目本來我覺得有點(diǎn)離散化的意思，想用無序map輔助維護(hù)一下vis數(shù)組，但是稍微仔細(xì)的讀了一下題目后發(fā)現(xiàn)其實(shí)開一個(gè)1e5的數(shù)組就夠用了，而且用數(shù)組的話肯定比stl要快，也不差那點(diǎn)空間了，浪費(fèi)就浪費(fèi)了吧。。空間換時(shí)間？（誤。。）

直接上代碼了，第一次見這種模擬題，也算是挺好玩的：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int x[N];int a[N],b[N];bool vis[N];int main() { // freopen("input.txt","r",stdin);int w;cin>>w;while(w--){memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(vis,false,sizeof(vis));int n,m;int cnt=0;//記錄說沒犯罪的人的人數(shù) scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",x+i);if(x[i]>0){a[x[i]]++;}else{b[-x[i]]++;cnt++;}}vector<int>v;for(int i=1;i<=n;i++){if(a[i]+cnt-b[i]==m){v.push_back(i);vis[i]=true;}}if(v.size()==1){for(int i=1;i<=n;i++){if(abs(x[i])==v[0]){if(x[i]>0)printf("Truth\n");elseprintf("Lie\n");}else{if(x[i]<0)printf("Truth\n");elseprintf("Lie\n");}}}else{for(int i=1;i<=n;i++){if(vis[abs(x[i])]){printf("Not defined\n");}else{if(x[i]>0)printf("Lie\n");elseprintf("Truth\n");}}}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的FZU - 2202 犯罪嫌疑人(逻辑思维+简单模拟)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。