题解 [email protected]洛谷 | [email protected] 【Suspects】

nn 个人中有 11 个罪犯,每个人说一句话,说第 ii 个人是/不是罪犯,其中有 mm 句真话,要判断这些话的真假。

思路:

首先假设所有人都不是罪犯,统计出真话条数,然后枚举每一个人,在这个真话条数的基础上加上这个人是罪犯时对答案的贡献,如果刚好有 mm 句真话,标记有嫌疑,最后判断即可。

但是这个贡献怎么求呢?

很简单,如果所有人都不是罪犯,则真话条数就是 ai<0a_i\lt 0 的数量;当 xx 是罪犯时,减去 ai=xa_i=-x 的数量,加上 ai=xa_i=x 的数量,即为最新的贡献,这里在读入时也处理出来。

最后话的真假的判断方式也很简单:

如果 ii 指控一个人是罪犯:经过如上处理,发现他不可能是罪犯,则为假话;如果他可能是罪犯且嫌疑人数为 11,则为真话;否则不确定。说一个人不是罪犯的情况类似,不展开细说,可以参考代码。


代码:

//By: [email protected]_er(122461)
#include <bits/stdc++.h>
#define loop while(true)
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define fil(x,y) memset(x, y, sizeof(x))
#define mulT0 int T; for(scanf("%d", &T);T;T--)
#define mulT1 int T, rnds; for(scanf("%d", &T),rnds=1;rnds<=T;rnds++)
using namespace std;
typedef long long ll;
const int N = 1e5+5;

int n, m, a[N], contribution[N], suspect[N], tot, s;

int main() {
	scanf("%d%d", &n, &m);
	rep(i, 1, n) {
		scanf("%d", &a[i]);
		if(a[i] > 0) ++contribution[a[i]];
		else --contribution[-a[i]], ++s;
	}
	rep(i, 1, n) if(s + contribution[i] == m) suspect[i] = 1, ++tot;
	rep(i, 1, n) {
		if(a[i] > 0) {
			if(!suspect[a[i]]) puts("Lie");
			else if(tot == 1) puts("Truth");
			else puts("Not defined");
		}
		else {
			if(!suspect[-a[i]]) puts("Truth");
			else if(tot == 1) puts("Lie");
			else puts("Not defined");
		}
	}
	return 0;
}