题解：CF1475F Unusual Matrix

qwertpower · 2026-11-11 12:55:27 · 题解

我们分析一下把 a 矩阵转化为 b 矩阵的性质。

若 a_{i,j}\neq b_{i,j}，则需要对 a_{i,j} 操作奇数次。

若 a_{i,j}= b_{i,j}，则需要对 a_{i,j} 操作偶数次。

设 c_i 为对第 i 行的操作次数，d_j 为对第 j 列的操作次数。则对 a_{i,j} 的操作次数为 c_i+d_j 次。

我们可以发现，只有奇偶性有影响。所以 c_i,d_j 只取 0,1 两个数代表奇偶性。默认 1 代表奇数，0 代表偶数。

若 a_{i,j} 需要操作奇数次。则要求相当于要求 c_i\neq d_j。

若 a_{i,j} 需要操作偶数次。则要求相当于要求 c_i=d_j。

我们已经把它转换为 2-sat 问题了。

无解的情况就是代表某个变量取 0 的点和代表某个变量取 1 的点在同一个强连通分量中。

代码：

#include<bits/stdc++.h>
using namespace std;
int _,n,c[4005],dfn[4005],low[4005],m,cnt,u,v;
char b[1005][1005],x;
vector<int> a[4005];
stack<int> t;
void dfs(int u){
    t.push(u);dfn[u]=low[u]=++cnt;
    for(auto v:a[u])
    {
        if(!dfn[v]){
            dfs(v);low[u]=min(low[u],low[v]);
        }
        else if(!c[v])low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        m++;
        while(!t.empty()){
            v=t.top();t.pop();c[v]=m;
            if(u==v)break;
        }
    }
}\\Tarjan 缩点
void solve(){
    cin>>n;cnt=m=0;
    for(int i=1;i<=4*n;i++)
    {
        a[i].clear();dfn[i]=low[i]=0;c[i]=0;
    }\\清空
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)cin>>b[i][j];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>x;v=abs(b[i][j]-x);
            if(v){
                a[i].push_back(j+n+2*n);a[i+2*n].push_back(j+n);
                a[j+n+2*n].push_back(i);a[j+n].push_back(i+2*n);
            }
            else {
                a[i].push_back(j+n);a[i+2*n].push_back(j+n+2*n);
                a[j+n].push_back(i);a[j+n+2*n].push_back(i+2*n);
            }
        }
    }\\建图
    for(int i=1;i<=4*n;i++)
    {
        if(!dfn[i])dfs(i);
    }
    for(int i=1;i<=2*n;i++)
    {
        if(c[i]==c[i+2*n]){
            cout<<"NO\n";return;
        }
    }
    cout<<"YES\n";\\判断合法性
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>_;
    while(_--)solve();
    return 0;
}