CodePlus 第五次网络赛我有矩阵，你有吗？(思维+枚举)

Ch_Zaqdt

发布于 2019-01-11 10:50:21

5450

发布于 2019-01-11 10:50:21

文章被收录于专栏：Zaqdt_ACM

题目链接：https://oj.thusaac.org/#!/contest/136/problem/2 (要报名才能看题交题)

时间限制： 1.0 秒

空间限制： 128 MB

相关文件： 题目目录

题目描述

企鹅豆豆手里有两个 01 矩阵 A 和 B。他可以进行两种操作：

选择 A 矩阵的一行，然后把这一行的 0 变成 1，把 1 变成 0。
选择 A 矩阵的一列，然后把这一列的 0 变成 1，把 1 变成 0。

现在他想知道能不能把 A 矩阵通过以上操作变成 B 矩阵。保证 A 矩阵和 B 矩阵的大小一致。

输入格式

从标准输入读入数据。

每个测试点只有一组数据。

输入的第一行包含两个正整数 n 和 m，表示 A 矩阵的行数，保证 n≤103，m≤103。接下来 n 行，每行 m 个由空格隔开的整数，表示矩阵 A。保证矩阵中只有 0 或者 1。接下来 n 行，每行 m 个由空格隔开的整数，表示矩阵 B。保证矩阵中只有 0 或者 1。

输出格式

输出到标准输出。

如果矩阵 A 通过以上两种操作可以变成矩阵 B，输出 Koyi，否则输出 Budexing。

样例1输入

样例1输出

Koyi

样例1解释

对于样例一，依次对于第一行和第一列分别执行操作 1 和操作 2 即可。

因为对矩阵的操作是任意一行或一列，所以我们可以只对第一行和第一列进行操作的话，实际上就把整个矩阵进行了操作，所以我们先把两个矩阵不相同的标记一下，然后我们对第一行进行枚举，如果不相同，就把这一列的元素进行异或，然后再枚举第一列，如果不相同就把这一行进行异或，然后最终和B矩阵进行比较就行了。

AC代码：

#include <bits/stdc++.h>
#define maxn 1005
using namespace std;
int pre[maxn][maxn];
int a[maxn][maxn], b[maxn][maxn];
int n,m;

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            scanf("%d",&b[i][j]);
            pre[i][j] = a[i][j] ^ b[i][j];
        }
    }
    for(int j=0;j<m;j++){
        if(pre[0][j]){
            for(int i=0;i<n;i++){
                a[i][j] ^= 1;
                if(a[i][j] == b[i][j])pre[i][j] = 0;
                else pre[i][j] = 1;
            }
        }
    }
    for(int i=1;i<n;i++){
        if(pre[i][0]){
            for(int j=0;j<m;j++){
                a[i][j] ^= 1;
                if(a[i][j] == b[i][j]) pre[i][j] = 0;
                else pre[i][j] = 1;
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(pre[i][j]){
                puts("Budexing");
                return 0;
            }
        }
    }
    puts("Koyi");
    return 0;
}

经过FLY大佬的指点写了一发空间优化的呆码...

AC代码：

#include <bits/stdc++.h>
#define maxn 1005
using namespace std;
int a[maxn][maxn],b[maxn][maxn];
int n,m;

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&b[i][j]);
	for(int i=1;i<=m;i++){
		if(a[1][i] != b[1][i]){
			for(int j=1;j<=n;j++){
				a[j][i] ^= 1;
			}
		}
	}
	for(int i=2;i<=n;i++){
		if(a[i][1] != b[i][1]){
			for(int j=1;j<=m;j++){
				a[i][j] ^= 1;
			}
		}
	}
	bool flag = true;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j] != b[i][j]){
				puts("Budexing");
				return 0;
			}
		}
	}
	puts("Koyi");
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018年11月08日，如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度