前几天看到并查集的题目，竟然只会最简单的并查集，看来带权并查集和扩展域并查集还要是好好写个笔记复习复习的。
如果仅仅使用路径压缩的并查集，时间复杂度似乎并不是\(O(\alpha(n))\)，详情见这里。
yxc给出了一种简单易懂的理解扩展域并查集的方式：将并查集中的元素看成一个个条件，两个元素在一个集合中的意义是：如果有一个条件，那么整个集合中的条件都成立。
我来形式化一点：并查集中的每一个元素都是一个语句\(p\)，每一个集合\(S\)都是一个命题：
\(如果p(p \in S)，那么q(q \in S,q\not=p)。\)
这样就十分容易理解了。
注：(x)指并查集中编号为x的元素。
我们定义：
这样动物之间的关系就十分清晰了，合并的时候只需满足题意即可。
x和y同类：
x吃y：
由于A吃B，B吃C，C吃A，所以：
判断矛盾同理。
我们维护一个点到根节点的“距离”（这个“距离”是根据题意抽象得出的，而非真实的距离），以得出该点与集合中其它点的关系。
通常，关系有几种，距离就有几种，具体地，如果有\(n\)种关系，就有\(n\)种距离，为了方便，一般将距离定义为\([0,n-1]\)，这样可以使用取模运算方便地得出两点间相对关系。
还是上面的例题，这次使用带权并查集来做。
两只动物之间的关系只有3种，所以我们定义距离：
注：x->y意为x吃y
红色的边是根据题意的环形结构推理得出的。
所以，我们会发现当且仅当\(d_x + 1 \equiv d_y (mod 3)\)时，x吃y。
同类自然就不用讲，只要\(d_x \equiv d_y(mod 3)\)，x和y就同类。
判断矛盾同理。
维护\(d_x\)时，只需要暴力维护到根的权值之和即可。这为何是正确的呢？直观地理解，每一个结点都吃更深一层的结点，到了第3层，刚好完成一个循环，也就是第3层的结点和第0层的是同类，
而我们判断关系时又是在同余下处理的，所以自然是正确的。
需要注意的是，如果不做特殊处理，直接累加距离的话，可能会导致距离倍增并溢出。
解决办法有两个：
扩展域并查集更加直观、易懂，不易写错，但是也有缺点，就是空间占用过多。
带权并查集关系较为复杂，用到了同余的知识，可能会吃数学的亏（like me），但是空间占用小。
P2294 [HNOI2005]狡猾的商人
（带权并查集）
SPI接收数据左移一位问题目录SPI接收数据左移一位问题一、问题描述二、问题分析三、探究原理四、经验总结最近在工作在学习调试SPI的过程中遇到一个问题——接收数据整体向左移了一位（1bit）。SPI数据收发是数据交换，因此接收数据时从第二个字节开始才是有效数据，也就是数据整体向右移一个字节（1byte）。请教前辈之后也没有得到解决，通过在网上查阅前人经验终于解决问题，所以写一个避坑经验总结。实际背景：MCU与一款芯片使用spi通信，MCU作为主机，芯片作为从机。这款芯片采用的是它规定的六线SPI，多了两根线：RDY和INT，这样从机就可以主动请求主机给主机发送数据了。一、问题描述根据从机芯片手
文章目录一、项目场景二、基本模块原理与调试方法分析——信源部分：三、信号处理部分和显示部分：四、基本的通信链路搭建：四、特殊模块：interpretedMATLABfunction：五、总结和坑点提醒一、项目场景 最近一个任务是使用simulink搭建一个MIMO串扰消除的链路，并用实际收到的数据进行测试，在搭建的过程中也遇到了不少的问题（当然这比vivado里面的debug好不知道多少倍）。准备趁着这个机会，先以一个很基本的通信链路对simulink基础和相关的debug方法进行总结。 在本篇中，主要记录simulink的基本原理和基本的SISO通信传输链路（QPSK方式），计划在下篇记
【动态规划】一、背包问题1.背包问题总结1）动规四部曲：2）递推公式总结：3）遍历顺序总结：2.01背包1）二维dp数组代码实现2）一维dp数组代码实现3.完全背包代码实现4.多重背包代码实现一、背包问题1.背包问题总结暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化！背包问题是动态规划（DynamicPlanning）里的非常重要的一部分,关于几种常见的背包，其关系如下：在解决背包问题的时候，我们通常都是按照如下五部来逐步分析，把这五部都搞透了，算是对动规来理解深入了。1）动规四部曲：（1）确定dp数组及其下标的含义（2）确定递推公式（3）dp数组的初始化（4）确定遍历顺
1，Camera基本工作原理答案：光线通过镜头Lens进入摄像头内部，然后经过IRFilter过滤红外光，最后到达sensor（传感器），senor分为按照材质可以分为CMOS和CCD两种，可以将光学信号转换为电信号，再通过内部的ADC电路转换为数字信号，然后传输给DSP（如果有的话，如果没有则以DVP的方式传送数据到基带芯片baseband，此时的数据格式RawData，后面有讲进行加工）加工处理，转换成RGB、YUV等格式输出。数据流是如何从sensor到APP的？上述描述结束后，在ISP处理后面的阶段，数据会进行分流，分为capture,preview，video等以供后续动作使用。例如
📢博客主页：https://blog.csdn.net/dxt19980308📢欢迎点赞👍收藏⭐留言📝如有错误敬请指正！📢本文由肩匣与橘编写，首发于CSDN🙉📢生活依旧是美好而又温柔的，你也是✨目录🔴线性表1.1顺序表1.1.1顺序表定义1.1.2顺序表基本操作1.2单链表1.2.1单链表节点定义1.2.2单链表基本操作1.3双链表1.3.1双链表节点定义1.3.2双链表基本操作1.4静态链表🟠栈和队列2.1栈2.1.1顺序栈2.1.2链式栈2.2队列2.2.1顺序队列2.2.2链式队列2.3应用🟡串3.1串的定义与实现3.2串的模式匹配🟢树与二叉树4.1二叉树4.1.1二叉树的概念4.1.2
目录MyBatisPlusMP特点MP框架结构MP使用准备导入依赖springboot整合mybatisplus配置文件定义好实体类User后编辑mapper接口@Mapper与@MapperScan("包名")区别MP基本操作新增操作删除操作通过id删除用户通过map作为条件删除通过多个id实现删除更新用户通过id进行用户更新查询用户 根据id查询用户根据多个id查询用户根据map集合作为条件查询用户通用Service接口一些操作 查询总记录数批量添加数据MP常用注解雪花算法前言垂直分表水平分表条件构造器继承结构使用条件构造器实现查询操作查询所有用户根据构造器查询主键字段集合根据条件构造器查
本文总结了在以太坊智能合约中使用Solidity在合约内创建合约以及引用其他合约的方法，包括了如何使用mochai进行测试的方法。在这之前先明白一个比较：Contract{}相当于面向对象语言的类当部署后获得到address后，address相当于对象，address0x.......本身就类似指针地址然后我们讨论下Solidity代码中对合约类，合约对象的操作。Solidity首先区分下三种写法：import'ContractB.sol';ConractBB=newConractB(arg1,arg2...);ContractBB=ContractB(Baddress);functionse
智慧医院不良事件精细化管理平台——微信小程序总结一、实现的功能二、项目收获三、总结（经历分享）一、实现的功能到目前为止，微信小程序开发，到此就算是结束了，其中实现了不少功能，如下：1.1角色与权限（后端同学实现的，写这个方便介绍后面的功能）平台可以配置不同的用户角色并授予其不同的操作权限。每个用户在使用平台时都需要指定一个角色。1.2可视范围——根据角色绑定的权限菜单全体职工可以查看自己上报的事件（待审核、已通过、被驳回）。质控人员可以查看所有的事件（待审核、待评价、已通过、已驳回、已评价）。职能人员可以查看自己/自己部门负责的事件（待整改、待评价、已评价）。各科室医务人员可以查看本科室相关的
我得到了[objectObject]9778177结果，我尝试解析该值但都无济于事，出了点问题。letx=[{"total_count":7},{"total_count":9},{"total_count":778},{"total_count":177}]letsum=x.reduce((accum,obj)=>{returnaccum+obj.total_count})console.log(sum) 最佳答案 您可以添加一个起始值，因为第一次迭代从累加器的对象开始，而您没有所需的属性。letsum=x.reduce((acc
一、知识框架二、练习题调节一个装瓶机使其对每个瓶子的灌装量均值为μ盎司，通过观察这台装瓶机对每个瓶子的灌装量服从标准差σ＝1.0盎司的正态分布。随机抽取这台机器灌装的9个瓶子组成一个样本，并测定每个瓶子的灌装量。试确定样本均值偏离总体均值不超过0.3盎司的概率。解：设每个瓶子的灌装量为X，X为样本均值，样本容量为n。由于总体X服从正态分布，样本均值X也服从正态分布，且均值相同，标准差为所以三、简述题1什么是统计量？为什么要引进统计量？统计量中为什么不含任何未知参数？答：（1）统计量的定义：设X1，X2，…，Xn是从总体X中抽取的容量为n的一个样本，如果由此样本构造一个函数T（X1，X2，…，X
