- 2024-04-08蓝桥杯,推导部分和
题意:给定若干个区间端点与区间和,还有若干个查询,求该查询的区间和。思路:带权并查集。总结:区间左端点-1是为了左开右闭(也可以右端点+1)。比如[1,2]=(0,2]=5,[3,4]=(2,4]=6。这样就得到了[1,4]=11(查询1可以直接得到代表元素4),处理边界情况更方便。可以思考一下,如果不
- 2024-04-04洛谷 P1196 [NOI2002] 银河英雄传说
题意:30000列军队,每列初始有1个。编号从1~30000.每次操作有两种,将现在第i列所在的列合并到第j列所在列的末尾。或者查询第i列举例第j列的距离。思路:带权并查集。合并时将第i列头节点接到第j列头节点上。然后直接查询dist取绝对值相减就好。总结:一开始没看清题,以为要把从i列从当
- 2024-03-07A. Learning Languages
https://codeforces.com/problemset/problem/277/AItpresentsaproblemthatweneedtomakeallelementconnected,itcanbesolvedbyusingdsu.Ididn'tusemydsumodelandwriteasimpleversionofDsu.classDSU{public:DSU(intm):size_(m){
- 2023-12-11(来一套)JavaScript并查集模板
code: classUnionFind{constructor(n){this.parent=Array.from({length:n},(_,i)=>i);this.size=newArray(n).fill(1);this.cnt=n;}findset(x){if(this.parent[x]===x){returnx
- 2023-11-28P1955 [NOI2015] 程序自动分析
P1955[NOI2015]程序自动分析基本思路考虑到了不等号的不可传递性,所以决定只开相等的并查集。然后突发奇想,觉得可以在找父亲的过程中判断是不是冲突。然而这样就不能路径压缩,显然超时。并且,根本没看清楚数据范围,实际上这题的数很大,裸开数组会爆炸。这是一开始的代码#inclu