题解 P5427 【[USACO19OPEN]Left Out】

· · 题解

USACO银组题目，照例还是比较灵活、巧妙的。

题意：一个01矩阵，每次翻转一行或一列，最后除了一个元素之外的其他元素完全一样，求这个元素。

乍一看似乎没什么思路。怎么下手呢？

首先我们注意到，0和1是对称的，也就是说因为不限次数，只需把每一行翻转一遍就可以把元素01互换。

于是我们先把第一行和第一列翻转成0。

方法：对于第一行中的1，翻转它所在的列；对于第一列中的1，翻转它所在的行。

于是我们得到了一个新矩阵：(以5*5为例）

于是我们发现：在不改变第一行和第一列的情况下，蓝色部分无法被改变（因为两次翻转同一行等于没有翻转）。

若有解，则解只有以下三种位置：（1，1）、第一行或第一列（除（1，1）外）、蓝色区域中

若答案在蓝色区域中，目标位置此时一定为1并且其他部分全部为0

若答案在（1，1），则蓝色区域一定此时全部为1（翻转第一行再翻转第一列后，图中只有（1，1）为0）

若答案在第一行或第一列（除（1，1））上，则目标位置所在列或行在蓝色区域中一定全部为1且蓝色区域其他部分全部为0（翻转该列或行后，图中只有目标位置为1）

若不符合这三种情况，则无解

（感性理解一下没有其他情况吧qwq，蒟蒻也不会严谨证明啊）

于是我们就愉快地做完了

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector> 
#define pii pair<int, int>
using namespace std; 

int main()
{
    int n; 
    scanf("%d", &n); 
    if(n == 1){printf("-1"); return 0; }

    char c; 
    int a[n + 1][n + 1]; 

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        {
            c = getchar(); 
            while(c != 'L' && c != 'R')c = getchar(); 
            a[i][j] = ((c == 'L') ? 0 : 1); 
        }

    for(int i = 1; i <= n; i++)
        if(a[i][1])
            for(int j = 1; j <= n; j++)
                a[i][j] ^= 1; 

    for(int i = 2; i <= n; i++)
        if(a[1][i])
            for(int j = 1; j <= n; j++)
                a[j][i] ^= 1; 
    //翻转            
    int f = 0; 
    for(int i = 2; i <= n; i++)
        for(int j = 2; j <= n; j++)
            f += a[i][j]; 
    //通过子矩阵和判断情况
    if(f == (n - 1) * (n - 1))
    {
        if(n == 2)printf("-1\n"); else printf("1 1\n"); 
        return 0; 
    }
    else if(f == 1)
    {
        for(int i = 2; i <= n; i++)
            for(int j = 2; j <= n; j++)
                if(a[i][j]){printf("%d %d", i, j); return 0; }
    }
    else if(f == n - 1)
    {
        for(int i = 1; i <= n; i++)
        {
            int s = 0; 
            for(int j = 1; j <= n; j++)
                s += a[i][j]; 
            if(s == n - 1){printf("%d %d", i, 1); return 0; }
        }
        for(int i = 1; i <= n; i++)
        {
            int s = 0; 
            for(int j = 1; j <= n; j++)
                s += a[j][i]; 
            if(s == n - 1){printf("%d %d", 1, i); return 0; }
        }
    }//三种情况
    printf("-1"); 
    return 0; 
}

有错误请指出qwq