2020.7.25 PAT甲级7-2 The Judger (25分)

原题链接：暂无
关键词：模拟、unordered_set

A game of numbers has the following rules: at the beginning, two distinct positive integers are given by the judge. Then each player in turn must give a number to the judge. The number must be the difference of two numbers that are previously given, and must not be duplicated to any of the existed numbers. The game will run for several rounds. The one who gives a duplicate number or even a wrong number will be kicked out.

Your job is to write a judger program to judge the players’ numbers and to determine the final winners.

Input Specification:

Each input file contains one test case. For each case, the first line gives two distinct positive integers to begin with. Both numbers are in [1,10​5​​].

In the second line, two numbers are given: N (2≤N≤10), the number of players, and M (2≤M≤10​3​​), the number of rounds.

Then N lines follow, each contains M positive integers. The i-th line corresponds to the i-th player (i=1,⋯,N). The game is to start from the 1st player giving his/her 1st number, followed by everybody else giving their 1st numbers in the 1st round; then everyone give their 2nd numbers in the 2nd round, and so on so forth.

Output Specification:

If the i-th player is kicked out in the k-th round, print in a line Round #k: i is out… The rest of the numbers given by the one who is out of the game will be ignored. If more than one player is out in the same round, print them in increasing order of their indices. When the game is over, print in the last line Winner(s): W1 W2 … Wn, where W1 … Wn are the indices of the winners in increasing order. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the beginning or the end of the line. If there is no winner, print No winner. instead.

Sample Input 1:

101 42
4 5
59 34 67 9 7
17 9 8 50 7
25 92 43 26 37
76 51 1 41 40

Sample Output 1:

Round #4: 1 is out.
Round #5: 3 is out.
Winner(s): 2 4

Sample Input 2:

42 101
4 5
59 34 67 9 7
17 9 18 50 49
25 92 58 1 39
102 32 2 6 41

Sample Output 2:

Round #1: 4 is out.
Round #3: 2 is out.
Round #4: 1 is out.
Round #5: 3 is out.
No winner.

题目大意：
裁判先给出两个数，后面是n个玩家在m轮游戏中给出的数。如果玩家给出的数和之前的数重复，或者不是之前数的差值，则该玩家淘汰。淘汰之后的回合该玩家给出的数忽略。

分析：
考试的时候我都没读懂样例，只是单纯的以为要满足给的数在最早两个数的区间内且不能重复。而he difference of two numbers 的意思是两数之差，这波是英语水平的问题，考试的时候一定要根据样例来判断规则……

用二维数组存储玩家给出的所有数，用unordered_set存储合法的数。首先判断玩家是否已经淘汰，若已经淘汰应当continue到下一个数。然后判断该数是否在set中，后面的部分就没有难度了。

要用unordered_set防止出现超时的问题。

代码：

#include <bits/stdc++.h>
using namespace std;

int a, b, n, m;
int g[15][105];
unordered_set<int> se;
vector<bool> alive;

bool judge(int x){	//是否是之前数的差值 
	unordered_set<int>::iterator it;
	for(it = se.begin(); it != se.end(); it++){
		if(se.find((*it) + x) != se.end()) return true;
	}
	return false;
}


int main(){
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	
	cin >> a >> b >> n >> m;
	se.insert(a);
	se.insert(b);
	alive.resize(n+1);
	for(int i = 1; i <= n+1; i++) alive[i] = 1;
	
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; j ++){
			scanf("%d", &g[i][j]);
		}
	}
	
	for(int j = 1; j <= m; j ++){
		for(int i = 1; i <= n; i ++){
			if(!alive[i]) continue;
			int temp = g[i][j];
			if(se.find(temp) != se.end() || !judge(temp)){
				alive[i] = 0;
				printf("Round #%d: %d is out.\n", j, i);
			}
			else se.insert(temp);
		}
	}
	
	vector<int> winner;
	for(int i = 1; i <= n; i ++){
		if(alive[i]) winner.push_back(i);
	}
	if(winner.size() == 0) puts("No winner.");
	else{
		printf("Winner(s):");
		for(int i = 0; i < winner.size(); i ++)
			printf(" %d", winner[i]);
	}
	
	return 0;
}