Legend
给定 (n) 个长 (m) 的数组 (s_1,s_2,cdots,s_n),已知这些数组都是由某一个数组修改至多两个元素得到的,求一个满足条件的数组或报告无解。
(n imes m le 250\,000)。
Link ( extrm{to Codeforces})。
Editorial
我们不妨就以第一个数组为样本来构造——如果存在解,必然第一个数组修改两个位置就能得到答案。
所以暴力检查第 (i)((2 le i le n)) 个数组,设 (s_i) 与 (s_1) 不同的位置有 (d) 个
- (d le 2),继续检查 (s_{i+1});
- (d ge 5),无解;
- (3 le d le 4),暴力把 (s_1) 与 (s_i) 不同的元素替换成 (s_i) 中的元素,(igets 2) 继续检查。
不难发现,这个做法并不是指数级的,而就是 (O(nm)) 的。
Code
那么问题来了,为什么在比赛的时候,我没有想到暴力复杂度是对的呢?
#include <bits/stdc++.h>
#define debug(...) fprintf(stderr ,__VA_ARGS__)
#define __FILE(x)
freopen(#x".in" ,"r" ,stdin);
freopen(#x".out" ,"w" ,stdout)
#define LL long long
const int MX = 250000 + 23;
const LL MOD = 998244353;
int read(){
char k = getchar(); int x = 0;
while(k < '0' || k > '9') k = getchar();
while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
return x;
}
using namespace std;
int n ,m;
vector<int> A[MX];
int Ans[MX];
bool check(int dep){
if(dep >= 3) return 0;
int ok = 1;
for(int i = 1 ; i < n ; ++i){
vector<int> pos;
for(int j = 0 ; j < m ; ++j){
if(A[i][j] != A[0][j]) pos.push_back(j);
}
int diff = pos.size();
if(diff > 4) return 0;
if(diff < 3) continue;
if(dep == 2) return 0;
if(diff == 3){
for(int j = 0 ; j < 3 ; ++j){
int org = A[0][pos[j]];
A[0][pos[j]] = A[i][pos[j]];
if(check(dep + 1)){
ok = 1;
goto End;
}
A[0][pos[j]] = org;
}
ok = 0;
break;
}
else{
for(int j = 0 ; j < 4 ; ++j){
int org = A[0][pos[j]];
A[0][pos[j]] = A[i][pos[j]];
if(check(dep + 1)){
ok = 1;
goto End;
}
A[0][pos[j]] = org;
}
ok = 0;
break;
}
}
End:
if(ok) for(int i = 0 ; i < m ; ++i) Ans[i] = A[0][i];
return ok;
}
int main(){
n = read() ,m = read();
for(int i = 0 ; i < n ; ++i){
for(int j = 1 ; j <= m ; ++j){
A[i].push_back(read());
}
}
if(check(0)){
puts("Yes");
for(int i = 0 ; i < m ; ++i) printf("%d " ,Ans[i]);
}
else{
puts("No");
}
return 0;
}