【模板】带权并查集

文章目录

    • 1. 奇偶游戏
    • 2. 银河英雄传说

1. 奇偶游戏

239. 奇偶游戏


在这里插入图片描述


题意: 依次给出多个区间的含 1 1 1 的个数的奇偶性,找出第一个不符合的答案的回答。

思路

已知区间 [ a , b ] [a,b] [a,b] [ b , c ] [b,c] [b,c]的奇偶性,那么具有传递性,即 [ a , c ] [a,c] [a,c]区间的奇偶性也已知了。(奇偶都指区间内 1 1 1的个数)

定义:区间奇为1,区间偶为0。

  • 那么传递性可表示为:

    • 1 + 1 − > 0 1+1->0 1+1>0
    • 1 + 0 − > 1 1+0->1 1+0>1
    • 0 + 1 − > 1 0+1->1 0+1>1
    • 0 + 0 − > 0 0+0->0 0+0>0

以第一种举例,读者可带入【a,b】为奇,【b,c】为奇,那么【a,c】为偶。

如此发现,传递性形同于异或,即将给定的区间【a,b】的奇偶性,可视为【1,a-1】区间和【1,b】区间的奇偶性的异或结果,这是因为异或的前缀和性质,读者可自行了解(简单理解: x x x xor x x x = 0 =0 =0)。所以给定一个区间【a,b】的奇偶性,实际上可以转化为 A − 1 A-1 A1 B B B的奇偶性。( 大写 A A A 定义为前缀和序列:【1,a】区间)

由上转化,我们需要维护的是前缀和序列的奇偶性:

  • 【a,b】奇: A − 1 A-1 A1 B B B不同类。(01,10)
  • 【a,b】偶: A − 1 A-1 A1 B B B 同类。(00,11)

我们可以通过并查集维护这种具有连通性,传递性的关系。考虑如下:(为了书写简便,以下用A代替上述推导的A-1了)

在这里插入图片描述

定义边权 d [ u ] d[u] d[u]:

  1. d [ u ] = = 0 d[u]==0 d[u]==0,表示 u u u 与父节点 p [ u ] p[u] p[u] 奇偶性同。
  2. d [ u ] = = 1 d[u]==1 d[u]==1,表示 u u u 与父节点 p [ u ] p[u] p[u] 奇偶性不同。

如图所示, A A A p [ A ] p[A] p[A] 同, p [ A ] p[A] p[A] r A rA rA 不同,那么如何推得 A A A 与根节点 r A rA rA 的关系也是不同呢?显然 d [ A ] d[A] d[A] xor d [ p [ A ] ] d[p[A]] d[p[A]] 就是答案。所以在路径压缩中,每个节点只需要做如上所述的异或运算即可得到和根节点的奇偶性关系。

那么在一个集合中,得到了每个节点和根节点的奇偶性关系,通过传递性,就可以知道该集合中的任意两个节点之间的关系了。

上述考虑完并查集的路径压缩以及同属一个集合之间节点的关系,现在考虑一下如何合并两个集合。

在这里插入图片描述

假设上图 A A A 集合和 B B B 集合合并, r B rB rB 连向 r A rA rA,那么图中 “ ? ” “?” ? 的边权是多少呢?考虑如下情况:

  • A A A B B B 同类:

    • ( d [ B ] d[B] d[B] xor ? ? ?) xor d [ A ] d[A] d[A] = = == == 0 0 0
  • A A A B B B 不同类:

    • ( d [ B ] d[B] d[B] xor ? ? ?) xor d [ A ] d[A] d[A] = = == == 1 1 1

= > => => ? ? ? = = == == t t t xor d [ A ] d[A] d[A] xor d [ B ] d[B] d[B] t t t 1 1 1 表示不同类, 0 0 0 表示同类)


所以对于给出的每个答案【a,b,t】(区间 [ a , b ] [a,b] [a,b],奇偶性 t : 0 / 1 t:0/1 t:0/1):

  • a − 1 a-1 a1 b b b 在一个集合:

    • 判断 d [ a − 1 ] d[a-1] d[a1] xor d [ b ] ! = t d[b] != t d[b]!=t 就是第一个不成立答案
  • a − 1 a-1 a1 b b b 不在一个集合:

    • 合并 a − 1 a-1 a1 集合连向 b b b 集合: p [ f i n d ( a − 1 ) ] = p [ f i n d ( b ) ] p[find(a-1)]=p[find(b)] p[find(a1)]=p[find(b)]
    • 并附上边权: d [ f i n d ( a − 1 ) ] = = d [ a − 1 ] d[find(a-1)]==d[a-1] d[find(a1)]==d[a1] xor d [ b ] d[b] d[b] xor t t t

读者可能会思考:上述判断不成立只有在同属于一个集合的情况下才会去判断,那么不属于一个集合然后合并的时候会不会存在矛盾呢?由于异或,由于传递性,是不会产生矛盾的。可以模拟一下各种情况。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set> 

using namespace std;

const int N = 200010;

int n, m;
int p[N], d[N]; 
int a[N << 1];

int find(int x)  // 并查集
{
    if (p[x] != x) {
        int r = find(p[x]);
        // d[x] ^= d[p[x]]; // 路径压缩中的权值计算
        d[x] += d[p[x]]; d[x] %= 2;
        p[x] = r;
    }
    return p[x];
}

struct node {
    int a, b, c;
}; 

node f[N << 1]; 

/*
由于题目数据太大,所以这里需要离散化处理。
此程序采用set离散化,注意需要用到的值还包含x-1。
*/

int main()
{
    cin >> n >> m;
    for (int i = 0; i < N; i++) p[i] = i;
    set<int> s;
    for (int i = 0; i < m; i++) {
        int u, v; string c; cin >> u >> v >> c;
        int x;
        if (c == "odd") {
            x = 1;
        } else {
            x = 0;
        }
        f[i] = {u, v, x}; 
        s.insert(u), s.insert(v);
        s.insert(u - 1), s.insert(v - 1);
    }
    int idx = 0;
    for (auto c: s) a[++idx] = c;
    
    for (int i = 0; i < m; i++) {
        int u = f[i].a, v = f[i].b, c = f[i].c; 
        int A = lower_bound(a + 1, a + 1 + idx, u - 1) - a, B = lower_bound(a + 1, a + 1 + idx, v) - a;
        int fx = find(A), fy = find(B);
        
        bool o = true; 
        
        if (fx == fy) {
            // if ((d[A] ^ d[B]) != c) o = false;
            if ((d[A] + d[B]) % 2 != c) o = false; 
        } else {
            p[fx] = fy; 
            // d[fx] = d[A] ^ d[B] ^ c;
            d[fx] = d[A] + d[B] + c;
        }
        
        if (!o) {
            cout << i << endl;
            return 0;
        }
    }
    cout << m << endl; 
    return 0;
}

这题还有扩展域做法,集合内属性维护的是条件,放在以后的并查集扩展域模板在做记录。


2. 银河英雄传说

238. 银河英雄传说


在这里插入图片描述


思路

  • s i z [ x ] siz[x] siz[x] 表示集合的大小, d [ x ] d[x] d[x] 表示 x x x p [ x ] p[x] p[x] 的距离。
  • a a a 列的船接在第 b b b 列的末尾,相当于让每个点到 p b pb pb 的距离都加上 s i z [ p b ] siz[pb] siz[pb]由于存储并查集中存在路径压缩的效果,因此只需要将 pa 到 pb 的距离加上 siz[pb] 即可,即 d [ p a ] = s i z [ p b ] d[pa] = siz[pb] d[pa]=siz[pb],其他跟着 p a pa pa 后面的元素会通过路径进行压缩更新 d [ i ] d[i] d[i] 的值。

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2e6 + 10;

int p[N], dis[N], siz[N];

int find(int x)  // 并查集
{
    if (p[x] != x) {
        int r = find(p[x]);
        dis[x] += dis[p[x]];
        p[x] = r;
    }
    return p[x];
}

int main()
{
    int n; scanf("%d", &n); 
    for (int i = 0; i < N; i++) siz[i] = 1, p[i] = i;
    int a, b; char op[2];
    for (int i = 0; i < n; i++) {
        scanf("%s%d%d", &op, &a, &b);
        int fx = find(a), fy = find(b);
        if (op[0] == 'M') {
            if (fx != fy) {
                p[fx] = fy;
                dis[fx] = siz[fy];
                siz[fy] += siz[fx];
            }
        } else {
            if (fx != fy) { printf("-1\n"); }
            else printf("%d\n", max(0, abs(dis[b] - dis[a]) - 1));
        }
    }
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/5061.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

分享一个国内可用的免费ChatGPT网站(自己写的)

背景 ChatGPT作为一种基于人工智能技术的自然语言处理工具&#xff0c;近期的热度直接沸腾&#x1f30b;。 作为一个程序员&#xff0c;我也忍不住做了一个基于ChatGPT的网站&#xff0c;免费&#xff01;免登陆&#xff01;&#xff01;国内可直接对话ChatGPT&#xff0c;也…

10.线性表代码实战

10.1 与408关联解析及本节内容介绍 链表比顺序表出现的顺序更加的频繁。 10.2线性表地顺序表示原理解析 线性表的特点&#xff1a; &#xff08;1&#xff09;表中的元素的个数是有限的 &#xff08;2&#xff09;表中元素的数据类型相同。意味着每一个元素占用相同大小的空…

使用Dism++和360安全卫士搞定Windows10离线升级

Windows10有很多版本&#xff0c;常见的由1903、1909、20H1、21H2等&#xff0c;在离线状态下&#xff0c;很难下载到匹配的升级补丁。期间尝试多种方法均失败&#xff0c;最后用Dism和360安全卫士组合拳搞定。 1、使用下载补丁&#xff0c;升级失败 比如这里介绍了常见补丁&a…

【SL101】 传感器接入chirpstack平台

【SL101】 传感器接入chirpstack平台使用硬件SL100工程师答疑chirpstack 中 net-server 使能 80-87 频段网关开启80-87 频段设备传感器端配置频点连接成功测试结果---chirpstackSL100系列温湿度传感器产品&#xff08;墨水屏版&#xff09;接入chirpstack 平台笔记记录 使用硬件…

mysql学习之数据系统概述

☀️马上要成为打工人&#xff0c;这几天把前面的知识都捡了捡&#xff0c;发现自己对关系数据库这块的学习还有所缺失&#xff0c;于是本章开始学习mysql 这里写目录标题1. 数据库系统的发展1.1 人工管理阶段1.2 文件系统阶段1.3 数据库阶段1.4 大数据阶段2 数据库系统的组成2…

了解这7个Node.js库,让你的开发效率提升不止一点点

Node.js是一个流行的JavaScript运行时环境&#xff0c;拥有庞大的生态系统和丰富的库&#xff0c;使得在Node.js上构建高效、可靠的应用程序变得非常容易。在这篇文章中&#xff0c;我们将分享七个有用的Node.js库&#xff0c;它们可以提高您的工作效率&#xff0c;让您更轻松地…

android:手搓一个即时消息聊天框(包含消息记录)

先看一下效果 1.后端 要实现这个&#xff0c;先说一下后端要实现的接口 1.创建会话id 传入“发送id”和“接收id”给服务端&#xff0c;服务端去创建“会话id” 比如 get请求&#xff1a;http://xxxx:8110/picasso/createSession?fromUserId1&toUserId2 返回seesionId…

【SSconv:全色锐化:显式频谱-空间卷积】

SSconv: Explicit Spectral-to-Spatial Convolution for Pansharpening &#xff08;SSconv&#xff1a;用于全色锐化的显式频谱-空间卷积&#xff09; 全色锐化的目的是融合高空间分辨率的全色&#xff08;PAN&#xff09;图像和低分辨率的多光谱&#xff08;LR-MS&#xff…

HTML5 Web 存储

HTML5 Web 存储 在HTML5之前&#xff0c;主要是使用cookies存储&#xff0c;cookies的缺点有&#xff1a;需要在请求头上带着数据&#xff0c;存储大小不过&#xff0c;在4k之内。本节&#xff0c; HTML5 web 存储&#xff0c;一个比cookie更好的本地存储方式。 什么是 HTML5 …

Redis技术详解

Redis技术详解 Redis是一种支持key-value等多种数据结构的存储系统。可用于缓存&#xff0c;事件发布或订阅&#xff0c;高速队列等场景。支持网络&#xff0c;提供字符串&#xff0c;哈希&#xff0c;列表&#xff0c;队列&#xff0c;集合结构直接存取&#xff0c;基于内存&…

Proxmox VE 超融合集群虚拟的NFS服务性能很差的问题解决

作者&#xff1a;田逸&#xff08;formyz&#xff09; 场景描述 五节点Proxmox VE集群&#xff0c;万兆网络,数据网络与存储网络独立&#xff0c;接口两两bond&#xff0c;交换机堆叠。 单机配置两颗AMD 宵龙CPU&#xff0c;核心数48&#xff0c;单台线程数192&#xff0c;单台…

服务器版RstudioServer安装与配置详细教程

Docker部署Rstudio server 背景&#xff1a;如果您想在服务器上运行RstudioServer&#xff0c;可以按照如下方法进行操作&#xff0c;笔者测试时使用腾讯云服务器&#xff08;系统centos7&#xff09;&#xff0c;需要在管理员权限下运行 Rstudio 官方提供了使用不同 R 版本的 …

Baumer工业相机中偏振相机如何使用Baumer堡盟GAPI SDK来进行偏振数据的计算转换输出(C++)

项目场景 Baumer工业相机堡盟相机是一种高性能、高质量的工业相机&#xff0c;可用于各种应用场景&#xff0c;如物体检测、计数和识别、运动分析和图像处理。 Baumer的万兆网相机拥有出色的图像处理性能&#xff0c;可以实时传输高分辨率图像。此外&#xff0c;该相机还具…

【ansible】管理变量与事实详解

目录 管理变量与事实 一&#xff0c;变量 1&#xff0c;变量命名 2&#xff0c;变量优先级&#xff08;高--低&#xff09; 3&#xff0c;命令行引用 4&#xff0c; 引用playbook中的变量 5&#xff0c; 在主机清单中定义变量 6&#xff0c; 在自定义变量文件中定义变量 7&…

Linux基础IO - 文件描述符、重定向

前面的文章中我们讲述了C语言中文件相关的操作与系统文件IO的接口&#xff0c;这篇文章中将会讲述文件描述符与重定向的知识。 运行在前文中的系统文件程序&#xff0c;通过观察可以看到图中的数据3非常的奇怪没头没尾的&#xff0c;下面我们就来从这里开始。 通过查看man手册…

console使用方法介绍

console是在写前端Javascript时经常会使用到&#xff0c;我平时使用最多的是console.log&#xff0c;相比大多数人也是如此吧&#xff01; 下面一起来看一下强大的console吧&#xff01; 01函数&#xff08;属性&#xff09; 包含如下函数 / 属性&#xff1a;memory、assert、c…

Hadoop三大框架之HDFS

一、概述HDFS产生的背景及定义HDFS产生背景随着数据量越来越大&#xff0c;在一个操作系统存不下所有的数据&#xff0c;那么就分配到更多的操作系统管理的磁盘中&#xff0c;但是不方便管理和维护&#xff0c;需要一种系统来管理多台机器上的文件&#xff0c;这就是分布式文件…

日入500+的程序员都在用的“接私活”平台

网上总说程序员的薪资很高&#xff0c;这我可就不同意了&#xff1a; 程序员的薪资哪里是很高&#xff0c;而是非常高&#xff01;而会接私活的程序员更是能拿到更高的收入&#xff01;作为一个程序员&#xff0c;这些接私活的网站一定要收藏起来&#xff0c;让你在“八小时外…

ChatGPT transformer 5篇经典论文以及代码和解读

一次性读懂ChatGPT的技术演进路线&#xff0c;根据李沐老师推荐的5篇经典论文&#xff0c;整理了论文原文、论文解读、Github代码实现。 2017Transformer继MLP、CNN、RNN后的第四大类架构2018GPT使用 Transformer 解码器来做预训练2018BERTTransformer一统NLP的开始2019GPT-2更…

区块链概论

目录 1.概述 2.密码学原理 2.1.hash函数 2.2.签名 3.数据结构 3.1.区块结构 3.2.hash pointer 3.3.merkle tree 3.3.1.概述 3.3.2.证明数据存在 3.3.3.证明数据不存在 4.比特币的共识协议 4.1.概述 4.2.验证有效性 4.2.1.验证交易有效性 4.2.2.验证节点有效性 …