题目链接：点击查看
题目大意：给出n和m，代表有n个人，每个人说一句话，指认一个人是无辜还是罪犯，总共有m个人说了真话，问每个人说话的真实性
题目分析：一拿到这个题目我是懵逼的。。因为n给到了1e5，肯定没法暴力跑，而且如果用算法至多也只能用到n*logn的时间复杂度，真的是束手无策，想了有一会之后去看了一眼题解，发现这就是个简单的模拟题，用n的时间开销模拟出谁是犯罪嫌疑人，然后再用n跑一遍就能确定每个人说话的真假性了，一共是n+n的时间复杂度，原来只是一个简单模拟。。我给想复杂了，不过这个题目判断谁是犯罪嫌疑人也是有技巧的，不是那么明摆着让判断。
首先我们可以知道每个人被指控了多少次，也就是被多少人指控为罪犯，我们用数组a记录，也能知道每个人被洗白了多少次，也就是被多少人证明为无辜，我们用数组b记录，这样一来我们可以顺便记录一下一共有多少个人为其他人证明无辜，我们用变量cnt记录，如果当前我们遍历到了第i个人，如果这个人是嫌疑犯，那么a[i]个指控他为罪犯的人说了真话，b[i]个证明他是无辜的人说了假话，相对应的，cnt-b[i]个证明其他人是无辜的人说了真话，那么到此为止说真话的人一共就是a[i]+cnt-b[i]，用这个值和m判断一下就能知道当前这个人是不是犯罪嫌疑人了，我们先用n把所有的犯罪嫌疑人跑出来，因为题目中也说了犯罪嫌疑人至少有一个
接下来就是判断每个人说话的真假性了，如果犯罪嫌疑人只有一个人的话，那么很简单了，每个人说的话不是真话就是假话，这里不多赘述了，按照要求模拟即可
然后就是如果犯罪嫌疑人有多个的话该怎么办，假如一个人的论述中包括了其中任意一个犯罪嫌疑人，那么都输出不确定，因为我们也不知道哪个犯罪嫌疑人是真的罪犯，相反，如果一个人的论述中没有包括犯罪嫌疑人，那么不是真话就是假话，根据规则模拟就行
这个题目本来我觉得有点离散化的意思，想用无序map辅助维护一下vis数组，但是稍微仔细的读了一下题目后发现其实开一个1e5的数组就够用了，而且用数组的话肯定比stl要快，也不差那点空间了，浪费就浪费了吧。。空间换时间？（误。。）
直接上代码了，第一次见这种模拟题，也算是挺好玩的：
#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;//记录说没犯罪的人的人数 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"); else printf("Lie\n"); } else { if(x[i]<0) printf("Truth\n"); else printf("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"); else printf("Truth\n"); } } } } return 0; }
