[分类讨论]Bit Transmission 2022牛客多校第5场 C

题目描述

NIO is good at programming. He developed an STM32 program to communicate with his robot. When he sends a number to the robot, he will send a binary string of length NNN, that only consists of 000 and 111 instead of a decimal number. The string is a binary representation of the decimal number NIO wants to send. However, there are some bugs on the robot's intelligent system, when someone asks the robot, it sometimes will translate a wrong digit in the binary string, therefore reporting a wrong decimal number. 

Although there are bugs inside the robot, NIO is very lazy to fix them. He can tolerate the bug until the robot constantly reports wrong decimal numbers or crashes down. To find out whether the bug fix is necessary, NIO asked the robot 3×N3 \times N3×N times whether the k−thk-thk−th number in the binary string is 111. If there exists a unique string for his question, then NIO considers that there's no need of a bug fix. Note that it's possible that the same digit of the string is asked for more than 333 times and some digits will not be asked.

If at most ONCE the robot will report a wrong answer for NIO's all queries, can you figure out what binary string NIO sent?

输入描述:

There are multiple test cases.
For each case, the first line is NNN, the length of the string.
Following by 3×N3 \times N3×N lines, each line consists of an integer kkk and a string "YES" or "NO", denoting the robot's answer for whether the k−thk-thk−th digit in the binary string is 111. (The index is started from 000.)
1≤N≤1051 \leq N \leq 10^51≤N≤105

输出描述:

If the binary string can be determined, output it. Otherwise output -1, denoting that the robot will crash down.

示例1

输入

3
0 NO
1 YES
2 YES
0 YES
1 YES
2 YES
0 YES
1 YES
2 YES

输出

111

题意： 有一个机器人以及一个长度为n的01串，机器人对于这个01串有3*n条陈述语句，每条语句给出该01串某个位置是否为1，不过这个机器人可能会说谎，已知其最多说谎一次，问能否确定该01串。

分析： 可以统计出对于每一位机器人给出1和0的次数，记为num1[i]和num0[i]，然后0~n-1遍历一遍数组，按照num1和num0的值分类讨论，显然num1和num0同时大于等于2是不可能出现的，这意味着说谎不止1次，之后就是其中一个大于等于2，另一个等于1，这时候说明一定说谎了，如果其中一个大于等于2，另一个等于0，那么意味着没有说谎，接下来是其中一个为1，另一个也为1，这时候肯定说谎了，并且没法知道具体哪一次说的谎，所以此时无法判断，然后是其中一个为1，另一个为0，这时候要先看是否说谎，如果未说谎那么无法确定，如果说过谎，那么可以确定，最后就是全为0的情况了，这时候显然是无法确定的。

具体代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
 
int n, num0[100005], num1[100005], ans[100005]; 
 
bool check(){
	bool lie = false;//是否说谎
	for(int i = 0; i < n; i++){
		if(num0[i] >= 2 && num1[i] == 1){
			lie = true;
			ans[i] = 0;
		}
		if(num0[i] >= 2 && num1[i] == 0)
			ans[i] = 0;
		if(num1[i] >= 2 && num0[i] == 1){
			lie = true;
			ans[i] = 1;
		}	
		if(num1[i] >= 2 && num0[i] == 0)
			ans[i] = 1;
		if(num0[i] == 1 && num1[i] == 1)
			return false; 
		if(num0[i] == 0 && num1[i] == 0)
			return false;
	}
	for(int i = 0; i < n; i++){
		if(num0[i] == 1 && num1[i] == 0){
			if(lie)
				ans[i] = 0;
			else return false;
		} 
		if(num1[i] == 1 && num0[i] == 0){
			if(lie)
				ans[i] = 1;
			else return false;
		} 
	}
	return true;
}
 
signed main()
{
	while(~scanf("%d", &n)){
		for(int i = 0; i < n; i++)
			num0[i] = num1[i] = 0;
		for(int i = 1; i <= 3*n; i++){
			int t;
			char s[10];
			scanf("%d%s", &t, s);
			if(s[0] == 'Y') num1[t]++;
			else num0[t]++;
		}
		if(check()){
			for(int i = 0; i < n; i++)
				printf("%d", ans[i]);
			puts(""); 
		}
		else puts("-1");
	}
    return 0;
}