Codeforces Round 782 (Div. 2) E. AND-MEX Walk(思维+并查集)

news/2025/3/16 22:17:55/

原题链接:E. AND-MEX Walk


题目大意:


给出一张 n n n 个点 m m m 条边的无向图,边带有边权。

我们定义一条路径的价值为:

假设我们经过了 k k k 个点(点和边都可重复经过),且按顺序经过的边的权值分别为 { w 1 , w 2 , w 3 , . . . , w k − 1 } \{w_1,w_2,w_3,...,w_{k-1}\} {w1,w2,w3,...,wk1} ,那么 m e x { w 1 , w 1 & w 2 , . . . , w 1 & w 2 & . . . & w k − 1 } mex\{w_{1},w_{1}\&w_{2},...,w_{1}\&w_{2}\&...\&w_{k-1}\} mex{w1,w1&w2,...,w1&w2&...&wk1} 就是我们路径的价值。( 其中 & \& & 为二进制的与的操作, m e x { S } mex\{S\} mex{S} 为集合 S S S 中没有出现过的最小的自然数)。

现在给出 q q q 次询问,每次给出两个不同的点 u , v u,v u,v ,问你从 u u u 出发经历一些点到达点 v v v 所能获得的路径的价值的最小值为多少。

解题思路:


答案只会出现 0 , 1 , 2 0,1,2 0,1,2 三种情况,感性证明一下:

假设要使得我们的 m e x { S } ≥ 3 mex\{S\}\geq3 mex{S}3 ,那么就要让我们的 S = { 0 , 1 , 2 } S=\{0,1,2\} S={0,1,2} 在我们的序列中全都出现过。

假设我们经历了一系列前缀与的情况,最后剩下一个 2 2 2 ,现在我们还要走过一系列的点,然后使得 1 1 1 出现在我们的序列中(或者剩下一个 1 1 1,再使得 2 2 2 出现)。

但注意到 2 = ( 10 ) 2 , 1 = ( 01 ) 2 2=(10)_{2},1=(01)_{2} 2=(10)2,1=(01)2,它们相互与起来为 0 = ( 00 ) 2 0=(00)_{2} 0=(00)2 ,那么想要使得 1 , 2 1,2 1,2 都同时出现在 m e x { S } mex\{S\} mex{S} 序列中同时出现,由于有 与运算 这个操作在,两者必然不可能同时出现。

对于上面所讨论的情况而言,我们最后一定只会只有 { 1 , 0 } , { 2 , 0 } , \{1,0\},\{2,0\}, {1,0},{2,0}, ,即答案一定会被限制在 { 0 , 1 , 2 } \{0,1,2\} {0,1,2} 中。

想想怎么做:

先考虑 m e x { S } = 0 mex\{S\}=0 mex{S}=0 的情况,对于这种情况来说,我们的 与操作 只要保证选出一些边,且某个二进制位上一直包含有 1 1 1 ,且这些边使得我们 u → v u \rightarrow v uv 联通即可,比较简单的一个想法就是,对每个二进制位开一个并查集,然后直接判连通性即可。

再考虑 m e x { S } = 1 mex\{S\}=1 mex{S}=1 的情况,假设我们 u → v u \rightarrow v uv与操作 不能使得某个二进制位上一直包含有 1 1 1 ,即我们 u , v u,v u,v 不在一个第 i i i 个二进制位的并查集之内( 没有任何一个 2 i 2^{i} 2i 位在路径上是一直出现的 ),那么这一定会使得我们 0 0 0 出现在 S S S 当中,因为此时我们必定要选出一条不包含 2 i 2^{i} 2i 的边( 否则 u u u 无法走到 v v v ),然后走过这条边。

那么什么时候会出现 1 1 1 呢?

给出一个结论:按上面的来说,我们与序列一定是 S = { a , b , c , d , . . . , 0 , 0 , 0 , 0 , . . . } S=\{a,b,c,d,...,0,0,0,0,...\} S={a,b,c,d,...,0,0,0,0,...}只要我们能使得那些二进制第 2 0 2^{0} 20 位不 单独出现 a , b , c , d , . . . , 0 a,b,c,d,...,0 a,b,c,d,...,0 这一段之间即可,怎么保证?我们只需要有至少存在某个二进制位 2 i ( i ≠ 0 ) 2^{i}(i\neq0) 2i(i=0) 和它一起同时出现,或者 2 0 2^{0} 20 不出现即可。那么我们最开始先保留二进制 2 i 2^{i} 2i 位,在此基础上我们任选一条边与起来,使得 2 0 2^{0} 20 这一位变成 0 0 0 ,最后再走任意的 ( u → v ) (u \rightarrow v) (uv) 的路径使得 m e x { S } = 0 mex\{S\}=0 mex{S}=0 即可。

可知这样做,我们最开始由于存在 2 i 2^{i} 2i 不会出现单独的 2 0 2^{0} 20,我们最后将 2 i 2^{i} 2i 消掉时,我们也能保证 2 0 2^{0} 20 在最开始时被消掉了,故 2 0 2^{0} 20 不可能单独出现。

要这样做,我们要找出所有能让 2 0 2^{0} 20 位为 0 0 0 的边,再找一个含有 2 i ( i ≠ 0 ) 2^{i}(i\neq0) 2i(i=0) 的并查集,和这些边合并起来,再判断 u , v u,v u,v 是否在这些新的并查集中即可。

再考虑 m e x { S } = 2 mex\{S\}=2 mex{S}=2 的情况,显然答案只会有 0 , 1 , 2 0,1,2 0,1,2 ,只要上面的情况不满足,那么我们的答案就一定会是 2 2 2 了。

时间复杂度: O ( n log ⁡ w + ( m + q ) α ( n ) log ⁡ w ) O(n\log w+(m+q)\alpha(n)\log w) O(nlogw+(m+q)α(n)logw)

AC代码:

#include <bits/stdc++.h>
using namespace std;using PII = pair<int, int>;
using i64 = long long;struct DSU {vector<int> fa, siz;DSU(int n) : fa(n + 1), siz(n + 1, 1) { iota(fa.begin(), fa.end(), 0); };int find(int x) {while (x != fa[x]) x = fa[x] = fa[fa[x]];return x;}int size(int x) { return siz[find(x)]; }bool same(int x, int y) { return find(x) == find(y); }bool merge(int x, int y) {x = find(x), y = find(y);if (x == y) return false;siz[y] += siz[x];fa[x] = y;return true;}
};void solve() {int n, m;cin >> n >> m;vector dsu1(31, DSU(n));vector<bool> mark(n + 1);for (int i = 1; i <= m; ++i) {int u, v, w;cin >> u >> v >> w;for (int j = 0; j <= 30; ++j) {//至少包含 2^i 的并查集if (w >> j & 1) {dsu1[j].merge(u, v);}}if (~w & 1) {mark[u] = mark[v] = true;}}auto dsu2 = dsu1;//判1的并查集for (int j = 0; j <= 30; ++j) {for (int i = 1; i <= n; ++i) {//将至少包含 2^i 的并查集和 2^0 = 0 的边并起来 保证最后 2^0 恒为0if (mark[i]) {dsu2[j].merge(i, 0);}}}int q;cin >> q;for (int i = 1; i <= q; ++i) {int u, v;cin >> u >> v;int ans = 2;//先设为2for (int j = 0; j <= 30; ++j) {//是否可以为0if (dsu1[j].same(u, v)) {ans = min(ans, 0);}}for (int j = 1; j <= 30; ++j) {//是否可以为1if (dsu2[j].same(u, 0)) {ans = min(ans, 1);}}//否则为2cout << ans << '\n';}
}signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t = 1; //cin >> t;while (t--) solve();return 0;
}

http://www.ppmy.cn/news/1368018.html

相关文章

存储过程基本了解

文章目录 介绍存储过程示例1. 目的2. 输入参数3. 输出参数4. 执行逻辑5. 返回值6. 示例用法7. 注意事项 存储过程的关键字有哪些简单实操 介绍 存储过程是一组预编译的SQL语句&#xff0c;以及流程控制语句&#xff0c;封装在数据库服务器中并可以被重复调用。它们可以接收参数…

2024/3/1 贪心

跳跳 跳跳&#xff01; - 洛谷 思路&#xff1a;从一个数组里面依次取出最大值和最小值&#xff0c;然后进行运算 完整代码&#xff1a; #include <bits/stdc.h> #define int long long #define PII std::pair<int,int> signed main() {int n;std::cin >>…

大数据智能化-长视频领域

随着数字化时代的到来&#xff0c;长视频领域的发展迎来了新的机遇和挑战。在这一背景下&#xff0c;大数据智能化技术的应用成为长视频行业提升用户体验、优化运营管理的重要手段之一。本文将从优爱腾3大长视频背景需求出发&#xff0c;分析静态资源CDN、视频文件存储与分发、…

27.HarmonyOS App(JAVA)可复用列表项的ListContainer

可复用列表项的ListContainer 简短的列表可以通过定向布局实现,但是如果列表项非常多,则使用定向布局就不再合适。如需要创建50个列表项的列表,那么用定向布局实现至少需要创建50个以上的组件了。然而,限于设备屏幕大小的限制,绝大多数组件不会显示在屏幕上,却会占据大量的内存…

港大提出GraphEdit, 图数据编辑大模型!

论文链接&#xff1a;https://arxiv.org/abs/2402.15183 代码链接&#xff1a;https://github.com/HKUDS/GraphEdit 摘要 图结构学习&#xff08;Graph Structure Learning, GSL&#xff09;旨在通过生成新的图结构来捕捉图结构数据中节点之间的内在依赖性和交互关系。 图神…

JavaScript定义函数,创建函数实例时的内部原理

1、定义一个函数&#xff0c;JavaScript内部各做了哪些事情 定义一个函数时&#xff0c;JavaScript内部执行了以下步骤&#xff1a; 解析函数声明: 当你定义一个函数时&#xff0c;JavaScript的解析器会首先解析函数声明。这意味着它会检查函数声明的语法是否正确&#xff0c;…

100M服务器能同时容纳多少人访问

100M服务器的并发容纳人数会受到多种因素的影响&#xff0c;这些因素包括单个用户的平均访问流量大小、每个用户的平均访问页面数、并发用户比例、服务器和网络的流量利用率以及服务器自身的处理能力。 点击以下任一云产品链接&#xff0c;跳转后登录&#xff0c;自动享有所有…

qiankun微前端使用

微前端是什么&#xff1f; 微前端就是页面的某个功能可以独立为一个项目进行开发、部署。比如&#xff1a;自己的项目使用iframs引入百度 qiankun qiankun是一个基于single-spa的微前端实现库&#xff0c;qiankun 对于用户而言只是一个类似 jQuery 的库&#xff0c;你需要调…