CF1715D 题解
2022/8/27 23:22:54
本文主要是介绍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\) 的情况,避免自环。
完整代码
#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; }
希望能帮助到大家!
首发:2022-08-25 14:57:13
这篇关于CF1715D 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!