CF1844E题解

· · 题解

有一个套路是，只要确定第一行和第一列内填的字母，你就可以确定整个矩阵。

所以有个自然的想法是把矩阵中格子的关系转换为第一行和第一列内格子的关系。

假设我们不填字母，改填数字 0,1,2，来观察一下每个 2\times 2 子矩阵的性质。

不妨设左上角为 0 ，有如下四种情况：

\begin{bmatrix}0&1\\2&0\end{bmatrix}\begin{bmatrix}0&2\\1&0\end{bmatrix}\begin{bmatrix}0&2\\2&1\end{bmatrix}\begin{bmatrix}0&1\\1&2\end{bmatrix}

瞪眼看这四个矩阵，发现对于一个合法的矩阵 \begin{bmatrix}a&b\\c&d\end{bmatrix}，满足：

b+c\equiv a+d\pmod 3 这两个结论显然对整个矩阵也成立。 设 $(i,j)$ 的权值为 $a_{i,j},c_{i}=a_{i+1,j}-a_{i,j},d_i=a_{i,j+1}-a_{i,j}$。 不妨设 $a_{1,1}=0$，这个矩阵只和 $c,d$ 有关。 而且由于相邻的数不相等，所以 $c_i,d_i$ 的取值只有 $1,2$。 现在我们来看限制，限制有两种： 1. 给定 $(x,y)$，要求 $a_{x,y}=a_{x+1,y+1}
  1. 给定 (x,y)，要求 a_{x,y+1}=a_{x+1,y}

考虑分析子矩阵 \begin{bmatrix}a_{x,y}&a_{x,y+1}\\a_{x+1,y}&a_{x+1,y+1}\end{bmatrix}：

对于第一种限制类型，a_{x,y},a_{x+1,y},a_{x,y+1} 两两不相等，所以 a_{x,y+1}-a_{x,y}\not\equiv a_{x+1,y}-a_{x,y}\pmod3，即 d_y\neq c_x

对于第二种限制类型，a_{x+1,y}=a_{x,y+1}，所以 a_{x,y+1}-a_{x,y}\equiv a_{x+1,y}-a_{x,y}\pmod3，即 d_y=c_x

那么我们就直接 c_x 向 d_y 连边权为 w 的边（w=0 表示 c_x=d_y，w=1 表示 c_x\neq d_y）。

因为 c_i,d_i 的取值只有 1,2，用类似二分图染色的方法就可以判断是否有解了。

时间复杂度为 O(n+m+k)。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200005;
inline int read() {
    static int x=0,c=getchar(),f=1;
    for(f=1; c<=47||c>=58; c=getchar())f=f&&c^45;
    for(x=0; c>=48&&c<=57; c=getchar())x=(x<<3)+(x<<1)+(c&15);
    return f?x:-x;
}
vector<pair<int,int>>vec[MAXN];
int n,m,k,col[MAXN],ans;
void dfs(int u,int c) {
    if(col[u]!=-1) {
        if(col[u]^c) ans=0;
        return;
    }
    col[u]=c;
    for(pair<int,int>tmp:vec[u])
        dfs(tmp.first,tmp.second^c);
}
inline void solve() {
    n=read(),m=read(),k=read();
    for(int i=1,x,y,xx,yy,u,v,w; i<=k; ++i) {
        x=read(),y=read(),xx=read(),yy=read();
        u=min(x,xx),v=n-1+min(y,yy),w=x+y!=xx+yy;
        vec[u].push_back(make_pair(v,w)),vec[v].push_back(make_pair(u,w));
    }
    ans=1;
    for(int i=1; i<=n+m-2; ++i) col[i]=-1;
    for(int i=1; i<=n+m-2&&ans; ++i)
        if(col[i]==-1)
            dfs(i,0);
    printf(ans?"YES\n":"NO\n");
    for(int i=1; i<=n+m-2; ++i)vec[i].clear();
}
int main() {
    int t=read();
    while(t--)solve();
    return 0;
}