Codeforces 156B Suspects——————【逻辑判断】
Description
As Sherlock Holmes was investigating a crime, he identified n suspects. He knows for sure that exactly one of them committed the crime. To find out which one did it, the detective lines up the suspects and numbered them from 1 to n. After that, he asked each one: "Which one committed the crime?". Suspect number i answered either "The crime was committed by suspect number ai", or "Suspect number ai didn't commit the crime". Also, the suspect could say so about himself (ai = i).
Sherlock Holmes understood for sure that exactly m answers were the truth and all other answers were a lie. Now help him understand this: which suspect lied and which one told the truth?
Input
The first line contains two integers n and m (1 ≤ n ≤ 105, 0 ≤ m ≤ n) — the total number of suspects and the number of suspects who told the truth. Next n lines contain the suspects' answers. The i-th line contains either "+ai" (without the quotes), if the suspect number isays that the crime was committed by suspect number ai, or "-ai" (without the quotes), if the suspect number i says that the suspect number ai didn't commit the crime (ai is an integer, 1 ≤ ai ≤ n).
It is guaranteed that at least one suspect exists, such that if he committed the crime, then exactly m people told the truth.
Output
Print n lines. Line number i should contain "Truth" if suspect number i has told the truth for sure. Print "Lie" if the suspect number i lied for sure and print "Not defined" if he could lie and could tell the truth, too, depending on who committed the crime.
Sample Input
1 1
+1
Truth
3 2
-1
-2
-3
Not defined
Not defined
Not defined
4 1
+2
-3
+4
-1
Lie
Not defined
Lie
Not defined
Hint
The first sample has the single person and he confesses to the crime, and Sherlock Holmes knows that one person is telling the truth. That means that this person is telling the truth.
In the second sample there are three suspects and each one denies his guilt. Sherlock Holmes knows that only two of them are telling the truth. Any one of them can be the criminal, so we don't know for any of them, whether this person is telling the truth or not.
In the third sample the second and the fourth suspect defend the first and the third one. But only one is telling the truth, thus, the first or the third one is the criminal. Both of them can be criminals, so the second and the fourth one can either be lying or telling the truth. The first and the third one are lying for sure as they are blaming the second and the fourth one.
题目大意:给你n表示嫌疑人说的话,+c[i]表示第i个人说c[i]是犯人,-c[i]表示第i个人说c[i]不是犯人。m表示这n个人中有m个人说真话。现在让你判断每个人说的是真话还是假话,或者不确定。
解题思路:如果我们假设第i个人是犯人,那么我们通过O(n)的复杂度可以得出说真话的人的个数mi,那么如果mi==m,那么把这个人放入犯人数组。最后如果犯人数组中只有一个犯人,那么我们可以准确判断每个人说话的真假性。如果犯人数组中人数很多,那么如果c[i] > 0,且c[i]在犯人数组中,那么不确定,如果c[i]不在犯人数组中,那么这个人必然说假话;如果c[i]<0,且|c[i]|这个人在犯人数组中,那么也是不确定,如果|c[i]|不在犯人数组中,那么这个人必然说真话。 现在问题是如果每次用O(n)得出mi,那么复杂度将是O(n^2)。我们可以首先统计出总的说别人不是犯人的个数nosupn,以及说i是犯人的人数issuspect[i]和说i不是犯人的人数nosuspect[i],那么mi = issuspect[i] + nosupn - nosuspect[i]。 这复杂度为O(1)。
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<string>
#include<iostream>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<set>
using namespace std;
typedef long long LL;
#define mid (L+R)/2
#define lson rt*2,L,mid
#define rson rt*2+1,mid+1,R
#pragma comment(linker, "/STACK:102400000,102400000")
const int maxn = 1e5 + 300;
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef unsigned long long ULL;
int a[maxn];
int issuspect[maxn], nosuspect[maxn];
int iscrimer[maxn], crimer[maxn];
int main(){
int n, m;
while(scanf("%d%d",&n,&m)!=EOF){
int nosupn = 0;
for(int i = 1; i <= n; i++){
scanf("%d",&a[i]);
if(a[i] > 0){
issuspect[a[i]]++;
}else{
nosuspect[-a[i]]++;
nosupn++;
}
}
int saytrue = 0;
int cn = 0;
for(int i = 1; i <= n; i++){
saytrue = issuspect[i] + nosupn - nosuspect[i];
if(saytrue == m){
crimer[cn] = i; cn++;
iscrimer[i] = 1;
}
}
if(cn == 1){
for(int i = 1; i <= n; i++){
if(a[i] > 0){
if(iscrimer[a[i]]){
puts("Truth");
}else{
puts("Lie");
}
}else{
if(iscrimer[-a[i]]){
puts("Lie");
}else{
puts("Truth");
}
}
}
}else{
for(int i = 1; i <= n; i++){
if(a[i] > 0){
if(iscrimer[a[i]]){
puts("Not defined");
}else{
puts("Lie");
}
}else{
if(iscrimer[-a[i]]){
puts("Not defined");
}else{
puts("Truth");
}
}
}
}
}
return 0;
}
最新文章
- Oracle连接与会话
- Android课程---关于数据存储的学习(2)
- 能不能用javascript实现素数求和问题呢?
- Codeforces Round #345 (Div. 2)
- HTTPS_SSL配置的步骤以及原理说明
- 每天一个命令day1【diff 命令】(具体实例看下一节)
- 【CITE】DrawImage方法详解(转)
- POJ 2724
- Sqlyog增加试用期
- 内存溢出System.OutOfMemoryException
- OC中Foundation框架之NSDictionary、NSMutableDictionary
- mysql主键约束和唯一性约束
- (NO.00004)iOS实现打砖块游戏(七):关卡类的实现
- Maximum Sum of Digits(CodeForces 1060B)
- 写给大忙人的spring cloud 1.x学习指南
- SpringBoot获取全局配置文件的属性以及@ConfigurationProperties实现类型安全的配置
- 数组方法splice
- python&#160;以单例模式封装logging相关api实现日志打印类
- 使用代码段遍历,枚举类型Enum
- python的面向对象-实例(对象)的相关知识、实例化