题解：P16439 [XJTUPC 2026] 鲜艳 / 方格

Deepsick · 2026-05-10 19:15:58 · 题解

::::info[闲话] 感觉这题可能会像 P14752 一样出现不少大炮打蚊子题解，先写一个自认为比较简单的做法。不过证明可能没那么简单。 :::: 以下用 a_{i,j} 代表题目中的 \text{color}(i,j)。

结论：题目条件成立当且仅当每一行要么和上一行的颜色完全相同，要么完全相反。证明如下：

考虑反证法。假设存在某个 i（2\le i\le n），j（1\le j\le m）和 k（1\le k\le m），使得 a_{i-1,j}=a_{i,j} 而 a_{i-1,k}\ne a_{i,k}。

那么，一定存在绝对值之差为 1 的 j 和 k 满足这一条件。具体的，如果 a_{i-1,1}=a_{i,1}，则可以取 k 为最小满足 a_{i-1,k}\ne a_{i,k} 的数，并取 j=k-1；否则，取 j 为最小满足 a_{i-1,j}=a_{i,j} 的数，并取 k=j-1。

所以我们可以令 \vert j-k\vert=1。此时，在第 i-1 和第 i 行，第 j 和第 k 列围成的 2\times 2 子矩阵中，就出现了三个黑色格子或者三个白色格子，这显然是不可能的。因为如果一个矩形包含该子矩阵中的三个格子，则一定也包含第四个格子。

综上，结论成立。 ::::success[AC 代码]

#include <iostream>
using namespace std;
char s[501][501];
int main() {
    int T,n,m,i,j,x;
    cin>>T;
    while(T--) {
        cin>>n>>m;
        for(i=0;i<n;i++) cin>>s[i];
        for(i=1;i<n;i++) {
            x=0;
            for(j=0;j<m;j++) x+=s[i][j]==s[i-1][j];
            if(x>0&&x<m) break;
        }
        cout<<(i==n?"Yes\n":"No\n");
    }
    return 0;
}

:::: AC 记录。