B. 与矩阵
单点时限: 1.0 sec
内存限制: 512 MB
前有牛顿瘟疫“家里蹲”发明微积分。
现有 Cuber QQ 新冠肺炎“家里蹲”发明与矩阵。
与矩阵是一个 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) 满足 ak+1<bk+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 。
输入格式
第一行输入一个整数 n (1≤n≤1000) ，表示矩阵的大小。
接下来的 n 行，每行 n 个用空格隔开的整数 ai,1,ai,2,…,ai,n (0≤ai,j≤107) ，表示与矩阵。
输入保证至少存在一个可能的解。
输出格式
输出包含一行 n 个用空格隔开的数，表示字典序最小的数列。
样例
Input
3 0 0 1 0 0 2 1 2 0
Output
1 2 3
看起来很吓人...实际上把a[i]和别的数与出来的数或起来即可，这样也满足了字典序最小。
#include <bits/stdc++.h> using namespace std; int m[1005][1005], n; int a[1005] = {0}; inline int read() { int X=0; bool flag=1; char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();} while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();} if(flag) return X; return ~(X-1); } int main() { cin >> n; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { m[i][j] = read(); } } for(int i = 1; i <= n; i++) { for(int j = i + 1; j <= n; j++) { a[i] |= m[i][j]; a[j] |= m[i][j]; } } for(int i = 1; i <= n; i++) printf("%d ", a[i]); return 0; }