CF1715D 题解

## 前言 [题目传送门！](https://www.luogu.com.cn/problem/CF1715D) [更好的阅读体验？](https://liangbowen.blog.luogu.org/solution-cf1715d) 感觉挺不错的一道图论转化题。（其实也和图论关系不大。） ## 思路 对于每个条件 $a_u \mid a_v = x$，二进制拆掉 $x$。如果 $x$ 的二进制位 $j$ 是 $1$，说明 $a_u$ 和 $a_v$ 中，当前位也肯定有至少一个为 $1$。标记一下 $f_{u, j} = f_{v, j} = 1$。 由于字典序最小，所以我们尽量只让 $a_{\max(u, v)}$ 的对应二进制位为 $1$，这样可以使得 $a_{\min(u, v)}$ 小一些。 由于要表示出点与点之间的关系，我们尝试**建图**。对每一个条件建图：连一条 $u$ 与 $v$ 间，边权为 $x$ 的双向边。 然后，枚举每一位二进制位 $j$，以及每一个点。对于每一个点，看与之相连的其他所有点（仍然是记为 $u$, $v$, $x$）。 我们现在是看 $a_u$ 的第 $j$ 位（指的是二进制下。之后同理），要不要变成 $1$。 如果 $x$ 的第 $j$ 位是 $0$，就跳过。否则，看 $u$ 与 $v$ 的大小关系。 + 如果 $u < v$，那么如果 $f_v$ 的第 $j$ 位没有被标记过，$a_u$ 的第 $j$ 位才必须为 $1$。否则应该让 $a_v$ 为 $1$，这样 $u$ 就能小一些了。 + 如果 $u > v$，那么看当前 $a_v$ 的结果。如果 $a_v$ 的第 $j$ 位为 $0$，那 $a_u$ 的第 $j$ 位才必须为 $1$。 你可能会问，$u = v$ 怎么办？显然 $a_u \mid a_u = x$，直接表明了 $a_u = x$。因此在第一步时，就能特判掉 $u = v$ 的情况，避免自环。 ## 完整代码 ```cpp #include <iostream> #include <cstdio> #define space putchar(' ') #define endl putchar('\n') using namespace std; int read() { char op = getchar(); int x = 0, f = 1; while (op < 48 || op > 57) {if (op == '-') f = -1; op = getchar();} while (48 <= op && op <= 57) x = (x << 1) + (x << 3) + (op ^ 48), op = getchar(); return x * f; } void write(LL x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + 48); } const int N = 1e5 + 5, M = 2e5 + 5; struct Edge { int now, nxt, w; }e[M << 1]; //这里空间要开足！赛时调了好久。 int head[N], cur; void add(int u, int v, int w) { e[++cur].now = v; e[cur].nxt = head[u]; e[cur].w = w; head[u] = cur; } bool bit(int x, int j) {return x & (1 << (j - 1));} //x 的第 j 位 bool flag[N][35]; //flag[i][j]表示a[i]的第j位是否有可能为1 int a[N]; bool calc(int u, int j) { for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].now, x = e[i].w; if (!bit(x, j)) continue; if (u < v) {if (flag[v][j]) return true;} else {if (!bit(a[v], j)) return true;} } return false; } int main() { int n = read(), m = read(); for (int i = 1; i <= m; i++) { int u = read(), v = read(), x = read(); for (int j = 1; j <= 30; j++) if (!bit(x, j)) flag[u][j] = flag[v][j] = true; if (u == v) {a[u] = x; continue;} //特判，避免加边时造成自环 add(u, v, x), add(v, u, x); } for (int j = 1; j <= 30; j++) for (int i = 1; i <= n; i++) if (calc(i, j)) a[i] |= (1 << (j-1)); for (int i = 1; i <= n; i++) write(a[i]), space; return 0; } ``` 希望能帮助到大家！