TopCoder 12792 BitwiseAnd 题解

题意

原题链接

\(m\) 个数 \(\{ori_i\}\),让你添加 \(n - m\) 个数(设这一共 \(n\) 个数为 \(\{a_i\}\)),使得:

  1. \(\forall 1 \le i, j \le n,~a_i \operatorname{bitand} a_j \ne 0\)
  2. \(\forall 1 \le i, j, k \le n,~a_i \operatorname{bitand} a_j \operatorname{bitand} a_k = 0\)

求字典序最小的 \(\{a_i\}\),或者判断无解。

做法

先转成二进制,然后条件就等价于对于每一个二进制位, \(\{a_i\}\) 中这一位是 \(1\) 的不超过 \(2\)。(不满足就无解,我们把 \(a_i\) 中这一位是 \(1\) 记为 这一位在 \(a_i\) 中出现

那么我们将 \(a\) 的前 \(m\) 个设为 \(ori\),后面先设为 \(0\)

枚举 \(i, j (1 \le i < j \le n)\)(都按从小到大的顺序),然后强制令 \(a_i \operatorname{bitand} a_j \ne 0\)。具体如下:

  • 如果 \(a_i \operatorname{bitand} a_j\) 已经不为 \(0\),就不考虑下面的了。
  • 如果 \(i \le m\)\(j \le m\),那么无解。(因为都修改不了)
  • 如果 \(i \le m\),那么 \(a_i\) 修改不了,只有从 \(a_j\) 下手。如果有二进制位只出现过一次(且这一次是在 \(a_i\) 中出现),那么可以让这一位在 \(a_j\) 也出现一次。如果有多个这样的二进制位,取最小的。(因为要字典序最小)
  • 否则(\(i > m, j > m\))分两种情况:
    • 如果有二进制位只出现过一次(且这一次是在 \(a_i\) 处出现),那么让它在 \(a_j\) 中出现。多个取最小。(因为要字典序最小)
    • 否则,取以下两种情况中 \(a_i\) 较小的:
      • 如果有二进制位只在 \(a_j\) 中出现,那么让它在 \(a_i\) 中出现。多个取最小。
      • 如果有一个二进制位没有出现过,那么让它在 \(a_i\)\(b_i\) 中都出现。

看不懂?伪代码版解释。

将只在 \(a_i\) 处出现一次的最小的 \(k\) 记为 \(occur(a_i)\)(如果没有就是 \(-1\))。
将没有出现过的最小的 \(k\) 记为 \(occur_{min}\)(如果没有就是 \(-1\))。
\(\operatorname{bitand}\) 是二进制下的按位与,\(\textbf{and}\) 是逻辑与(就是 )。

\[ \begin{array}{ll} 1 & \textbf{if } a_i \operatorname{bitand} b_i \ne 0&\\ 2 & \qquad \text{Skip.}&\\ 3 & \textbf{elif } i \le m \textbf{ and } j \le m&\\ 4 & \qquad \text{No Solution.}&\\ 5 & \textbf{elif } i \le m&\\ 6 & \qquad \textbf{if } occur(a_i) = -1&\\ 7 & \qquad \qquad \text{No Solution.}&\\ 8 & \qquad a_j \gets a_j \operatorname{bitor} 2^{occur(a_i)}&\\ 9 & \textbf{else}&\\ 10 & \qquad \textbf{if } occur(a_i) \ne -1&\\ 11 & \qquad \qquad a_j \gets a_j \operatorname{bitor} 2^{occur(a_i)}&\\ 12 & \qquad \textbf{else}&\\ 13 & \qquad \qquad id \gets +\infty&\\ 14 & \qquad \qquad \textbf{if } occur(a_j) \ne -1&\\ 15 & \qquad \qquad \qquad id \gets \min\left\{id, occur(a_j)\right\}&\\ 16 & \qquad \qquad \textbf{if } occur_{min} \ne -1&\\ 17 & \qquad \qquad \qquad id \gets \min\left\{id, occur_{min}\right\}&\\ 18 & \qquad \qquad \textbf{if } id = +\infty&\\ 19 & \qquad \qquad \qquad \text{No Solution.}&\\ 20 & \qquad \qquad a_i \gets a_i \operatorname{bitor} 2^{id}&\\ 21 & \qquad \qquad a_j \gets a_j \operatorname{bitor} 2^{id}&\\ \end{array} \]

证明不难(贪心),当作业

代码

代码

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
#include <cstdio>
#include <algorithm>
#include <vector>
using std::vector;
typedef long long LL;
const int N = 50 + 5;
int edge[N][N];
int used[70];
vector<int> to[N];
int nw_id() {
for(int i = 0; i < 60; i++) if(!used[i]) return i;
return -1;
}
LL ans[N];
class BitwiseAnd {
public:
vector<LL> lexSmallest(vector<LL> st, int n) {
int m = st.size();
for(int i = 1; i <= m; i++) ans[i] = st[i - 1];
for(int i = 1; i <= m; i++)
for(int j = 0; j < 60; j++) if(st[i - 1] >> j & 1) {
if(!used[j]) used[j] = i;
else if(used[j] != -1) edge[i][used[j]] = edge[used[j]][i] = true, used[j] = -1;
else return {};
}
for(int i = 59; i >= 0; i--) if(used[i] > 0) to[used[i]].push_back(i);
for(int i = 1; i <= n; i++)
for(int j = i + 1; j <= n; j++) if(!edge[i][j]) {
if(i <= m && j <= m) return {};
else if(i <= m) {
if(to[i].empty()) return {};
int id = to[i].back();
to[i].pop_back();
ans[j] |= 1LL << id;
used[id] = -1;
} else {
int id;
if(!to[i].empty()) id = to[i].back(), to[i].pop_back();
else {
id = 100;
if(to[i].empty() && to[j].empty()) id = std::min(id, nw_id());
if(!to[j].empty()) id = std::min(id, to[j].back()), to[j].pop_back();
}
if(id == -1 || id == 100) return {};
ans[i] |= 1LL << id, ans[j] |= 1LL << id;
used[id] = -1;
}
}
auto v = vector<LL>(ans + 1, ans + n + 1);
std::sort(v.begin(), v.end());
return v;
}
};