cf1492e
xh39
·
·
题解
注:本题解时间复杂度 O(36n^2+nm) 不保证正确。
正确数据在任意一行上改变不超过 2。所以设第一行为标准行，要求出改第一行的哪两个数。
如果直接枚举，需要 O(m^{2})，所以肯定不能直接枚举。需要观察一下可能改的数有什么规律。
改的数肯定是与第一行不同的数。若相同，改了反而会使差异更大。
设第一行与第 i 行的差异为 dif[i]。差异定义为 一个位置上的元素不同 的个数。于是对 dif 进行分类讨论。
$dif=4$:一定是要改变差异中的 $2$ 个。于是枚举哪两个。然后判断是否可行。由于只有4个，所以全部枚举也只需要 $C^{2}_{4}=6(\text{次})$ 即可。
$dif=3$:此种情况比较复杂。如果单纯改其中的 $2$ 个，会被这一组数据卡掉:
```cpp
3 3
0 1 2
3 4 5
6 7 8
```
这时，需要把 $1$ 改为 $4$，把 $2$ 改为 $8$。所以有可能改过的答案来自不同的 $2$ 行。
这时，需要枚举到底来自哪两行。同样，只会来自差异部分。
时间复杂度:此时并**不**是要枚举 $O(n^{2})$ 种情况。$dif[i]\leq3$，意味着至少要改成这一行中的一个差异。否则这一行差异不会变小，这样就无解了。所以只需要 $O(n)$ 找到其中一个 $dif[i]==3$ 的行，然后枚举所有的 $dif[j]=3$ 且 $i!=j$ 的 $j$。所以只需要 $O(n)$ 即可。
$dif\leq2$:此时无法判断是否改了。所以此信息对我们没用。如果仅有 $dif<=2$ 的行，直接输出第一行即可。
现在需要解决如何 $O(n)$ 求修改 $2$ 个数后的差异。枚举每一行，看改对(指原来错，现在对)有多少个，改错(原来对，现在错)有多少个，然后直接 $\text{总差异}\gets dif[i]-\text{改对}+\text{改错}$。具体见代码。
细节:因本题未单独限定 $n$ 与 $m$ 的范围，所以直接开二维数组不可取。于是模拟系统建二维数组的思路，$a[i][j]$ 表示为 $a[i\times m+j]$。这可以理解为简单的 有序数对hash。
总时间复杂度:$O(n^{2}+nm)$，常数为 $9\times 4=36$。
虽然时间复杂度较高，在 $n$ 很大的时候过不了，但是 codeforces 貌似没卡。
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dif[1000005][7],tot[1000005],a[1000005],n,m; //第i行第j列:m*i+j。
void check(int b,int c,int d,int e){ //将位置b修改为c,将位置d修改为e。
if(b==d){ //如果b与d相同,说明只改了一个。此种情况已经枚举过了,故可直接返回。若不返回,则需将d,e设为-1。避免计算改对与改错时出错。
return;
}
int i,j,sum=0,dui,cuo;
bool ykbb,ykbd; //ykbb表示b有没有改对一个数,ykbd表示d有没有改对一个数。
for(i=1;i<n;i++){
//对:之前没对&&现在对了。错:之前对了,现在错了。
dui=0;
ykbb=(b>=0&&a[b]!=c); //一开始要是对的,才可能改错。
ykbd=(d>=0&&a[d]!=e); //判b,d为正的原因:若其为负,则说明该元素不改,详见main函数调用部分。
for(j=0;j<tot[i];j++){ //枚举差异。改对的元素只可能在这里面产生。
dui+=(b==dif[i][j]&&a[i*m+b]==c)+(d==dif[i][j]&&a[i*m+d]==e); //b与其相等才可能改对该元素。而b相等的情况下,值与c(现在的数)相同即为改对。
ykbb&=(b!=dif[i][j]); //若b与dif相等,则说明之前也是错的。最终答案取与即表示原先所有的差异位置都不与b相同。
ykbd&=(d!=dif[i][j]);
}
cuo=ykbb+ykbd; //二者相加表示改错了多少。
if(tot[i]-dui+cuo>2){
return;
}
}
cout<<"Yes"<<endl;
for(i=0;i<m;i++){
if(i==b){ //被改成b的部分输出c,改成d的部分输出e。否则未改,输出原值。
cout<<c<<" ";
}else if(i==d){
cout<<e<<" ";
}else{
cout<<a[i]<<" ";
}
}
exit(0); //找到解了,直接结束程序。未结束说明该方案不可取。相当于return false;
}
int main(){
int i,j;
bool ykb=0;
cin>>n>>m;
for(i=0;i<n;i++){
for(j=0;j<m;j++){
scanf("%d",a+m*i+j);
}
}
for(i=1;i<n;i++){
dif[i][0]=m+1;
dif[i][1]=m+1;
dif[i][2]=m+1;
dif[i][3]=m+1;
for(j=0;j<m;j++){
if(a[j]!=a[m*i+j]){
dif[i][tot[i]++]=j;
}
}
if(tot[i]>=5)
cout<<"No";
return 0;
}
}
for(i=0;i<n;i++){
if(tot[i]==4){
check(dif[i][0],a[m*i+dif[i][0]],dif[i][1],a[m*i+dif[i][1]]);
check(dif[i][0],a[m*i+dif[i][0]],dif[i][2],a[m*i+dif[i][2]]);
check(dif[i][0],a[m*i+dif[i][0]],dif[i][3],a[m*i+dif[i][3]]);
check(dif[i][1],a[m*i+dif[i][1]],dif[i][2],a[m*i+dif[i][2]]);
check(dif[i][1],a[m*i+dif[i][1]],dif[i][3],a[m*i+dif[i][3]]);
check(dif[i][2],a[m*i+dif[i][2]],dif[i][3],a[m*i+dif[i][3]]);
cout<<"No";
return 0;
}
}
for(i=1;i<n;i++){
if(tot[i]==3){
check(dif[i][0],a[m*i+dif[i][0]],-3,-3); //现在只要改一个元素,那么第二个修改值定为原数组中不存在的下标,就相当于没改。
check(dif[i][1],a[m*i+dif[i][1]],-3,-3);
check(dif[i][2],a[m*i+dif[i][2]],-3,-3);
for(j=1;j<n;j++){
if(i!=j){
check(dif[i][0],a[m*i+dif[i][0]],dif[j][1],a[m*j+dif[j][1]]);
check(dif[i][0],a[m*i+dif[i][0]],dif[j][2],a[m*j+dif[j][2]]);
check(dif[i][1],a[m*i+dif[i][1]],dif[j][0],a[m*j+dif[j][0]]);
check(dif[i][1],a[m*i+dif[i][1]],dif[j][2],a[m*j+dif[j][2]]);
check(dif[i][2],a[m*i+dif[i][2]],dif[j][0],a[m*j+dif[j][0]]);
check(dif[i][2],a[m*i+dif[i][2]],dif[j][1],a[m*j+dif[j][1]]);
}
}
cout<<"No";
return 0;
}
}
cout<<"Yes"<<endl; //说明未出现>=3的情况,若出现,早就返回了。
for(i=0;i<m;i++){
cout<<a[i]<<" ";
}
return 0;
}
```
附一组可以卡掉本算法的数据(生成在 ```1.in```)(*windows7* 下跑了 $81.76$s):
```cpp
#include<iostream>
using namespace std;
int main(){
freopen("1.in","w",stdout);
int i;
cout<<"83333 3"<<endl;
for(i=0;i<40000;i++){
cout<<"0 0 0"<<endl;
}
for(i=0;i<43333;i++){
cout<<i*3<<" "<<i*3+1<<" "<<i*3+2<<endl;
}
return 0;
}
```