acm并查集基础题目
poj 1861 Network
题意:
Andrew要在公司里用电缆连接n个集线器，要用总长度最小的线连接，求出其中最长的那根电缆。
也就是告诉n个顶点，m条边，求最小生成树的最大边。并把生成树的每条边输出来，Sample 里面的输出有问题，应该是三条。
给出节点个数m和边数n，下面n行给出边(x,y)以及权值w。输出第一行为最小生成树中的最大边权值，第二行为一个可行生成树方案的边数k，下面k行为可行生成树的k条边。题目是Special Judge，意思就是不具有唯一解，可能有多解，样例输出为以下结果也可算对。1
3
1 3
2 4
2 3
一样按照Kruskal解题即可，结果虽然不唯一，但是最小生成树一定是可行解之一。将边加入生成树时记录最大权值和边信息然后输出即可。
#include
#include
#define MAX 15001
/* 定义边(x,y)，权为w */
typedef struct
{
int x, y;
int w;
}edge;
edge e[MAX];
edge v[MAX];
/* rank[x]表示x的秩 */
int rank[MAX];
/* father[x]表示x的父节点 */
int father[MAX];
/* 比较函数，按权值非降序排序 */
int cmp(const void *a, const void *b)
{
return (*(edge *)a).w - (*(edge *)b).w;
}
/* 初始化集合 */
void Make_Set(int x)
{
father[x] = x;
rank[x] = 0;
}
/* 查找x元素所在的集合,回溯时压缩路径 */ int Find_Set(int x)
{
if (x != father[x])
{
father[x] = Find_Set(father[x]);
}
return father[x];
}
/* 合并x,y所在的集合 */
void Union(int x, int y)
{
if (x == y) return;
if (rank[x] > rank[y])
{
father[y] = x;
}
else
{
if (rank[x] == rank[y])
{
rank[y]++;
}
father[x] = y;
}
}
int main()
{
int i, j, m, n, k, max;
int x, y;
scanf("%d%d", &m, &n);
/* 读入边数据 */
for (i = 0; i < n; i++)
{
scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].w);
}
/* 初始化集合 */
for (i = 0; i < m; i++)
{
Make_Set(i);
}
/* 对边排序 */
qsort(e, n, sizeof(edge), cmp);
k = 0;
max = 0;
for (i = 0; i < n; i++)
{
x = Find_Set(e[i].x);
y = Find_Set(e[i].y);
if (x != y)
{
k++;
Union(x, y);
/* 保存边信息 */
v[k] = e[i];
/* 记录最大权值 */
if (max < e[i].w) max = e[i].w;
}
}
/* 输出结果 */
printf("%d\n", max);
printf("%d\n", k);
for (i = 1; i <= k; i++)
{
printf("%d %d\n", v[i].x, v[i].y);
}
//system("pause");
return 0;
}
poj 1182 食物链
建议：做此题之前先做 poj 2524 和 poj 1611。这两道题都是并查集的基础应用。
关键词：并查集相对关系
思路：（用一个并查集就够了，同时对每个节点保持其到根结点的相对类别偏移量）
1.p[x]表示x的根结点。r[x]表示p[x]与x的关系。r[x] == 0 表示p[x]与x同类；1表示p[x]吃x；2表示x吃p[x]。
2.怎样划分一个集合呢？
注意，这里不是根据x与p[x]是否是同类来划分。而是根据“x与p[x]能否确定两者之间的关系”来划分，若能确定x与p[x]的关系，则它们同属一个集合。
3.怎样判断一句话是不是假话？
假设已读入 D , X , Y , 先利用find_set()函数得到X , Y 所在集合的代表元素 rx , ry ,若它们在同一集合（即 rx == ry ）则可以判断这句话的真伪（据 2. ）.
若 D == 1 而 r[X] != r[Y] 则此话为假。（D == 1 表示X与Y为同类，而从r[X] != r[Y]可以推出 X 与 Y 不同类。矛盾。）
若 D == 2 而 r[X] == r[Y] （X 与Y为同类）或者r[X] == ( r[Y] + 1 ) % 3 （Y吃X ）则此话为假。
4.上个问题中 r[X] == ( r[Y] + 1 ) % 3这个式子怎样推来？
假设有Y吃X，那么r[X]和r[Y]的值是怎样的？
我们来列举一下: r[X] = 0 && r[Y] = 2
r[X] = 1 && r[Y] = 0
r[X] = 2 && r[Y] = 1
稍微观察一下就知道r[X] = ( r[Y] + 1 ) % 3;
事实上，对于上个问题有更一般的判断方法：
若 ( r[Y] - r[X] + 3 ) % 3 != D - 1 ，则此话为假。（来自poj 1182中的Discuss ）5.其他注意事项:
在union_set( rx , ry )过程中若将S(ry)合并到S(rx)上，则相应的r[ry]必须更新为ry相对于rx的关系。怎样得到更新关系式？
#include
using namespace std;
void make_set( int [] , int [] , int );
int find_set( int [] , int [] , int );
void union_set( int [] , int [] , int , int , int , int , int );
int main()
{
int p[50001];
int r[50001];
int n, k;
int d, x, y, rx, ry;
int fs;
scanf( "%d%d" , &n , &k );
make_set( p , r , n );
fs = 0;
while ( k-- > 0 )
{
scanf( "%d%d%d" , &d , &x , &y );
if ( x > n || y > n || ( d == 2 && x == y ) )
{
fs++;
continue;
}
rx = find_set( p , r , x );
ry = find_set( p , r , y );
if ( rx == ry ) //可以确定X与Y的关系，也就可以判断此话的真伪。 if ( d == 1 && r[x] != r[y] )
fs++;
else
{
if ( d== 2 && r[x] != ( r[y] + 2 ) % 3 )
fs++;
}
else
union_set( p , r , rx , ry , x , y , d );
}
cout << fs << endl;
return 0;
}
void make_set( int p[] , int r[] , int n )
{
for ( int i = 0 ; i <= n ; i++ )
{
p[i] = i;
r[i] = 0;
}
}
int find_set( int p[] , int r[] , int x )
{
if ( p[x] == x ) return x;
int temp_px = p[x];
p[x] = find_set( p , r , p[x] ); //递归寻找元素x所在集合的代表元素 rx r[x] = ( r[temp_px] + r[x] ) % 3; //important. 更新r[]数组中x与代表元素的相对关系。更新原因:代表元素在
//union_set操作中被改变了。至于这个式子的推得.可以枚举rx与p[x], p[x] //与x的关系，然后观察得到。更好的方法是向量运算。来自poj 1182 Discuss return p[x];
}
void union_set( int p[] , int r[] , int rx , int ry , int x , int y , int d ) {
p[ry] = rx;
r[ry] = ( r[x] - r[y] + 2 + d ) % 3; //同上。这两个关系的推得实际上是这道题的关键所在。
}
poj 1308 Is It A Tree?
题意：
给出一系列节点对，判断是不是树。是树的条件是：只有一个根节点，没有指向根节点的边，除了根节点每个节点都只有一条边指向它，只有一条唯一的路从根节点到其他各个节点。空树是一棵树。森林不是树。
思路：
这么多条件总结起来其实只要判断：①.树的节点数v是不是等于边的条数u+1，②判断有没有环，③考虑空树的情况就可以了。主要是数顶点，我是把所有节点存在数组num里，再排个序，在找出不同的个数，再跟边比较。第二种用到了并查集，一条边一条边加进去，看是否有祖先节点相同的情况，有的话就是存在环。第三种最简单，输入只有两个0的话，直接判断是棵树。
#include
#include
#include
#define N 100
typedef struct
{
int x, y;
}node;
node nodes[N];
int t, parent[N], rank[N], num[N], count;
int find(int x)
{
int y, z;
y = x;
while(parent[y]!= y)
y = parent[y];
while(x != y)
{
z = parent[x];
parent[x] = y;
x = z;
}
return y;
}
void _union(int x, int y)
{
if(rank[x] > rank[y])
parent[y] = x;
else {
if(rank[x] == rank[y])
rank[y]++;
parent[x] = y;
}
}
void fun(int n)
{
int i, x, y;
int ok = 0;
if(count != n+1)
ok = 1;
else
{
for(i=0; i { x = find(nodes[i].x); y = find(nodes[i].y); if(x == y) { ok = 1; break; } else _union(nodes[i].x, nodes[i].y); } } t++; printf("Case %d is not a tree.\n", t); else printf("Case %d is a tree.\n", t); } int cmp(const void *p, const void *q) { return *(int *)p > *(int *)q ? 1 : -1; } int main() { int i, j, k, s; int a, b, c; k = 0; s = 0; while(scanf("%d%d", &a, &b)) { if(a == -1 && b == -1) break; if(!a && !b) { if(!k) { t++; printf("Case %d is a tree.\n", t); continue; } qsort(num, s, sizeof(num[0]), cmp); count = 1; c = num[0]; for(i=1; i { if(num[i] != c) { count ++; c = num[i]; } } fun(k); k = 0; s = 0; memset(num, 0, sizeof(num)); memset(nodes, 0, sizeof(nodes)); memset(rank, 0, sizeof(rank)); continue; nodes[k].x = a; nodes[k].y = b; parent[a] = a; parent[b] = b; num[s++] = a; num[s++] = b; k++; } return 0; } poj 2524 Ubiquitous Religions(并查集) 题目大意： 本题主要是给定一个图的点数和相应的边，判断一个图有多少堆 解题思路： 此题主要应用并查集来处理即先把每个节点的根节点初始化为自己，并将每个节点看成一棵树每读进一条边时，判断其根节点是否相等，如果不相等就两节点的根节点归一。并将树的数目减一，后有几棵树就有几堆。 注意事项： 当输入数据比较多时，用scanf()比用cin输入更省时。 #include #include #define MAXN 1000000 int set[MAXN],rank[MAXN]; int FindSet(int x) { if(set[x]!=x) set[x]=FindSet(set[x]); return set[x]; } void MakeSet(int x) { set[x]=x; rank[x]=0; } void Link(int a,int b) { if(rank[a]>rank[b]) set[b]=a; else if(rank[a] set[a]=b; else { set[a]=b; rank[b]++; } } void Union(int a,int b) { Link(FindSet(a),FindSet(b)); } int main() { int point1,point2; int n,m,num,cas=0; int i; while(scanf("%d%d",&n,&m),n!=0) { cas++; num=n; for(i=1;i<=n;i++) MakeSet(i); for(i=0;i { scanf("%d%d",&point1,&point2); if(FindSet(point1)!=FindSet(point2)) { Union(point1,point2); num--; } } printf("Case %d: %d\n",cas,num); } return 0; } ACM contests https://www.wendangku.net/doc/f512029976.html, 中庸之道(一) Time Limit: 1000 ms Memory Limit: 65535 kB Solved: 306 Tried: 1491 Description 读入三个整数a、b、c，找出中间数并输出。若有两个数相同，最大数作为中间数。Input 有多组测试数据。输入的第一行是整数T（0 } return 0; } 或者 #include 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)组合数学: 信息学奥赛中的特殊数据结构——并查集 在一些有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，构造图论模型。 1、装箱问题：给定大小为S1,…,Sn的n个物件，其中0＜Si≤1，寻找能够装进所有这些物件的最少数量的箱盒，每个箱盒容量为1。(提示：贪心法求解。) 2、已知一个包含n个元素的整型数组和一个整数K。试用O（NlogN）算法解决这样的问题：确定数组中是否存在两个数，它们的和等于给定的数K。一个数可以被使用两次。 例如，如果输入是8，5，2，7而K是12，则答案为yes（5和7）。 输入： 8 5 2 7 12 输出： yes 3、已知有2n个元素的无序数组a，试用O（n）算法将这2n个元素分别放入大小均为n的数组b和c。使得数组b中的所有元素均小于数组c中的任意元素。 输入： 5 7 10 4 2 6 9 1 8 3 5 输出： 4 2 1 3 5 7 10 6 9 8 （注意：输入第一行为1/2数组a的大小，第二行为数组a中的元素，输出时b、c数组中元素顺序不一定与示例一致） 4、令A为元素是0和1的N行N列矩阵。A的子矩阵S由形成方阵的任意一组相邻项组成。设计一种O（n2）算法，确定A中的全为1的最大子矩阵的阶数。 输入：（可以程序中初始化） 1 0 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 1 0 1 0 1 1 1 1 0 0 1 0 1 1 1 1 0 0 0 0 1 1 1 1 0 输出： 4 （输入：一个矩阵，输出：全为1的最大子矩阵阶数） (提示：动态规划解题。) 5、输入一批数据{34，27，56，12，25，78，94，36，58，90，66，77}，从这 批数中找出最大值和第二大的值以及它们所在的位置。要求在同一个循环中既找出最大值又找出第二大值（只能使用一层循环）。不允许用排序的方法。 6、编写一个万年历程序。输入1900年后的某一年，要求显示该年份的日历， 日历以月份顺序排列，每月以星期顺序排列，类似于一般挂历上的格式。 7、一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通常的 习惯编排，每个页码都不含多余的前导数字0。例如，第6页用数字6表示，而不是06或006等。数字计数问题要求编写程序对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2，3，4，……9. 8、用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如：给定了 6种钱币面值为2、5、10、20、50、100，用来凑15元，可以用5个2 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.wendangku.net/doc/f512029976.html,/redcastle/blog/item/934b232dbc40d336349bf7e4.html poj1035:拼写检查 时间限制： 2000毫秒内存限制： 65536K 提交总数： 11190 ： 4140 说明 作为一个新的拼写检查程序的开发团队成员，你写的模块，将检查使用一切形式的所有已知的正确的话字典的 话的正确性。如果这个词在字典中缺席那么它可以取代正确的话（从字典）可以取得下列操作之一： 从单词的一个字母删去 ;在任意一个字母的单词一个字母 取代，插入一个？任意字母到单词 ，你的任务是编写程序，会发现每一个给定的单词从字典中所有可能的替代。 输入 输入文件的第一部分包含从字典中的所有单词。每个字中占有它自己的行。完成这部分是由一个单独的行上的单字符'＃' 。所有的字是不同的。将有10000字的字典。 文件的下一部分，包含了所有的单词进行检查。每个字中占有它自己的行。这部分也完成了由一个单独的行上的单字符'＃' 。将有最多50个字进行检查。 输入文件中的所有单词（从字典和被检查的词字）只包括小字母字符，每一个包含15个字符最多。 输出 写入到输出文件中完全检查它们在输入文件的第二部分中出现的顺序每个字一行。如果这个词是正确的（即它在字典中存在）写留言：“是正确的“，如果这个词是不正确的，那么先写这两个字，然后写字符。”：“（冒号），并在一个单独的空间写了所有可能的替代品，用空格隔开这些替代应在书面的顺序。其在字典中（在输入文件的第一部分）。出现，如果有这个字没有替换，然后换行，应立即按照冒号。 样例输入 我是有我更多的比赛，我太iF奖＃我知道米的较量HAV OO或我的网络连接MRE＃ 输出范例 我是正确的认识到：奖米：我的我的比赛是正确的甲肝：已经有OO：太：我是正确的FI：我MRE：更多的我 poj3080:蓝色牛仔裤 时间限制： 1000毫秒内存限制： 65536K 提交总数： 6173 接受日期： 2560 说明 基因地理工程是IBM与国家地理学会，是分析，从成千上万的贡献者地图地球是如何填充DNA的研究伙伴关系，作为IBM的研究人员，你一直负责编写一个程序，会发现共性之间个人调查资料，以确定新的遗传标记，可与相关的DNA 片段。DNA碱基序列是指出在它们在分子中发现的顺序列出的氮基地。有四种碱基：腺嘌呤（A），胸腺嘧啶（T），鸟嘌呤（G），胞嘧啶（C）。一个6碱基的DNA序列可以作为TAGACC代表。鉴于一组DNA碱基序列，确定在所有序列中出现的最长的系列基地。 输入 输入到这个问题，将开始与行包含一个单一的整数n表示数据集的数目。每个数据集由以下几部分组成组成： ?一个正整数m（2 <= M <= 10）的碱基序列，在此数据集。 ?m行每片含60个碱基组成的单一碱基序列。 输出 对于每一个输入数据集，输出基地序列的最长共同所有的碱基序列。如果最长的公共子序列的长度小于3基地，显示字符串“没有显着的共性”。如果存在多个子序列相同的长度最长，只输出序列的按字母顺序排列第一。 题目来源：福州大学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 数据结构与算法 课程设计报告 课程设计题目：并查集检查网络 专业班级：信息与计算科学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是网络中连通集的个数。两组测试数据之间请输出一空行分隔 这个训练计划我也只是把我知道的知识点罗列出来而已. 其实acm还有很多方面的知识。 可能到acm生涯结束的时候还是无法把所有的知识都吃透 所以acm的知识能学多少算多少，知识重要的不是你知道的多，重要的是你能否熟练的运用他们！ 题目注意事项： zoj：https://www.wendangku.net/doc/f512029976.html,/ grid：https://www.wendangku.net/doc/f512029976.html,/ hdu：https://www.wendangku.net/doc/f512029976.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.wendangku.net/doc/f512029976.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 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 ACM常用算法及练习 第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码，因为太常用，所以要练到写时不用想，10-15分钟内打完，甚至关掉显示器都可以把程序打出来. 1.最短路(Floyd、Dijstra,BellmanFord) 2.最小生成树(先写个prim,kruscal要用并查集，不好写) 3.大数（高精度）加减乘除 4.二分查找. (代码可在五行以内) 5.叉乘、判线段相交、然后写个凸包. 6.BFS、DFS,同时熟练hash表(要熟，要灵活,代码要简) 7.数学上的有：辗转相除（两行内），线段交点、多角形面积公式. 8. 调用系统的qsort, 技巧很多，慢慢掌握. 9. 任意进制间的转换 第二阶段：练习复杂一点，但也较常用的算法。 如： 1. 二分图匹配（匈牙利），最小路径覆盖 2. 网络流，最小费用流。 3. 线段树. 4. 并查集。 5. 熟悉动态规划的各个典型：LCS、最长递增子串、三角剖分、记忆化dp 6.博弈类算法。博弈树，二进制法等。 7.最大团，最大独立集。 8.判断点在多边形内。 9. 差分约束系统. 10. 双向广度搜索、A*算法，最小耗散优先. 相关的知识 图论 路径问题 0/1边权最短路径 BFS 非负边权最短路径（Dijkstra） 可以用Dijkstra解决问题的特征 负边权最短路径 Bellman-Ford Bellman-Ford的Yen-氏优化 差分约束系统 Floyd 广义路径问题 传递闭包 极小极大距离/ 极大极小距离 Euler Path / Tour 圈套圈算法 混合图的Euler Path / Tour Hamilton Path / Tour 特殊图的Hamilton Path / Tour 构造 生成树问题 最小生成树 第k小生成树 最优比率生成树 0/1分数规划 度限制生成树 连通性问题 强大的DFS算法 无向图连通性 割点 割边 二连通分支 有向图连通性 强连通分支 2-SAT 最小点基 有向无环图 拓扑排序 有向无环图与动态规划的关系 二分图匹配问题 一般图问题与二分图问题的转换思路 最大匹配 有向图的最小路径覆盖 0 / 1矩阵的最小覆盖 完备匹配 最优匹配 稳定婚姻 网络流问题 网络流模型的简单特征和与线性规划的关系最大流最小割定理 最大流问题 有上下界的最大流问题 循环流 最小费用最大流/ 最大费用最大流 自己刷的题 这是我在杭电做题的记录，希望我的分享对你有帮助！！！ 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. 来自牛人的ACM经验 竞赛2010-07-16 09:51:43 阅读0 评论0 字号：大中小 转于：https://www.wendangku.net/doc/f512029976.html,/luxuejuncarl/ hacker名单 https://www.wendangku.net/doc/f512029976.html,/isbx posted @ 2007-03-19 21:30 路雪军阅读(120) | 评论(0) | 编辑收藏 Linux常用命令锦集 https://www.wendangku.net/doc/f512029976.html,/images/tech/linux/zhuanti/mingling/index.htm posted @ 2007-03-19 20:25 路雪军阅读(112) | 评论(0) | 编辑收藏 2007年3月5日 随想 记录下wonderful的sentences，背下来并加以应用is a good habit.. posted @ 2007-03-05 15:24 路雪军阅读(88) | 评论(0) | 编辑收藏 2007年3月3日 acm比赛经验（转） 在天大，偶参加的比赛可以算是最多的了，说说比赛经验。 可能现在说早了点，需要大家在正式比赛之前再看一遍。 推荐此篇文章打印，与模板放在一起。 1. 比赛中评测会有些慢，偶尔还会碰到隔10分钟以上才返回结果的情况，这段时间不能等结果，必须开工其他题，如果W A，两道题同时做。交完每道题都要先打印。 2. 比赛时发的饭不是让你当时就吃的，那是给你赛后吃的。基本上比赛中前几名的队都没人吃，除非领先很多。 3. 很多选手，尤其是第一次参加比赛的，到一个新环境，全当旅游了，参观的参观，找同学的找同学，玩玩乐乐就把正事抛到脑后了，结果比赛自然没什么好成绩，这样的例子太多了。所以到参赛地后要时刻不忘自己是来比赛的，好好休息、备战。 4. 参赛前一天要睡10个小时以上，非常有助于保持比赛中的精力，很多时候比赛到3个多小时队员就没劲了就是这个原因。前一天晚饭与当天早饭要吃好，理由同上，要知道下顿饭得下午3点赛后才能吃。 5. 到新环境，时刻注意远离疾病，感冒肠炎病不大，却是成绩的天敌。 6. 英语不好，看不懂的，要勤查词典，懒一次就少一道题，远离奖牌。 7. 可以紧张，杜绝慌张，慌张是出题的敌人，任何时候，如果发现自己或者队友出现慌张的情况，提醒深呼吸。 8. 照着纸敲代码和sample数据时不要敲错，特别注意文字信息。 9. 第一道简单题交给队中最稳的人做，万一遇到麻烦也不要慌，如果有很多队都出了就更不必着急了，它必定是简单题，必定是可以很快做出来的，晚几分钟也比罚掉20分好。另外注意不要PE。 10. 最后一小时是出题高峰，谁松懈，谁落后。最后一小时出一道是正常，出两道更好。 以上各条均有出处，每条都包含着以往教训，每条都可能浪费掉你一年的努力，不可小视。以下各条有些来自于其他学校，有些是总结： 11. 无论是否有人通过，所有题必须全读过，最好每道题都有两人以上读过，尽量杜绝讲题 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、公约数和公倍数 https://www.wendangku.net/doc/f512029976.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这个函数就是找掌门用的，意义再清楚不过了（路径压缩算法先不论，后面再说）。ACM练习题
ACM经典算法及配套练习题
信息学奥赛-并查集
acmicpc练习题
(2020年编辑)ACM必做50题的解题-数论
ACM训练题集一
ACM题目整理
并查集检查网络课程设计报告
ACM一期 基础训练计划
ACM必做50题——模拟
ACM必做50题——数学
ACM训练计划
杭电acm部分题目及答案答案
来自牛人的ACM经验
整理出ACM所有题目及答案
ACM数论方面十道基础题目详解
并查集超级易懂讲解