专栏首页Zaqdt_ACMCodePlus 第五次网络赛 我有矩阵,你有吗?(思维+枚举)

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

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

时间限制: 1.0 秒

空间限制: 128 MB

相关文件: 题目目录

题目描述

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

  1. 选择 A 矩阵的一行,然后把这一行的 0 变成 1,把 1 变成 0。
  2. 选择 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输入

3 3
1 0 1
1 1 0
0 1 0
1 1 0
0 1 0
1 1 0

样例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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • POJ 2112 Optimal Milking(Floyd+二分+二分图多重匹配)

           题意是有k台挤奶机,c头奶牛,每台挤奶机最多可以给m奶头牛挤奶,1--k是挤奶机的编号,k+1--k+c是奶牛的编号,然后输入一个邻接矩阵,表示它...

    Ch_Zaqdt
  • Codeforces Round #546 (Div. 2) C. Nastya Is Transposing Matrices(思维)

    题目链接:https://codeforces.com/contest/1136/problem/C

    Ch_Zaqdt
  • POJ 3020 Antenna Placement(二分图最小边覆盖)

           题意是有一个n*m的地图,图中'*'表示城市,现在要给每个城市覆盖无线,需要安装基站,每个基站最多只能覆盖相邻的两个城市,也就是1*2或者2*1的...

    Ch_Zaqdt
  • 04:最匹配的矩阵

    04:最匹配的矩阵 总时间限制: 1000ms 内存限制: 65536kB描述 给定一个m*n的矩阵A和r*s的矩阵B,其中0 < r ≤ m, 0 < s...

    attack
  • 浙大版《C语言程序设计(第3版)》题目集 习题7-3 判断上三角矩阵

    上三角矩阵指主对角线以下的元素都为0的矩阵;主对角线为从矩阵的左上角至右下角的连线。

    C you again 的博客
  • 2018年全国多校算法寒假训练营练习比赛(第一场)

     说实话,一开始看到这个题,还以为是动态规划,后来想了一下好像并不存在什么子问题,就是单纯要求个最大值而已,枪的威力由强本身的威力加上配件的加成,那么配件加...

    mathor
  • 旋转不变的感知哈希

    package com.imageretrieval.features; import com.imageretrieval.utils.ImageUtil;...

    Venyo
  • P2347 砝码称重

    题目描述 设有1g、2g、3g、5g、10g、20g的砝码各若干枚(其总重<=1000), 输入输出格式 输入格式: 输入方式:a1 a2 a3 ...

    attack
  • 历届试题 最大子阵

    问题描述   给定一个n*m的矩阵A,求A中的一个非空子矩阵,使这个子矩阵中的元素和最大。

    AI那点小事
  • 09:矩阵乘法

    09:矩阵乘法 总时间限制: 1000ms 内存限制: 65536kB描述 计算两个矩阵的乘法。n*m阶的矩阵A乘以m*k阶的矩阵B得到的矩阵C 是n*k阶的...

    attack

扫码关注云+社区

领取腾讯云代金券