Warning: session_start(): open(/tmp/sess_2f7307ccfd18279ed33d85ea21ed9eab, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== Codeforces Round #704 (Div. 2) ======
[[https://codeforces.com/contest/1492|比赛链接]]
===== E. Almost Fault-Tolerant Database =====
==== 题意 ====
给定 $n$ 个长度为 $m$ 的数组 $\{a_i\}$。要求找到一个长度为 $m$ 的数组 $b$,使得 $b$ 与每个 $\{a_i\}$ 不同的位置数不超过 $2$。
==== 题解 ====
首先如果所有 $\{a_i\}$ 与 $\{a_1\}$ 不同的位置数都不超过 $2$,则 $\{a_1\}$ 就是答案。
否则如果存在 $\{a_j\}$ 与 $\{a_1\}$ 不同的位置数大于 $4$,则无解。
如果存在 $\{a_j\}$ 与 $\{a_1\}$ 不同的位置数等于 $4$,则暴力枚举两个一定要修改的位置,修改后暴力验证答案,如果全部失败则无解。
如果存在 $\{a_j\}$ 与 $\{a_1\}$ 不同的位置数等于 $3$,则暴力枚举一个一定要修改的位置和一个可能要修改的位置。
先修改一定要修改的位置,然后验证答案,如果所有 $\{a_i\}$ 与当前答案不同的位置数都不超过 $2$,则成功。
否则发现一个数组 $\{a_k\}$ 与当前答案不同位置大于 $2$,则将可能要修改的位置修改为 $\{a_k\}$ 位置对应的值,此时答案固定,重新验证。
如果暴力枚举一定要修改的位置和可能要修改的位置全部失败则无解。
总时间复杂度 $O(nm)$。
const int MAXN=2.5e5+5;
vector a[MAXN];
vector cmp(vector a,vector b){
vector diff;
_for(i,0,a.size()){
if(a[i]!=b[i])
diff.push_back(i);
}
return diff;
}
void check(vector ans,int n){
_for(i,1,n){
vector diff=cmp(ans,a[i]);
if(diff.size()>2)return;
}
puts("Yes");
_for(i,0,ans.size())space(ans[i]);
exit(0);
}
int main()
{
int n=read_int(),m=read_int();
_for(i,0,n){
a[i].resize(m);
_for(j,0,m)
a[i][j]=read_int();
}
check(a[0],n);
_for(i,1,n){
vector diff=cmp(a[0],a[i]);
if(diff.size()>=3){
if(diff.size()==4){
vector ans=a[0];
_for(j,0,4)_for(k,j+1,4){
ans[diff[j]]=a[i][diff[j]];
ans[diff[k]]=a[i][diff[k]];
check(ans,n);
ans[diff[j]]=a[0][diff[j]];
ans[diff[k]]=a[0][diff[k]];
}
}
else if(diff.size()==3){
vector ans=a[0];
_for(j,0,3)_for(k,0,3){
if(j==k)continue;
ans[diff[j]]=a[i][diff[j]];
check(ans,n);
_for(t,1,n){
vector diff2=cmp(ans,a[t]);
if(diff2.size()>=3){
if(diff2.size()==3&&find(diff2.begin(),diff2.end(),diff[k])!=diff2.end()){
ans[diff[k]]=a[t][diff[k]];
check(ans,n);
ans[diff[k]]=a[0][diff[k]];
}
break;
}
}
ans[diff[j]]=a[0][diff[j]];
}
}
break;
}
}
puts("No");
return 0;
}