[LOJ 6030]「雅礼集训 2017 Day1」矩阵

rvalue 收录于 cnblogs 题解

2019-03-26 约 531 字预计阅读 2 分钟

迁移提示

本文迁移自博客园, 原文链接

[LOJ 6030] 「雅礼集训 2017 Day1」矩阵

题意

给定一个 $n\times n$ 的 01 矩阵, 每次操作可以将一行转置后赋值给某一列, 问最少几次操作能让矩阵全为 1. 无解输出 -1.

$n \le 1000$.

题解

首先手玩下样例就可以发现一个非常虾皮的明显性质: 因为操作是赋值而不是取或, 于是一定是先让某一行都为 1 然后用这一行去染所有不是全 1 的列.

对于构造一个全 1 的行, 如果行号为 $k$, 那么显然是用某一行的第 $k$ 列上的 1 去染第 $k$ 行. 如果初始状态恰好不存在任何一行的第 $k$ 列上有 1, 那么我们可以把任意一个有 1 的行覆盖到第 $k$ 列, 那么就存在某一行的第 $k$ 列上是 1 了.

这个过程中我们发现, 只要初始状态中有 1 就一定有合法方案.

那么我们只要枚举行号 $k$ 钦定它来完成染掉所有列的任务, 然后计算出让它全 1 的最少步数. 如果存在某一行的第 $k$ 列是 1 那么答案直接就是第 $k$ 行 0 的个数, 否则需要一步让某一行的第 $k$ 列是 1, 于是等于 0 的个数 $+1$.

然后剩下的就沙雕了, 算一算初始状态中有多少列不是全 1 就行了.

~~所以这题复杂度瓶颈其实是读入~~

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


#include <bits/stdc++.h>

namespace rvalue{
	const int MAXN=1010;

	int n;
	int cntx[MAXN];
	int cnty[MAXN];
	char a[MAXN][MAXN];

	int main(){
		scanf("%d",&n);
		bool valid=false;
		for(int i=1;i<=n;i++){
			scanf("%s",a[i]+1);
			for(int j=1;j<=n;j++){
				if(a[i][j]=='#'){
					valid=true;
					++cntx[i];
					++cnty[j];
				}
			}
		}
		if(!valid)
			puts("-1");
		else{
			int ans=n;
			for(int i=1;i<=n;i++)
				if(cnty[i])
					ans=std::min(ans,n-cntx[i]);
				else
					ans=std::min(ans,n-cntx[i]+1);
			for(int i=1;i<=n;i++)
				if(cnty[i]!=n)
					++ans;
			printf("%d\n",ans);
		}
		return 0;
	}
}

int main(){
	rvalue::main();
	return 0;
}

目录

[LOJ 6030]「雅礼集训 2017 Day1」矩阵

[LOJ 6030] 「雅礼集训 2017 Day1」矩阵

题意

题解

参考代码