2020年7月第2题 PAT甲级真题 The Judger (25分)

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.

第二次作者道题了，心情炸裂，四个月和没有进步一样，真的很难受
每一轮判断这个人说的数字是否是前面记录的任意两个数字的差，且没有出现过，那就算过关。不然就淘汰，且后面也不用再参加了。
说真的，没有set和find函数，我用vector一个个遍历估计和个傻逼一样。
这里用的是unordered_set，可以减小查找时间，防止超时，和find()函数绝配。将前两个数字先加入s中，然后每一轮判断每个人说的数字，如果这个人说的数字在s中可以被find到或者不是任意两个数的差。任意两个数的差用unordered_set的迭代器来，遍历容器内的每一个数字，如果找得到x+当前迭代器的值，证明x就是这两个数的差了，就return false。每次it++，都要找一次。如果这个人不合格，就将它insert进bad中，然后输出它被淘汰的信息。反之，将这个数加入s中
最后for循环遍历每个人，看看能不能在bad中找到它，如果不能，证明这个人是winner
其实set就是用来find的，比vector好用多了！！！set是有序的，unordered_set是无序的，find的时间复杂度是O(logN)，比vector的for循环查找好多了

//记录每个人每轮的发言，如果这个人out了，它的发言不会被记录，且接下来到它的回合直接continue
//判断这个人的数字是否出现过且判断这个数是否是前面任意数的差值
//任意数的差值，是否找得到当前判断的这个数+当前的迭代器的数 
#include<iostream>
#include<unordered_set>
#include<cstdio>
using namespace std;
unordered_set<int> s;
unordered_set<int> bad;
int a[15][1005];

bool check(int x){
	for(unordered_set<int>::iterator it = s.begin(); it!=s.end();it++){
		if(s.find(x + *it) != s.end()) return true;
	}
	return false;
}

int main(){
	int s1,s2,n,m;
	cin>>s1>>s2>>n>>m;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin>>a[i][j];
		}
	}
	s.insert(s1);s.insert(s2);
	for(int i = 0; i <m; i++){//i是第几轮 
		for(int j = 0; j < n; j++){
			if(bad.find(j) != bad.end()) continue;
			if(s.find(a[j][i])!= s.end()||!check(a[j][i])){
				bad.insert(j);
				printf("Round #%d: %d is out.\n",i+1,j+1);
			}
			else{
				s.insert(a[j][i]);
			}
		}
	}
	bool flag = true;
	for(int i = 0; i < n; i++){
		if(bad.find(i) == s.end()){
			if(flag == true){
				printf("Winner(s): %d",i+1);
				flag = false;
			}
			else{
				printf(" %d",i+1);
			}
		}
	}
	if(flag == true) cout<<"No Winner";
	return 0;
}

自己用unordered_map写的，不知道会不会超时

//用unordered_map试试看，用两个unordered_map来
//一个map记录出现过的所有数，一个map记录出现过的所有数的差值，每次加进去一个数，都要遍历前面map的所有值，并和这个数做差，加入到后一个map里
//这个人out了就用bad记录它，然后每次到它的时候直接continue，最后输出不是bad的人
#include<vector>
#include<cstdio>
#include<iostream>
#include<unordered_map>
#include<cmath>
using namespace std;
int main(){
	unordered_map<int,int> exist;
	unordered_map<int,int> difference;
	int bad[15] = {0};//0就是好人 
	//知道长度的数组尽量别用vector，费时
	int a[15][1005];//a[1][1]记录1号第一局说的数字
	int s1,s2,n,m;
	cin>>s1>>s2>>n>>m;
	exist[s1]++;exist[s2]++;
	difference[abs(s1-s2)]++;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j<= m; j++){
			cin>>a[i][j];
		}
	}
	for(int i = 1; i <= m; i++){//外面是m局 
		for(int j = 1;j <= n; j++){//每次小循环是遍历n个人 
			if(bad[j] == 1) continue;
			if(exist[a[j][i]] != 0 || difference[a[j][i]] == 0){//以前出现过或者不为任意两个数的差值 
				bad[j]++;
				printf("Round #%d: %d is out.\n",i,j);
			}
			else{
				for(unordered_map<int,int>::iterator it = exist.begin(); it!=exist.end();it++){
					difference[abs(a[j][i] - it->first)]++;//当前这个数和之前存在的每一个数作差 
				}
				exist[a[j][i]]++;
			}
		}
	}
	bool first = true;
	for(int i = 1; i <= n; i++){
		if(bad[i] == 0 && first == true){
			printf("Winner(s): %d",i);
			first = false;
		}
		else if(bad[i] == 0 && first == false){
			printf(" %d",i);
		}
	}
	if(first == true){
		printf("No winner.");
	}
	return 0;
}