hdu 3461 Code Lock 并查集(有点难想到)★★
#include<stdio.h> #include<math.h> int set[]; int count; #define mod 1000000007 int find(int x) { int r=x; while(r!=set[r]) r...
HDU 3461 Code Lock（并查集）
很好的一个题，思想特别6题意：给你小写字母个数n，每个字母可以向上翻动，例如：d->c,a->z。然后给你m对数（L,R）（L<=R），表示[L,R]之间可以同时向上翻动，且翻动后是相同的类型。问你最后可以出现多少种不同的类型。例如：abcabc只给你[1,3],那么abcabc=...
HDU 6109 数据分割 并查集，SET
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6109题意：中文题面解法：每次都贪心地尝试将尽量多的条件放进当前这组，遇到第一个与已有条件冲突时，就是分割的时候。相等具有传递性，直接用并查集维护，不相等的关系用set维护，注意到x1=x2,x1!=x3...
HDU 4313 Matrix（并查集）
http://acm.hdu.edu.cn/showproblem.php?pid=4313题意：给出一棵树，每条边都有权值，其中有几个点是特殊点，现在破坏边还使得这几个特殊点互相不可达，需要使得破坏的边的权值和最小。思路：解法很妙！利用并查集，先将每个点分成一个集合，将边按照降序排序，如果该边两边...
HDU 3461 思维＋并查集
Code Lock题目链接http://acm.hdu.edu.cn/showproblem.php?pid=3461Problem DescriptionA lock you use has a code system to be opened instead of a key. The loc...
hdu 3461 Code Lock（并查集）2010 ACM-ICPC Multi-University Training Contest（3）
想不到这还可以用并查集解，不过后来证明确实可以……题意也有些难理解——给你一个锁，这个所由n个字母组成，然后这个锁有m个区间，每次可以对一个区间进行操作，并且区间中的所有字母要同时操作。每次操作可以将区间中所有字母+1。即把a变成b，把z变成a。举个例子，比如有一个锁，由abcdef组成，前三个字母...
天梯赛 L2-024. （并查集） 部落
题目链接题目描述在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。输入格式：输入在第一行给出一个正整数N（<= 104），是已知小圈子...
BZOJ4530 BJOI2014大融合（线段树合并+并查集+dfs序）
易知所求的是两棵子树大小的乘积。先建出最后所得到的树，求出dfs序和子树大小。之后考虑如何在动态加边过程中维护子树大小。这个可以用树剖比较简单的实现，但还有一种更快更优美的做法就是线段树合并。对每个点开权值线段树，维护当前时刻这棵点为根的子树中，已经和其相连的点的dfs序情况。合并时直接将表示两棵子...
POJ 2236 Wireless Network（并查集）
传送门 Wireless NetworkTime Limit: 10000MS Memory Limit: 65536KTotal Submissions: 24513 Accepted: 10227DescriptionAn earthquake takes place in Southeast ...
hdu 1232 畅通工程（并查集算法）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1232畅通工程Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submis...
UVA - 11987 Almost Union-Find[并查集 删除]
UVA - 11987Almost Union-FindI hope you know the beautiful Union-Find structure. In this problem, you’re to implement something similar, but not identi...
[并查集] POJ 1182 食物链
食物链Time Limit: 1000MS Memory Limit: 10000KTotal Submissions: 66294 Accepted: 19539Description动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。 现有N个动物，以1...
HDU 5441 Travel（并查集+统计节点个数）
http://acm.hdu.edu.cn/showproblem.php?pid=5441题意：给出一个图，每条边有一个距离，现在有多个询问，每个询问有一个距离值d，对于每一个询问，计算出有多少点对（x，y）使得在x到y的路径上没有一条边的距离大于d。思路：只要边距离小于d，那就是可行的，直接加入...
bzoj 1196: [HNOI2006]公路修建问题 二分+并查集
题目链接1196: [HNOI2006]公路修建问题Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 1576 Solved: 909[Submit][Status][Discuss]DescriptionOI island是一个非常漂亮的岛屿,自开发...
HDU1875 畅通工程再续 (并查集)
畅通工程再续Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 20693 Accepted Submission(s): 6528Pro...
POJ - 1733 Parity game 种类并查集+离散化
思路：d（i, j）表示区间(i, j]的1的个数的奇偶性。输入最多共有5000*2个点，需要离散化处理一下。剩下的就是并查集判冲突。AC代码#include <cstdio>#include <cmath>#include <cctype>#include &l...
【BZOJ-3673&3674】可持久化并查集 可持久化线段树 + 并查集
3673: 可持久化并查集 by zkyTime Limit: 5 Sec Memory Limit: 128 MBSubmit: 1878 Solved: 846[Submit][Status][Discuss]Descriptionn个集合 m个操作操作：1 a b 合并a,b所在集合2 k...
Codeforces #541 (Div2) - F. Asya And Kittens（并查集+链表）
Problem Codeforces #541 (Div2) - F. Asya And KittensTime Limit: 2000 mSecProblem DescriptionInputThe first line contains a single integer nn (2≤n≤15...
HDU 1863：畅通project（带权值的并查集）
畅通projectTime Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 16075 Accepted Submission(s): 6677...
Codeforces Round #345 (Div. 2) E. Table Compression（并查集）
传送门首先先从小到大排序，如果没有重复的元素，直接一个一个往上填即可，每一个数就等于当前行和列的最大值 + 1如果某一行或列上有重复的元素，就用并查集把他们连起来，很（不）显然，处于同一行或列的相同元素始终应该保持一样的，然后再一个一个往上填#include <bits/stdc++.h>...