Codeforces Round #704 (Div. 2) E. Almost Fault-Tolerant Database

传送门

题目大意

有n个长为m的数组,我们要找出一个数组a,和之前n个数组比较,每次不能有超过两个数字不同,如果找不到输出No

题解

我们直接暴力就好了,将第一个数组当作我们的答案,然后从第二行开始比较,如果不同的数量超过了2个,我们尝试递归的修改就好了,如果和数组a不同的数量有3个,那么我们可以选择将一个或两个不同的数字都匹配为a的数字,如果一个数字匹配了,那我们还可以再修改一个数字,与其他的不同数量有3个的数组匹配,如果和数组a不同的数量有4个,我们任意选2个匹配,匹配完之后,再搜索一遍全部的数组,如果有超过2个不一样的,输出no,因为我们不能再修改第一个数组了,否则就和之前匹配成功的再次匹配失败了

#include<cstdio>
#include<vector>
using namespace std;
const int MAX=250005;
vector<int> cinmap[MAX];
int dont[4];
int n,m;
void print(int i,int m){
	printf("Yes\n");
	printf("%d",cinmap[i][0]);
	for(int j=1;j<m;j++){
		printf(" %d",cinmap[i][j]);
	}
	printf("\n");
}
int check(){
	int no=0;
	for(int i=1;i<n;i++){
		no=0;
		for(int j=0;j<m;j++){
			if(cinmap[i][j]!=cinmap[0][j]){
				no++;
			}
		}
		if(no>2){
			return i;
		}
	}
	return 0;
}
int minfind(int flag,int no,int deep){
	if(no==4){
		for(int i=0;i<3;i++){
			int keepi=cinmap[0][dont[i]],keepj;
			cinmap[0][dont[i]]=cinmap[flag][dont[i]];
			for(int j=i+1;j<4;j++){
				keepj=cinmap[0][dont[j]];
				cinmap[0][dont[j]]=cinmap[flag][dont[j]];
				if(!check()){
					return 1;
				}
				cinmap[0][dont[j]]=keepj;
			}
			cinmap[0][dont[i]]=keepi;
		}
	}else{
		for(int i=0;i<3;i++){
			int keepi=cinmap[0][dont[i]],keepj,goo;
			cinmap[0][dont[i]]=cinmap[flag][dont[i]];
			goo=check();
			if(!goo){
				return 1;
			}
			if(!deep){
				if(minfind(goo,no,1)){
					return 1;
				}
				for(int j=i+1;j<3;j++){
					keepj=cinmap[0][dont[j]];
					cinmap[0][dont[j]]=cinmap[flag][dont[j]];
					if(!check()){
						return 1;
					}
					cinmap[0][dont[j]]=keepj;
				}
			}
			cinmap[0][dont[i]]=keepi;
		}
	}
	return 0;
}
int main(){
	int no,flag=0;
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			int num;
			scanf("%d",&num);
			cinmap[i].push_back(num);
		}
	}
	no=0;
	for(int i=1;i<n;i++){
		int now=0;
		for(int j=0;j<m;j++){
			if(cinmap[i][j]!=cinmap[0][j]){
				now++;
			}
		}
		if(now>2&&now>no){
			flag=i;
			no=now;
		}
	}
	if(no>4){
		printf("No\n");
	}else if(no){
		no=0;
		for(int i=0;i<m;i++){
			if(cinmap[0][i]!=cinmap[flag][i]){
				dont[no]=i;
				no++;
			}
		}
		no=minfind(flag,no,0);
		if(no){
			print(0,m);
		}else{
			printf("No\n");
		}
	}else{
		print(0,m);
	}
}
上一篇:Codeforces Round #704 (Div. 2)A,B,C,D


下一篇:leetcode 704. binary-search 二分查找 python3