EOJ Monthly 2020.3 B 与矩阵 题解

题目大意

与矩阵是一个 n×n 的矩阵。规定矩阵中的第 i 行第 j 列记为 (i,j) 。

生成一个与矩阵的方式是，先生成一个长度为 n 的数列 a1,a2,…,an−1,an ，而矩阵中 (i,j)=ai&aj 。

其中 & 是指按位与运算，其计算方式是参与运算的两数各对应的二进位相与。只有对应的两个二进位都为 1 时，结果位才为 1 。

Cuber QQ 发现，同一个与矩阵可能对应着一些不同的数列，不过 Cuber QQ 现在只想知道字典序最小的数列是什么样的。

对于两个数列$a1,a2,…,an−1,an $和 $b1,b2,…,bn−1,bn$ ，如果存在一个整数$ k (1≤k≤n) $满足 $a_{k+1}<b_{k+1} $且 $a1=b1,a2=b2,…,ak=bk $，我们就认为数列 $a1,a2,…,an−1,an $的字典序要小于数列 $b1,b2,…,bn−1,bn $。

当然，Cuber QQ 不会这么容易让你得到答案，他会把矩阵所有的 $(i,i) (1≤i≤n) $的位置全部隐藏，只显示为 0 。

解题思路

很明显的位运算。

（但是不会啊。。

因为题目要求字典序最小，那么我们可以用贪心的思想，假设这个数为0。

只要哪一位出现了1，那么那一位必然为1，这样很明显求出来是最小的。

完整代码

#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
const long long N=1e9+7; 
int a[1005][1005];

int main(){
	int n;
	cin>>n;
	for(int i = 0;i < n;i++){
		for(int j = 0;j < n;j++){
			cin>>a[i][j];
		}
	}
	for(int i = 0;i < n;i++){
		int ans=0;
		for(int j = 0;j < n;j++){
			ans|=a[i][j];
		}
		printf("%d%c",ans,i!=n?' ':'\n');
	}
	return 0;
}