题目描述
一个$n × n$的与矩阵由一个长度为$n$的数列 $a₁, a₂, …, aₙ$ 生成。矩阵中第$i$行第$j$列的元素 $(i, j)$定义为 $aᵢ$与$aⱼ$的按位与运算结果，即$(i,j)$=aᵢ&aⱼ。其中，&表示按位与运算。对于同一个与矩阵，可能存在多个不同的数列可以生成它。现在：给定一个$n × n$的矩阵，你需要找到任意一个能够生成该矩阵的数列 $a₁, a₂, …, aₙ$。保证生成的字典序最小。
思路
为了保证生成的字典序最小，应该使用贪心的思路即，先确定a[1]的最小值，让后确定a[2]以此类推。
以$a[1]$为例，$a[1]$的取值与$matrix[1][j]$有关，如果$matrix[1][j]$的第$k$位为1，那么$a[1]$中的第$k$位同样为1，找到满足所有$matrix[1][j]$为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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<vector<int>> matrix(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> matrix[i][j];
}
}
vector<int> a(n);
for (int i = 0; i < n; ++i) {
a[i] = 0;
for (int j = 0; j < n; ++j) {
if (i != j) {
a[i] |= matrix[i][j];
}
}
}
for (int i = 0; i < n; ++i) {
cout << a[i] << (i == n - 1 ? "" : " ");
}
cout << endl;
return 0;
}
|
思路
在暴力枚举基础上使用二分
代码
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
47
48
49
50
51
52
| #include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100000, M = 30;
int a, n, m , x;
int f[M];
int up[M];
bool check(int x)
{
memset(f, 0, sizeof f);
memset(up, 0, sizeof up);
f[1] = a, f[2] = a, up[1] = a, up[2] = x;
for(int i = 3; i <= n - 1; i ++)
{
up[i] = up[i - 1] + up[i - 2];
f[i] = f[i - 1] + up[i - 2];
}
return f[n - 1] >= m ? true:false;
}
int main()
{
cin >> a >> n >> m >> x;
int l = 0, r = N;
while(l < r)
{
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
memset(f, 0, sizeof f);
memset(up, 0, sizeof up);
f[1] = a, f[2] = a, up[1] = a, up[2] = l;
for(int i = 3; i <= x; i ++)
{
up[i] = up[i - 1] + up[i - 2];
f[i] = f[i - 1] + up[i - 2];
}
cout << f[x] << endl;
return 0;
}
|
string中的细节
字符串字典序的比较：string已重载了运算符直接使用
若是自定义字典序，注意
1
2
3
4
5
6
7
8
| string s1 = a.first;
string s2 = b.first;
for(int i = 0; i < min(a.first.size(), b.first.size()); i ++)
{
if(s1[i] != s2[i])
return s1[i] < s2[i];
}
return a.first.size() < b.first.size();
|
