题目大意
有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);
}
}