CF156B Suspects 【逻辑+】

50 阅读 0 评论 33 点赞

我是靠谱客的博主端庄毛巾，最近开发中收集的这篇文章主要介绍CF156B Suspects 【逻辑+】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

给出n个犯人的n条供述，并且知道有m条是真的

正数代表当前犯人供述该号犯人犯罪

负数代表当前犯人供述该号犯人没有犯罪

例如

+7代表当前犯人供述7号犯罪

-3代表当前犯人供述3号没有犯罪

来想想某人可能犯罪的条件

假设一个人犯罪

那么如果

说其他人犯罪的供述（暂时视作假话）条数+说他没有犯罪的供述（暂时视作假话）条数=n-m（假话条数）

这个式子成立的话

那么这个人就有可能犯罪（因为可能有多个人满足这个条件，而犯人只有一个）

否则

这个人不可能犯罪

那么对可能犯罪的人

如果不止一个

说他犯罪的属于not define

说他没犯罪的属于not define

如果只有一个

说他犯罪的属于true

说他没犯罪的属于lie

那么对不可能犯罪的人

说他犯罪的属于lie

说他没犯罪的属于true

#include <cstdio>
#include <climits>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int NN=1111111;
int tmp[NN];
int y[NN],nono[NN],maybe[NN];
int main(){
#ifndef ONLINE_JUDGE
	freopen("/home/rainto96/in.txt","r",stdin);
#endif
	int n,m;
	cin>>n>>m;
	int yes=0,no=0;
	for(int i=1;i<=n;i++){
		cin>>tmp[i];
		//vis[abs(tmp)]+=tmp/abs(tmp);
		if(tmp[i]>0) y[tmp[i]]++;
		else 	  nono[-tmp[i]]++;
		yes+=tmp[i]>0;
		no+=tmp[i]<0;
	}
	for(int i=1;i<=n;i++){
		maybe[i]=(yes-y[i]+nono[i]==n-m);
	}
	/*char statement[2][2][111]={{"Not defined","TRUETH"},{"Not defined","LIE"}};
	for(int i=1;i<=n;i++){
		if(tmp[i]>0){
			printf("%sn",statement[1][!maybe[tmp[i]]]);
		}else{
			printf("%sn",statement[0][maybe[-tmp[i]]]);
		}
	}*/
	int times=0;
	for(int i=1;i<=n;i++)   if(maybe[i]) times++;
	for(int i=1;i<=n;i++){
		if(tmp[i]>0){
			if(maybe[tmp[i]]){
                                if(times>1) cout<<"Not defined"<<endl;
                                else        cout<<"Truth"<<endl;
			}else         cout<<"Lie"<<endl;
		}else{
			if(maybe[-tmp[i]]){
                                if(times>1) cout<<"Not defined"<<endl;
                                else        cout<<"Lie"<<endl;
			}else         cout<<"Truth"<<endl;
		}
	}
	return 0;
}