题解 P5427 【[USACO19OPEN]Left Out S】

whiteqwq · 2020-10-30 10:38:42 · 题解

P5427 [USACO19OPEN]Left Out S解题报告：

更好的阅读体验

题意

• 给定一个n\times n的矩阵，可以给每一行取反，每一列取反。
• 如果可以让所有的数相同或者不能让只有一头奶牛与其他奶牛方向不同，那么输出-1。
• 否则输出行列最小的这头奶牛位置。

分析

提供一种好写又好想的暴力。

如果没有这样的奶牛，那么我们通过让行取反操作一定可以让所有的行相同。同样如果没有这样的奶牛，我们也可以通过列取反操作让所有的列相同。

考虑用\text{bitset}保存每一行每一列的奶牛朝向信息，我们可以暴力判断相邻的两行（注意1和n相邻）是否相同或者取反后相同。

同样的，我们可以对每一列进行这样的判断。

那么我们要求的奶牛位置肯定会让它所在的行列和它相邻的行列无法匹配，我们暴力找这样的位置就好了。

如果有多个这样的位置记得输出-1。

时间复杂度：O(n^2)。

代码

#include<stdio.h>
#include<iostream>
#include<bitset>
using namespace std;
const int maxn=1005;
int n,flg;
int ok1[maxn],ok2[maxn];
string s;
bitset<maxn>a[maxn],b[maxn],c[maxn],d[maxn];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        cin>>s;
        for(int j=1;j<=n;j++){
            if(s[j-1]=='L')
                a[i][j]=b[j][i]=0,c[i][j]=d[j][i]=1;
            else a[i][j]=b[j][i]=1,c[i][j]=d[j][i]=0;
        }
    }
    a[0]=a[n],b[0]=b[n],c[0]=c[n],d[0]=d[n];
    a[n+1]=a[1],b[n+1]=b[1],c[n+1]=c[1],d[n+1]=d[1];
    for(int i=0;i<=n;i++){
        if(a[i]==a[i+1]||a[i]==c[i+1])
            ok1[i]=0;
        else ok1[i]=1;
    }
    for(int i=0;i<=n;i++){
        if(b[i]==b[i+1]||b[i]==d[i+1])
            ok2[i]=0;
        else ok2[i]=1;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(ok1[i-1]+ok1[i]+ok2[j-1]+ok2[j]==4)
                flg++; 
    if(flg!=1){
        puts("-1");
        return 0;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(ok1[i-1]+ok1[i]+ok2[j-1]+ok2[j]==4)
                printf("%d %d\n",i,j);
    return 0;
}