1492E - Almost Fault-Tolerant Database(暴力&特判)

1492E - Almost Fault-Tolerant Database

思路

​ 对第一个数组进行操作，特判修改$0$次和修改$1$次，若都不成立，则特判修改两次，当前数组若与$a[0]$有超过$4$个不一样则无解，小于$3$个不管，否则若有解，必定要修改不同的两个，然后特判。

代码

// Problem: E. Almost Fault-Tolerant Database
// Contest: Codeforces - Codeforces Round #704 (Div. 2)
// URL: https://codeforces.com/contest/1492/problem/E
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// Date: 2021-02-23 17:05:42
// --------by Herio--------

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back 
void Print(int *a,int n){
    for(int i=1;i<n;i++)
        printf("%d ",a[i]);
    printf("%d\n",a[n]); 
}
int n,m;
vector<vector<int> >a;
void check(vector<int>ans,bool f){
    for(int i=0;i<n;i++){
        int c=0;
        for(int j=0;j<m;j++){
            if(ans[j]!=a[i][j]) c++;
            if(c>3) return;    //超过修改一次.
        }
        if(c>2){    //需要修改一次.
            if(f) return;    //如果修改过一次后还需要修改 说明该情况要修改两次.
            for(int j=0;j<m;j++){
                if(ans[j]!=a[i][j]){
                    vector<int>tmp=ans;
                    tmp[j]=a[i][j];
                    check(tmp,1);
                }
            }
            return;
        }
    }
    puts("Yes");
    for(int j=0;j<m;j++) printf("%d ",ans[j]);
    exit(0);
}
int main(){
    scanf("%d%d",&n,&m);
    a.resize(n,vector<int>(m));
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++) scanf("%d",&a[i][j]);
    check(a[0],0);//特判a[0] 一次都不用修改和只修改一次两种情况.
    for(int i=0;i<n;i++){
        vector<int>dif;
        for(int j=0;j<m;j++)
            if(a[i][j]!=a[0][j]) dif.pb(j);
        int sz=(int)dif.size();
        if(sz>4) return puts("No"),0;//超过4不成立.
        if(sz<=2) continue;//小于3不用管.
        for(int x:dif)    //否则修改两个位置.
            for(int y:dif){
                vector<int>tmp=a[0];
                tmp[x]=a[i][x],tmp[y]=a[i][y];
                check(tmp,0);
            }
        break;
    }
    puts("No");
    return 0;
}