树结构的并查集
采用树结构支持并查集的计算能够满足我们的要求。并查集与一般的树结构不同，每个顶点纪录的不是它的子结点，而是将它的父结点记录下来。下面是树结构的并查集的两种运算方式
⑴直接在树中查询
⑵边查询边“路径压缩”
对应与前面的链式存储结构，树状结构的优势非常明显：编程复杂度低；时间效率高。
直接在树中查询
集合的合并算法很简单，只要将两棵树的根结点相连即可，这步操作只要O（1）时间复杂度。算法的时间效率取决于集合查找的快慢。而集合的查找效率与树的深度呈线性关系。因此直接查询所需要的时间复杂度平均为O（logN）。但在最坏情况下，树退化成为一条链，使得每一次查询的算法复杂度为O（N）。
边查询边“路径压缩
其实，我们还能将集合查找的算法复杂度进一步降低：采用“路径压缩”算法。它的想法很简单：在集合的查找过程中顺便将树的深度降低。采用路径压缩后，每一次查询所用的时间复杂度为增长极为缓慢的ackerman函数的反函数——α（x）。对于可以想象到的n，α（n）都是在5之内的。
并查集：(union-find sets)是一种简单的用途广泛的集合. 并查集是若干个不相交集合，能够实现较快的合并和判断元素所在集合的操作，应用很多。一般采取树形结构来存储并查集，并利用一个rank数组来存储集合的深度下界，在查找操作时进行路径压缩使后续的查找操作加速。这样优化实现的并查集，空间复杂度为O(N)，建立一个集合的时间复杂度为O(1)，N次合并M查找的时间复杂度为O(M Alpha(N))，这里Alpha是Ackerman函数的某个反函数，在很大的范围内（人类目前观测到的宇宙范围估算有10的80次方个原子，这小于前面所说的范围）这个函数的值可以看成是不大于4的，所以并查集的操作可以看作是线性的。它支持以下三中种操作:
－Union (Root1, Root2) //并操作；把子集合Root2并入集合Root1中.要求：Root1和Root2互不相交,否则不执行操作.
－Find (x) //搜索操作；搜索单元素x所在的集合,并返回该集合的名字.
－UFSets (s) //构造函数。将并查集中s个元素初始化为s个只有一个单元素的子集合.
－对于并查集来说，每个集合用一棵树表示。
－集合中每个元素的元素名分别存放在树的结点中，此外，树的每一个结点还有一个指向其双亲结点的指针。
－设S1= {0, 6, 7, 8 }，S2= { 1, 4, 9 }，S3= { 2, 3, 5 }
－为简化讨论，忽略实际的集合名，仅用表示集合的树的根来标识集合。
－为此，采用树的双亲表示作为集合存储表示。集合元素的编号从0到n-1。其中n 是最大元素个数。在双亲表示中，第i 个数组元素代表包含集合元素i 的树结点。根结点的双亲为-1，表示集合中的元素个数。为了区别双亲指针信息( ≥0 )，集合元素个数信息用负数表示。下标
parent
集合S1, S2和S3的双亲表示:
S1 ∪S2的可能的表示方法
const int DefaultSize = 10;
class UFSets { //并查集的类定义
private:
int *parent;
int size;
public:
UFSets ( int s = DefaultSize );
~UFSets ( ) { delete [ ] parent; }
UFSets & operator = ( UFSets const & Value );//集合赋值
void Union ( int Root1, int Root2 );
int Find ( int x );
void UnionByHeight ( int Root1, int Root2 ); };
UFSets::UFSets ( int s ) { //构造函数
size = s;
parent = new int [size+1];
for ( int i = 0; i <= size; i++ ) parent[i] = -1;
}
unsigned int UFSets::Find ( int x ) { //搜索操作
if ( parent[x] <= 0 ) return x;
else return Find ( parent[x] );
}
void UFSets::Union ( int Root1, int Root2 ) { //并
parent[Root2] = Root1; //Root2指向Root1
}
Find和Union操作性能不好。假设最初n 个元素构成n 棵树组成的森林，parent[i] = -1。做处理Union(0, 1), Union(1, 2), …, Union(n-2, n-1)后，将产生如图所示的退化的树。
执行一次Union操作所需时间是O(1)，n-1次Union操作所需时间是O(n)。若再执行Find(0), Find(1), …, Find(n-1), 若被
搜索的元素为i，完成Find(i)操作需要时间为O(i)，完成n 次搜索需要的总时间将达到
Union操作的加权规则
为避免产生退化的树，改进方法是先判断两集合中元素的个数，如果以i 为根的树中的结点个数少于以j 为根的树中的结点个数，即parent[i] > parent[j]，则让j 成为i 的双亲，否则，让i成为j的双亲。此即Union的加权规则。
parent[0](== -4) < parent[4] (== -3)
void UFSets::WeightedUnion(int Root1, int Root2) {
//按Union的加权规则改进的算法
int temp = parent[Root1] + parent[Root2];
if ( parent[Root2] < parent[Root1] ) {
parent[Root1] = Root2; //Root2中结点数多
parent[Root2] = temp; //Root1指向Root2
}
else {
parent[Root2] = Root1; //Root1中结点数多
parent[Root1] = temp; //Root2指向Root1
}
}
使用加权规则得到的树
引题——亲戚（relation）
【问题描述】若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。（人数≤5000，亲戚关系≤5000，询问亲戚关系次数≤5000）。
【算法分析】
1. 算法1，构造图论模型。
用一个n*n的二维数组描述上面的图形，记忆各个点之间的关系。然后，只要判断给定的两个点是否连通则可知两个元素是否有“亲戚”关系。
但要实现上述算法，我们遇到两个困难：
（1）空间问题：需要n2的空间，而n高达5000！
（2）时间问题：每次判断连通性需要O(n)的处理。
该算法显然不理想。
并查集多用于图论问题的处理优化，我们看看并查集在这里的表现如何。
2. 算法2，并查集的简单处理。
我们把一个连通块看作一个集合，问题就转化为判断两个元素是否属于同一个集合。
假设一开始每个元素各自属于自己的一个集合，每次往图中加一条边a－b，就相当于合并了两个元素所在集合A和B，因为集合A中的元素用过边a－b可以到达集合B中的任意元素，反之亦然。
当然如果a和b本来就已经属于同一个集合了，那么a-b这条边就可以不用加了。
（1）具体操作：
①由此用某个元素所在树的根结点表示该元素所在的集合；
②判断两个元素时候属于同一个集合的时候，只需要判断他们所在树的根结点是否一样即可；
③也就是说，当我们合并两个集合的时候，只需要在两个根结点之间连边即可。
（2）元素的合并图示：
（3）判断元素是否属于同一集合：
用father[i]表示元素i的父亲结点，如刚才那个图所示：
faher[1]:=1；faher[2]:=1；faher[3]:=1；faher[4]:=5；faher[5]:=3
至此，我们用上述的算法已经解决了空间的问题，我们不再需要一个n2的空间来记录整张图的构造，只需要用一个记录数组记录每个结点属于的集合就可以了。
但是仔细思考不难发现，每次询问两个元素是否属于同一个集合我们最多还是需要O(n)的判断！
3. 算法3，并查集的路径压缩。
算法2的做法是指就是将元素的父亲结点指来指去的在指，当这课树是链的时候，可见判断两个元素是否属于同一集合需要O(n)的时间，于是路径压缩产生了作用。
路径压缩实际上是在找完根结点之后，在递归回来的时候顺便把路径上元素的父亲指针都指向根结点。
这就是说，我们在“合并5和3”的时候，不是简单地将5的父亲指向3，而是直接指向根节点1，由此我们得到了一个复杂度只是O(1)的算法。
〖程序清单〗
（1）初始化：
for i:=1 to n do father[i]:=i;
因为每个元素属于单独的一个集合，所以每个元素以自己作为根结点。
（2）寻找根结点编号并压缩路径：
function getfather(v : integer) : integer;
begin
if father[v]=v then exit(v);
father[v]:=getfather(father[v]);
getfather:=father[v];
end;
（3）合并两个集合：
proceudre merge(x, y : integer);
begin
x:=getfather(x);
y:=getfather(y);
father[x]:=y;
end;
（4）判断元素是否属于同一结合：
function judge(x, y : integer) : boolean;
begin
x:=getfaher(x);
y:=gefather(y);
if x=y then exit(true)
else exit(false);
end;
这个的引题已经完全阐述了并查集的基本操作和作用。
三、并查算法
通过对上面引题的分析，我们已经十分清楚——所谓并查集算法就是对不相交集合（disjoint set）进行如下两种操作：
（1）检索某元素属于哪个集合；
（2）合并两个集合。
我们最常用的数据结构是并查集的森林实现。也就是说，在森林中，每棵树代表一个集合，用树根来标识一个集合。有关树的形态在并查集中并不重要，重要的是每棵树里有那些元素。
1. 合并操作
为了把两个集合S1和S2并起来，只需要把S1的根的父亲设置为S2的根（或把S2的根的父亲设置为S1的根）就可以了。
这里有一个优化：让深度较小的树成为深度较大的树的子树，这样查找的次数就会少些。这个优化称为启发式合并。可以证明：这样做以后树的深度为O(logn)。即：在一个有n个元素的集合，我们将保证移动不超过logn次就可以找到目标。
【证明】我们合并一个有i个结点的集合和一个有j个结点的集合，我们设i≤j，我们在一个小的集合中增加一个被跟随的指针，但是他们现在在一个数量为i＋j的集合中。由于：
1+log i=log(i+i)<=log(i+j);
所以我们可以保证性质。
由于使用启发式合并算法以后树的深度为O(logn)，因此我们可以得出如下性质：启发式合并最多移动2logn次指针就可以决定两个事物是否想联系。
同时我们还可以得出另一个性质：启发式快速合并所得到的集合树，其深度不超过，其中n是集合S中的所有子集所含的成员数的总和。
【证明】我们可以用归纳法证明：
当i=1时，树中只有一个根节点，即深度为1
又|log2 1|+1=1所以正确。
假设i≤n－1时成立，尝试证明i＝n时成立。
不失一般性，可以假设此树是由含有m（1≤m≤n/2）个元素，根为j的树Sj，和含有n－m 个元素、根为k的树Sk合并而得到，并且，树j合并到树k，根是k。
（1）若合并前：子树Sj的深度＜子树Sk的深度
则合并后的树深度和Sk相同，深度不超过：
|log2(n-m)|+1
显然不超过|log2 n|+1；
（2）若合并前：子树Sj的深度≥子树Sk的深度
则合并后的树的深度为Sj的深度+1，即：
(|log2m|+1)+1=|log2(2m)|+1<=|log2n|+1
小结：实践告诉我们，上面所陈述的性质对于一个m条边n个事物的联系问题，最多执行mlogn次指令。我们只是增加了一点点额外的代码，我们就把程序的效率很大地提升了。大
量的实验可以告诉我们，启发式合并可以在线形时间内解答问题。更确切地说，这个算法运行时间的花费，很难再有更加明显的优秀、高效的算法了。
2. 查找操作
查找一个元素u也很简单，只需要顺着叶子到根结点的路径找到u所在的根结点，也就是确定了u所在的集合。
这里又有一个优化：找到u所在树的根v以后，把从u到v的路径上所有点的父亲都设置为v，这样也会减少查找次数。这个优化称作路径压缩（compresses paths）。
压缩路径可以有很多种方法，这里介绍两种最常用的方法：
（1）满路径压缩（full compresses paths）：这是一种极其简单但又很常用的方法。就是在添加另一个集合的时候，把所有遇到的结点都指向根节点。
（2）二分压缩路径（compresses paths by halving）：具体思想就是把当前的结点，跳过一个指向父亲的父亲，从6而使整个路径减半深度减半。这种办法比满路径压缩要快那么一点点。数据越大，当然区别就会越明显。
压缩路径的本质使路径深度更加地减小，从而使访问的时候速度增快，是一种很不错的优化。在使用路径压缩以后，由于深度经常性发生变化，因此我们不再使用深度作为合并操作的启发式函数值，而是使用一个新的rank数。刚建立的新集合的rank为0，以后当两个rank相同的树合并时，随便选一棵树作为新根，并把它的rank加1；否则rank大的树作为新根，两棵树的rank均不变。
3. 时间复杂度
并查集进行n次查找的时间复杂度是O(n )（执行n-1次合并和m≥n次查找）。其中是一个增长极其缓慢的函数，它是阿克曼函数（Ackermann Function）的某个反函数。它可以看作是小于5的。所以可以认为并查集的时间复杂度几乎是线性的。
通过上面的分析，我们可以得出：并查集适用于所有集合的合并与查找的操作，进一步还可以延伸到一些图论中判断两个元素是否属于同一个连通块时的操作。由于使用启发式合并和路径压缩技术，可以讲并查集的时间复杂度近似的看作O(1)，空间复杂度是O(N)，这样就将一个大规模的问题转变成空间极小、速度极快的简单操作。
本文来自CSDN博客，转载请标明出处：https://www.doczj.com/doc/bb16350437.html,/power721/archive/2009/10/16/4683604.aspx
POJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,p oj2255,poj3094) 初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序(poj1094) (5)二分图的最大匹配(匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) 三.数据结构. (1)串(poj1035,poj3080,poj1936) (2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299) (3)简单并查集的应用. (4)哈希表和二分查找等高效查找法(数的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503) (5)哈夫曼树(poj3253) (6)堆 (7)trie树(静态建树、动态建树) (poj2513) 四.简单搜索 (1)深度优先搜索(poj2488,poj3083,poj3009,poj1321,poj2251) (2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414) (3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129) 五.动态规划 (1)背包问题. (poj1837,poj1276) (2)型如下表的简单DP(可参考lrj的书page149): 1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533) 2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159) 3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题) 六.数学 (1)组合数学:
这个训练计划我也只是把我知道的知识点罗列出来而已. 其实acm还有很多方面的知识。 可能到acm生涯结束的时候还是无法把所有的知识都吃透 所以acm的知识能学多少算多少，知识重要的不是你知道的多，重要的是你能否熟练的运用他们！ 题目注意事项： zoj：https://www.doczj.com/doc/bb16350437.html,/ grid：https://www.doczj.com/doc/bb16350437.html,/ hdu：https://www.doczj.com/doc/bb16350437.html,/ zquoj：也就是我们的oj 一．数据机构基础。 请自学完数据结构书：2，3，4，6，7，9.1，9.2.1 9.3 10 这几章，带*号可以暂时掠过，以后再看。然后自行完成oj DS开头的题目。 注意栈队列这些数据结构一般不用像书本那样写得那么严谨。在acm中，往往因为时间关系，一般写成简单的模式：请参考附件：栈与队列acm中的简单实现.txt 其它数据结构请自行简化。 二．其他数据结构 1.trie树 请看附件trie树的相关附件或到网上搜索。注意自己写好和简化模版。 Trie树最好使用静态分配实现！ poj 3630 hdu 1251 2.并查集 Hdu：1558 1811 1829 1198 3.图论专题： 简单的说下图怎么存储。 图通常分为邻接表和邻接矩阵两种方式储存。 请先移步到数据结构书祥看这两种实现方式。 邻接表：我们知道要动态分配内存。这种方式有时会导致效率低下。我们可以模拟一下动态分配内存，详见附件静态分配。 这部分图论可参考 https://www.doczj.com/doc/bb16350437.html,/p-251720691.html 部分题目.这本书有讲解。 1.图的基本概念 poj：1659 2.图的遍历和活动问题 zoj：2110 1709 1649 2913 1060 2193 2412 1008 2165 1136 1361 1091 1083 poj：2935 1270 3687
信息学奥赛中的特殊数据结构——并查集 在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能采用一种全新的抽象的特殊数据结构——并查集来描述。 一、数学准备 首先，我们从数学的角度给出等价关系和等价类的定义： 定义1：如果集合S中的关系R是自反的，对称的，传递的，则称他为一个等价关系。 ——自反：x＝x； ——对称：若x＝y，则y＝x； ——传递：若x＝y、y＝z，则x＝z。 要求：x、y、z必须要同一个子集中。 定义2：如果R是集合S的等价关系。对于任何x∈S，由[x]R＝{y|y∈S and xRy}给出的集合[x]R S 称为由x∈S生成的一个R的等价类。 定义3：若R是集合S上的一个等价关系，则由这个等价关系可产生这个集合的唯一划 分。即可以按R将S划分为若干不相交的子集S 1，S 2 ，S 3 ，S 4 ，……，他们的并即为S，则这 些子集S i 变称为S的R等价类。 划分等价类的问题的提法是：要求对S作出符合某些等价性条件的等价类的划分，已知集合S及一系列的形如“x等价于y”的具体条件，要求给出S的等价类的划分，符合所列等价性的条件。（我们上面提到的联系，即可认为是一个等价关系，我们就是要将集合S划分成n个联系的子集，然后再判断x，y是否在一个联系子集中。） 二、引题——亲戚（relation） 【问题描述】若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。 规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。（人数≤5000，亲戚关系≤5000，询问亲戚关系次数≤5000）。 【算法分析】 1. 算法1，构造图论模型。
poj 1061 青蛙的约会 这题用的是解线性同余方程的方法，之前没接触到过，搜索资料后看到一个人的博客里面讲的很好就拷贝过来了。内容如下： 对于方程：ax≡b(mod m)，a，b，m都是整数，求解x 的值，这个就是线性同余方程。符号说明： mod表示：取模运算 ax≡b(mod m)表示：(ax - b) mod m = 0，即同余 gcd(a,b)表示：a和b的最大公约数 求解ax≡b(mod n)的原理：对于方程ax≡b(mod n)，存在ax + by = gcd(a,b)，x，y是整数。而ax≡b(mod n)的解可以由x，y来堆砌。具体做法如下： 第一个问题：求解gcd(a,b) 定理一：gcd(a,b) = gcd(b,a mod b) 欧几里德算法 int Euclid(int a,int b) { if(b == 0) return a; else return Euclid(b,mod(a,b)); } 附：取模运算 int mod(int a,int b) { if(a >= 0) return a % b; else return a % b + b; } 第二个问题：求解ax + by = gcd(a,b) 定理二：ax + by = gcd(a,b)= gcd(b,a mod b) = b * x' + (a mod b) * y' = b * x' + (a - a / b * b) * y' = a * y' + b * (x' - a / b * y') = a * x + b * y 则：x = y' y = x' - a / b * y' 以上内容转自https://www.doczj.com/doc/bb16350437.html,/redcastle/blog/item/934b232dbc40d336349bf7e4.html
题目来源：福州大学acm网站 代码：fpcdq 一、入门 熟悉ACM竞赛规则以及程序提交注意事项 例题： Problem 1000 A+B Problem Time Limit: 1000 mSec Memory Limit : 32768 KB Problem Description Calculate a + b. Input The input will consist of a series of pairs of integers a and b,separated by a space, one pair of integers per line. Output For each pair of input integers a and b you should output the sum of a and b in one line,and with one line of output for each line in input. Sample Input 1 5 2 3 Sample Output 6 5
My answer： #include
第一章：绪论 1．数据结构的基本概念和术语 ?数据、数据元素、数据项、数据对象、数据结构等基本概念 ?数据结构的逻辑结构，存储结构及数据运算的含义及其相互关系 ?数据结构的四种逻辑结构及四种常用的存储表示方法 2．算法的描述和分析。 ?无穷大阶的几种描述方法的区别 ?算法特征及其评价标准 ?算法的时间复杂度和空间复杂度的概念 ?几种常见复杂度的好坏程度 ?就（原）地算法的含义 ?算法描述和算法分析的方法 1. 设n是偶数，试计算运行下列程序段后m的值，并给出该程序段的时间复杂度。 m=0; for (i=1; i<=n; i++) for (j=2*i; j<=n; j++) m=m+1; 2. 下列算法对一n位二进制数加1，假如无溢出，该算法在最坏情况下时间复杂度是什么？并分析它的平均时间复杂度。 void func (int A[n]) //A[n]中每个元素取值0或1 {inti = n; while (A[i] == 1) { A[i] = 0； i-} A[i]=1；} 3. 调用下列函数f(n) 回答下列问题: （1）试给出f(n)值的大小，并写出f(n) 值的推导过程; （2）假定n= 5，试指出f(5)值的大小和执行f(5)时的输出结果。 int f(int n) {inti, j，k, sum= 0; for(i=1; i 数据结构与算法 课程设计报告 课程设计题目：并查集检查网络 专业班级：信息与计算科学1001班 姓名：学号： 设计室号： 设计时间： 2011-12-29 批阅时间：指导教师：成绩： 《数据结构与算法》课程设计报告 (2) 一、课题：并查集检查网络 (3) 1.题目要求： (3) 2.输入要求： (3) 3.输出要求： (3) 二、并查集操作 (4) 1.Creat() (4) 2.find（int e） (4) 3.hebin(int A ,int B) (4) 三、并查集的优化 (5) 1．路径压缩 (5) 2.启发式合并 (6) 四．问题实现 (6) 五．数据显示： (10) 《数据结构与算法》课程设计报告 姓名： 学号： 专业： 一、课题：并查集检查网络 1.题目要求： 给定一个计算机网络以及机器间的双向连线列表，每一条连线允许两端的计算机进行直接的文件传输，其他计算机间若存在一条连通路径，也可以进行间接的文件传输。 请写出程序判断：任意指定两台计算机，它们之间是否可以进行文件传输。 2.输入要求： 输入若干测试数据组成。 对于每一组测试，第1行包含一个整数N（≤10000），即网络中计算机的总台数，因而每台计算机可用1到N之间的一个正整数表示。 接下来的几行输入格式为I C1 C2或者C或者C C1C2或者S，其中C1和C2是两台计算机的序号，I表示在C1和C2间输入一条连线，C表示检查C1和C2间是否可以传输文件，S表示该组测试结束。当N为0时，表示全部测试结束，不要对该数据做任何处理。 3.输出要求： 对每一组C开头的测试，检查C1和C2间是否可以传输文件，若可以，则在一行中输出“yes”，否则输出“no”。当读到S时，检查整个网络。若网络中任意两机器间都可以传输文件，则在一行中输出“The network is connected.”，否则输出“There are k components.”,其中k是网络中连通集的个数。两组测试数据之间请输出一空行分隔 1、POJ 1029 False coin Slyar:又是假币判断问题，跟POJ1013类似，不过这个题用1013那个算法W A了...后来换了种枚举的算法才过...思路就是假币应该在每个不等式中都出现，最后只要看哪个硬币出现的次数和不等式出现的次数相同，如果这个硬币唯一，那它就是确认的假币。 #include r[t[i]] = 1; } } /* 左轻右重*/ else if (sign == '<') { total++; for (int i = 0; i < p; i++) { w[t[i]]--; } for (int i = p; i < 2 * p; i++) { w[t[i]]++; } } /* 左重右轻*/ else if (sign == '>') { total++; for (int i = 0; i < p; i++) { w[t[i]]++; } for (int i = p; i < 2 * p; i++) { w[t[i]]--; } } } /* 假币在不等式中每次都应该出现*/ int count = 0, pos = 0; for (int i = 1; i <= n; i++) { if (r[i]) { continue; } /* 找出每次都出现的"假币" */ if (w[i] == total || w[i] == - total) { count++; pos = i; 1、POJ 2249 Binomial Showdown 组合数学。 高精度，也可把分子分母的数组进行两两约分 #include 有一个溢出问题；比如64位全是p的序列，那么max会溢出，值为-1；同理min在全是n 时也会溢出，为1；显然是max>=0,min<=1,溢出时产生异常，依次可以判断； ②是否是最大限和最小限之间的数都能表示呢？ 都可以，而且能够表示的数是2^k个，这个原始2进制是一样的；因为每个位上要么是0，要么是1，而且每个位上的权重唯一的，不能通过其他位的01组合获得；最后，我们就可以仿照原始二进制来算在类2进制下的表示；不断求N的二进制最后一位和右移；如果取余是1，则该位上一定是1，如果该位对于字母为‘n’，则高位应该再加1；这里对2取余可能会出错，因为对于负数，补码的表示，最后一位一定是和原码一样的每次的右移后(有时需先加1）补码表示正好符合要求（可找实例验证）； #include 自己刷的题 这是我在杭电做题的记录，希望我的分享对你有帮助！！！ 1001 Sum Problem***********************************************************1 1089 A+B for Input-Output Practice (I)********************************2 1090 A+B for Input-Output Practice (II)********************************5 1091A+B for Input-Output Practice (III)****************************************7 1092A+B for Input-Output Practice (IV)********************************8 1093 A+B for Input-Output Practice (V)********************************10 1094 A+B for Input-Output Practice (VI)***************************************12 1095A+B for Input-Output Practice (VII)*******************************13 1096 A+B for Input-Output Practice (VIII)******************************15 How to Type***************************************************************16 1001 Sum Problem Problem Description Hey, welcome to HDOJ(Hangzhou Dianzi University Online Judge). In this problem, your task is to calculate SUM(n) = 1 + 2 + 3 + ... + n. Input The input will consist of a series of integers n, one integer per line. Output For each case, output SUM(n) in one line, followed by a blank line. You may assume the result will be in the range of 32-bit signed integer. 1111111杭电： 1000 A + B Problem (4) 1001 Sum Problem (5) 1002 A + B Problem II (6) 1005 Number Sequence (8) 1008 Elevator (9) 1009 FatMouse' Trade (11) 1021 Fibonacci Again (13) 1089 A+B for Input-Output Practice (I) (14) 1090 A+B for Input-Output Practice (II) (15) 1091 A+B for Input-Output Practice (III) (16) 1092 A+B for Input-Output Practice (IV) (17) 1093 A+B for Input-Output Practice (V) (18) 1094 A+B for Input-Output Practice (VI) (20) 1095 A+B for Input-Output Practice (VII) (21) 1096 A+B for Input-Output Practice (VIII) (22) 1176 免费馅饼 (23) 1204 糖果大战 (25) 1213 How Many Tables (26) 2000 ASCII码排序 (32) 2001 计算两点间的距离 (34) 2002 计算球体积 (35) 2003 求绝对值 (36) 2004 成绩转换 (37) 2005 第几天？ (38) 2006 求奇数的乘积 (40) 2007 平方和与立方和 (41) 2008 数值统计 (42) 2009 求数列的和 (43) 2010 水仙花数 (44) 2011 多项式求和 (46) 2012 素数判定 (47) 2014 青年歌手大奖赛_评委会打分 (49) 2015 偶数求和 (50) 2016 数据的交换输出 (52) 2017 字符串统计 (54) 2019 数列有序! (55) 2020 绝对值排序 (56) 2021 发工资咯：） (58) 2033 人见人爱A+B (59) 2037 今年暑假不AC (61) 2039 三角形 (63) 2040 亲和数 (64) 第一章数据结构基本概念 1、基本概念：理解什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系。 2、面向对象概念：理解什么是数据类型、抽象数据类型、数据抽象和信息隐蔽原则。了解什么是面向对象。由于目前关于这个问题有许多说法，我们采用了一种最流行的说法，即Coad与Yourdon 给出的定义：面向对象= 对象+ 类+ 继承+ 通信。 要点： ·抽象数据类型的封装性 ·面向对象系统结构的稳定性 ·面向对象方法着眼点在于应用问题所涉及的对象 3、数据结构的抽象层次：理解用对象类表示的各种数据结构 4、算法与算法分析：理解算法的定义、算法的特性、算法的时间代价、算法的空间代价。 要点：·算法与程序的不同之处需要从算法的特性来解释 ·算法的正确性是最主要的要求 ·算法的可读性是必须考虑的 ·程序的程序步数的计算与算法的事前估计 ·程序的时间代价是指算法的渐进时间复杂性度量 第二章数组 1、作为抽象数据类型的数组：数组的定义、数组的按行顺序存储与按列顺序存储 要点： ·数组元素的存放地址计算 2、顺序表：顺序表的定义、搜索、插入与删除 要点： ·顺序表搜索算法、平均比较次数的计算 ·插入与删除算法、平均移动次数的计算 3、多项式：多项式的定义 4、字符串：字符串的定义及其操作的实现 要点： ·串重载操作的定义与实现 第三章链接表 1、单链表：单链表定义、相应操作的实现、单链表的游标类。 要点： ·单链表的两种定义方式（复合方式与嵌套方式） ·单链表的搜索算法与插入、删除算法 ·单链表的递归与迭代算法 2、循环链表：单链表与循环链表的异同 3、双向链表：双向链表的搜索、插入与删除算法、链表带表头结点的优点 4、多项式的链接表示 第四章栈与队列 1、栈：栈的特性、栈的基本运算 要点： ·栈的数组实现、栈的链表实现 ·栈满及栈空条件、抽象数据类型中的先决条件与后置条件 2、栈的应用：用后缀表示计算表达式，中缀表示改后缀表示 3、队列：队列的特性、队列的基本运算 要点： ·队列的数组实现：循环队列中队头与队尾指针的表示，队满及队空条件·队列的链表实现：链式队列中的队头与队尾指针的表示、 4、双向队列：双向队列的插入与删除算法 5、优先级队列：优先级队列的插入与删除算法 第五章递归与广义表 1、递归：递归的定义、递归的数据结构、递归问题用递归过程求解 要点：·链表是递归的数据结构，可用递归过程求解有关链表的问题 2、递归实现时栈的应用 要点：·递归的分层（树形）表示：递归树 1、公约数和公倍数 https://www.doczj.com/doc/bb16350437.html,/JudgeOnline/problem.php?pid=40 这道题目是非常基础的题目，在学习了欧几里德算法之后，应该很好就能做的出来了。注意两个数的最小公倍数和最大公约数之间有关系为： a*b=gcd(a,b)*lcm(a,b); 代码如下： #include ?????≡≡≡)33(mod ) 28(mod )23(mod d n e n p n 那么找到k1、k2、k3满足： k1：k1%23==0&&k1%28==0&&k1%33==1 k2：k2%33==0&&k2%28==0&&k2%23==1 k3：k3%33==0&&k3%23==0&&k3%28==1 则n=k2*p+k3*e+k1*i+k*21252； 代码如下： #include 高级数据结构设计－－并查集及实现学习笔记（有趣篇） 并查集的程序设计： 为了解释并查集的原理，我将举一个更有趣的例子。 话说江湖上散落着各式各样的大侠，有上千个之多。他们没有什么正当职业，整天背着剑在外面走来走去，碰到和自己不是一路人的，就免不了要打一架。但大侠们有一个优点就是讲义气，绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”，只要是能通过朋友关系串联起来的，不管拐了多少个弯，都认为是自己人。这样一来，江湖上就形成了一个一个的群落，通过两两之间的朋友关系串联起来。而不在同一个群落的人，无论如何都无法通过朋友关系连起来，于是就可以放心往死了打。但是两个原本互不相识的人，如何判断是否属于一个朋友圈呢？我们可以在每个朋友圈内推举出一个比较有名望的人，作为该圈子的代表人物，这样，每个圈子就可以这样命名“齐达内朋友之队”“罗纳尔多朋友之队”…… 两人只要互相对一下自己的队长是不是同一个人，就可以确定敌友关系了。 但是还有问题啊，大侠们只知道自己直接的朋友是谁，很多人压根就不认识队长，要判断自己的队长是谁，只能漫无目的的通过朋友的朋友关系问下去：“你是不是队长？你是不是队长？”这样一来，队长面子上挂不住了，而且效率太低，还有可能陷入无限循环中。于是队长下令，重新组队。队内所有人实行分等级制度，形成树状结构，我队长就是根节点，下面分别是二级队员、三级队员。每个人只要记住自己的上级是谁就行了。遇到判断敌友的时候，只要一层层向上问，直到最高层，就可以在短时间内确定队长是谁了。由于我们关心的只是两个人之间是否连通，至于他们是如何连通的，以及每个圈子内部的结构是怎样的，甚至队长是谁，并不重要。所以我们可以放任队长随意重新组队，只要不搞错敌友关系就好了。于是，门派产生了。 下面我们来看并查集的实现。 int pre[1000]; 这个数组，记录了每个大侠的上级是谁。大侠们从1或者0开始编号（依据题意而定），pre[15]=3就表示15号大侠的上级是3号大侠。如果一个人的上级就是他自己，那说明他就是掌门人了，查找到此为止。也有孤家寡人自成一派的，比如欧阳锋，那么他的上级就是他自己。每个人都只认自己的上级。比如胡青牛同学只知道自己的上级是杨左使。张无忌是谁？不认识！要想知道自己的掌门是谁，只能一级级查上去。find这个函数就是找掌门用的，意义再清楚不过了（路径压缩算法先不论，后面再说）。 取石子游戏 Time Limit:1S Memory Limit:1000K Total Submit:505 Accepted:90 Description 有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。 Input 输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a 和b，表示两堆石子的数目，a和b都不大于1,000,000,000。 Output 输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。 Sample Input 2 1 8 4 4 7 Sample Output 1 跳蚤 Time Limit:1S Memory Limit:1000K Total Submit:198 Accepted:44 Description Z城市居住着很多只跳蚤。在Z城市周六生活频道有一个娱乐节目。一只跳蚤将被请上一个高空钢丝的正中央。钢丝很长，可以看作是无限长。节目主持人会给该跳蚤发一张卡片。卡片上写有N+1个自然数。其中最后一个是M，而前N个数都不超过M，卡片上允许有相同的数字。跳蚤每次可以从卡片上任意选择一个自然数S，然后向左，或向右跳S个单位长度。而他最终的任务是跳到距离他左边一个单位长度的地方，并捡起位于那里的礼物。 比如当N=2，M=18时，持有卡片(10, 15, 18)的跳蚤，就可以完成任务：他可以先向左跳10个单位长度，然后再连向左跳3次，每次15个单位长度，最后再向右连跳3次，每次18个单位长度。而持有卡片(12, 15, 18)的跳蚤，则怎么也不可能跳到距他左边一个单位长度的地方。 当确定N和M后，显然一共有M^N张不同的卡片。现在的问题是，在这所有的卡片中，有多少张可以完成任务。 Input 两个整数N和M(N <= 15 , M <= 100000000)。 Output 可以完成任务的卡片数。 Sample Input 2 4 Sample Output 12 Hint 转载自South_wind的专栏 常见的数据结构运用总结 考虑到Obsidian三个成员的擅长领域，这段时间都在做杂题，算是学习各种算法吧，趁现在休息的时间，而且大家马上要备战今年的比赛了，写写自己专攻方面的一些心得吧 扯开线段树、平衡树这些中高级的东西，先说说基础的数据结构 栈 算是代码量最小的数据结构？出栈进栈都只有一句话而已 常见用途： 消去一个序列中的相同元素(做法大家应该都知道了吧，见过很多次了) 维护一个单调的序列(所谓的单调栈，dp的决策单调？) 表达式求值(经典的栈运用，如果使用的很熟悉的话，可以处理一元、二元运算，不过最近没见过类似的题目了) 用于辅助其他算法(计算几何中的求凸包) 队列 队列应该还是很常见的数据结构了，如果专攻图论的话，spfa应该是写烂了的 这里说到的队列，是狭义的普通的队列和循环队列，不包括后面讲的一些变形 注意循环队列的写法，尽量不要使用取模运算，不然的话，遇到不厚道的出题者，可以把取模的循环队列卡到死 常见用途： 主要用于辅助其他算法，比如说spfa，bfs等(建议习惯用stl的孩子手写queue，毕竟就几行代码而已，偷懒会付出代价的。。。) 双端队列 如果写dp写的多的话，这个东西应该还是算是比较基础的东西了，双端队列多用于维护一个满足单调性的队列 还是建议手写，stl的deque使用块状链表写的，那东西的复杂度是O(Nsqrt(N))的，不要被迷惑了。 常见用途： dp的单调性优化，包括单调队列优化和斜率优化，都要用到这个结构 计算几何中的算法优化，比如半平面交 树的分治问题中利用单调队列减少转移复杂度 链表Dancing Links 写图论的不要告诉我不会写这货，链表可以写单双向，循环非循环的，高级点儿的可以考虑十字链表，麻花链表 不过链表可以说是树形结构的基础，如果这个掌握的不好，那么树形结构写起来就会很纠结 链表的优势在于可以O(1)的插入删除，如果要求插入的位置只是在序列的两端的话，这个数据结构是最方便的了(无视双端队列) hash表就是用链表实现的，熟悉hash的同学可以试试看怎么使你的hash效率提高 数论50题 1．由1，3，4，5，7，8这六个数字所组成的六位数中，能被11整除的最大的数是多少？ 【分析】各位数字和为1+3+4+5+7+8=28 所以偶数位和奇数位上数字和均为14 为了使得该数最大，首位必须是8，第2位是7，14-8=6 那么第3位一定是5，第5位为1 该数最大为875413。 2．请用1，2，5，7，8，9这六个数字（每个数字至多用一次）来组成一个五位数，使得它能被75整除，并求出这样的五位数有几个？ 【分析】75=3×25 若被3整除，则各位数字和是3的倍数，1+2+5+7+8+9=32 所以应该去掉一个被3除余2的，因此要么去掉2要么去掉8 先任给一个去掉8的，17925即满足要求 1）若去掉8 则末2位要么是25要么是75，前3位则任意排，有3！=6种排法 因此若去掉8则有2*6=12个满足要求的数 2）若去掉2 则末2位只能是75，前3位任意排，有6种排法 所以有6个满足要求 综上所述，满足要求的五位数有18个。 3．已知道六位数20□279是13的倍数，求□中的数字是几？ 【分析】根据被13整除的判别方法，用末三位减去前面的部分得到一个两位数，十位是7，个位是（9-□），它应该是13的倍数，因为13|78,所以9-□=8 □中的数字是1 4．某自然数，它可以表示成9个连续自然数的和，又可以表示成10个连续自然数的和，还可以表示成11个连续自然数的和，那么符合以上条件的最小自然数是？（2005全国小学数学奥赛） 【分析】可以表示成连续9个自然数的和说明该数能被9整除，可以表示成连续10个自然数的和说明该数能被5整除，可表示成连续11个自然数的和说明该数能被11整除 因此该数是[9,5,11]=495，因此符合条件的最小自然数是495。 5．一次考试中，某班同学有考了优秀，考了良好，考了及格，剩下的人不及格，已知该班同学的人数不超过50，求有多少人不及格？ 【分析】乍一看这应该是一个分数应用题，但实际上用到的却是数论的知识，由于人数必须是整数，所以该班同学的人数必须同时是2，3，7的倍数，也就是42的倍数，又因为人数不超过50，所以只能是42人，因此不及格的人数为（1---）×42=1人 6．（1）从1到3998这3998个自然数中，有多少个能被4整除？ （2）从1到3998这3998个自然数中，有多少个数的各位数字之和能被4整除？ （第14届迎春杯考题） 【分析】（1）3998/4=999….6所以1-3998中有996个能被4整除的 （2）考虑数字和，如果一个一个找规律我们会发现规律是不存在的 因此我们考虑分组的方法 我们补充2个数，0000和3999，此外所有的一位两位三位数都在前面加上0补足4位 然后对这4000个数做如下分组 并查集。 1、概念： 如果：给出各个元素之间的联系，要求将这些元素分成几个集合，每个集合中的元素直接或间接有联系。在这类问题中主要涉及的是对集合的合并和查找，因此将这种集合称为并查集。并查集是一种树型的数据结构，它是一个集合，这个集合的元素也是集合，常常在使用中以森林来表示。 2、并查集的主要操作： ①合并两个不相交集合 ②判断两个元素是否属于同一集合 初步分析觉得本题是一个图论中判断两个点是否在同一个连通子图中的问题。 1、识别水果模9第1题 在海上漂泊了249天后，由于食物和水都已消耗光了，三人已是筋疲力尽。终于，在第250天的早晨，一个隐隐约约的黑点在远处出现了，是一个小岛，三大护法高兴的几乎要跳起来。于是下令舰队全速前进，驶向小岛。 在登陆后，他们才知道，这就是著名的移花岛，岛上有三位女神：dp女神、涓涓女神和紫晶女神。由于三大女神与holy_one的关系不错，因此高兴地接待了他们三人。由于看到三人饥渴难耐，负责岛上水果的涓涓女神便带他们去了果园。 果园里水果丰富，共有n个，它们的标号为1~n，但有些水果是有毒，而且水果与水果之间有藤蔓相连，如果一个水果有毒，那么所有与它相连的所有水果都是有毒的。其中m 个水果上面会贴着一个标签，从标签上可以看出这个水果是否有毒。当然，如果这个水果的标签显示无毒，但它与有毒的水果相连，那它也是有毒的。 为帮助三人尽快吃到水果，涓涓女神给了他们一张毒物字典，只有通过字典上的对应关系翻译后，才能知道水果是否有毒。转化后的名称中包含'poison'，即表示这个水果有毒。输入： 第一行，字符串a 第二行，字符串b a串和b串长度都是26，a[i]到b[i]表示两个字母的对应关系。注意，对应关系是单向的。两个整数n和m。 以下m行， 每行第一个数是水果的标号k，后面是第k个水果的标签s k和s之间有空格分隔开 一个整数p。 以下p行，每行两个整数x,y表示第x个水果和第y个水果之间有藤蔓相连 输出： 无毒的水果的个数s:array[‘a’..’z’] of char; 样例输入： abcdefghijklmnopqrstuvwxyz s1 s[s1[i]]:=s2[i] abcdefghijklmnopqrstuvwxyz s2 3 2 1 poison x[i]:=x[i] or x[j] 2 viking 1 1 3 1 4并查集检查网络课程设计报告
ACM必做50题——模拟
ACM必做50题——数学
杭电acm部分题目及答案答案
整理出ACM所有题目及答案
数据结构复习要点
ACM数论方面十道基础题目详解
并查集超级易懂讲解
ACM竞赛试题集锦
数据结构总结
数论50题
并查集2
相关主题
文本预览