并查集支持三种操作

◆并查集支持三种操作：

Init（X）: 集合初始化：把元素xi加到集合Si中。每个集合Si只有一个独立的元素xi,并且元素xi就是集合Si的代表元素。

Find(x): 查找：查找xi所在集合Si的代表root[Si]。

优化：路径压缩。

Union(x, y): 合并：把x和y所在的两个不同集合合并。

1）、x=x （自反性）

2）、如果x=y，则y=x （对称性）

3）、如果x=y，y=z，则x=z （传递性）

采用树型结构实现并查集的基本思想是：

◆每个子集合用一棵树来表示。树中的每个结点用于存放集合中的一个元素。

◆树中的每个结点x设置一个指向父亲的指针。

father[x]

◆用根结点的元素代表该树所表示的集合。

?Init（X）: 集合初始化：

father[xi]=0(或者xi); 每个结点都是一颗独立的树，

是该树的代表元素。

?Find(x): 查找：

查找x所在集合Si的代表root[Si]。

即：查找x所在树的树根结点（代表元素）。

顺着x往上找，直到找到根节点，也就确定了x所在的集合。

?Union(x, y): 合并x和y所在的不同集合。

p=find(x) ；q=find(y);

if p<>q then father[p]=q 或father[q]=p

function find(i:longint):longint;{非递归算法找i的根}

var j,k,t:longint;

begin

j:=i;//顺着结点i开始向上找，直到根为止。

while a[j]<>0 do j:=a[j];

find:=j;

end;

function find(i:longint):longint;

//递归算法找i的根

var j,k,t:longint;

begin

if a[i]=0 then exit(i); //若i为根，返回本身结点序号

find:=find(a[i]); //否则继续向上找

end;

function find(i:longint):longint;{非递归算法找i的根}

var j,k,t:longint;

begin

j:=i;

while a[j]<>0 do j:=a[j]; // 顺着i向上找根。

find:=j;

k:=i; {从i开始对子树结点进行路径压缩}

while a[k]<>0 do begin t:=k;k:=a[k];a[t]:=j;end;

end;

function find(i:longint):longint;

{采用递归算法：寻找结点i的树根，并对结点i所在的子树进行路径压缩，返回调整后的i 的父指针（根）}

begin

if a[i]=0 then exit(i);

{若i为根，返回本身结点序号}

find:=find(a[i]);{递归找根结点}

a[i]:=find;

{路径压缩：找到根后，按原路返回的同时，进行中间结点的逆序路径压缩，一次性完成}

end;

USACO题解(NOCOW整理版)

USACO 题解 Chapter1 Section 1.1 Your Ride Is Here (ride) 这大概是一个容易的问题，一个“ad hoc”问题，不需要特殊的算法和技巧。 Greedy Gift Givers (gift1) 这道题的难度相当于联赛第一题。用数组incom、outcom记录每个人的收入和支出，记录每个人的名字，对于送礼人i，找到他要送给的人j，inc(incom[j],outcom[i] div n)，其中n 是要送的人数，最后inc(incom[i],outcom[i] mod n)，最后输出incom[i]-outcom[i]即可。（复杂度O(n^3)）。 用Hash表可以进行优化，降复杂度为O(n^2)。 Friday the Thirteenth (friday) 按月为单位计算，模拟运算，1900年1月13日是星期六（代号1），下个月的13日就是代号(1+31-1) mod 7+1的星期。 因为数据小，所以不会超时。 当数据比较大时，可以以年为单位计算，每年为365天，mod 7的余数是1，就是说每过一年所有的日和星期错一天，闰年第1、2月错1天，3月以后错2天。这样，只要先求出第一年的解，错位添加到以后的年即可。 详细分析：因为1900.1.1是星期一，所以1900.1.13就等于(13-1) mod7+1=星期六。这样讲可能不太清楚。那么，我来解释一下：每过7天是一个星期。n天后是星期几怎么算呢？现在假设n是7的倍数，如果n为14，那么刚好就过了两个星期，所以14天后仍然是星期一。但如果是过了15天，那么推算就得到是星期二。这样，我们就可以推导出一个公式来计算。(n天mod 7（一个星期的天数）+ 现在日期的代号) mod 7 就等于现在日期的代号。当括号内的值为7的倍数时，其代号就为0，那么，此时就应该是星期日这样，我们可以得出题目的算法： int a[13]={0，31，28，31，30，31，30，31，31，30，31，30，31} int b[8]={0} a数组保存一年12个月的天数（因为C语言中数组起始下标为0，所以这里定义为13）。 b数组保存星期一到星期日出现的天数。用date记录目前是星期几的代号，然后用两个循环，依次加上所经过的月份的天数，就出那个月是星期几，当然，要注意判断闰年！知道了这个方法，实现起来就很容易了。 注意考虑闰月的情况。 最后注意要换行，否则会错误。 Broken Necklace (beads) 这道题用标准的搜索是O(n^2)的，可以用类似动态规划的方法优化到O(n)。 用数组bl，br，rl，rr分别记录在项链i处向左向右收集的蓝色红色珠子数。 项链是环形的，但我们只要把两个同样的项链放在一块，就把它转换成线性的了。 我们只要求出bl，br，rl，rr，那么结果就是max(max(bl[i]，rl[i])+max(br[i+1]，rr[i+1])) (0<=i<=2*n-1)。 我们以求bl，rl为例：

ACM经典算法及配套练习题

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)组合数学:

排列组合专题复习及经典例题详解

排列组合专题复习及经典例题详解 1.学习目标 掌握排列、组合问题的解题策略 2.重点 （1）特殊元素优先安排的策略： （2）合理分类与准确分步的策略； （3）排列、组合混合问题先选后排的策略； （4）正难则反、等价转化的策略； （5）相邻问题捆绑处理的策略； （6）不相邻问题插空处理的策略． 3.难点 综合运用解题策略解决问题． 4.学习过程: (1)知识梳理 m种不完成一件事，有几类办法，在第一类办法中有1．分类计数原理（加法原理）：1mm种不同的方法，类型办法中有种不同的方法……在第n同的方法，在第2类办法中有n2N?m?m?...?m 种不同的方法．那么完成这件事共有n12m种不步有个步骤，做第12．分步计数原理（乘法原理）：完成一件事，需要分成n1mm种不同的方法；那么完成这步有种不同的方法……，做第同的方法，做第2步有n n2N?m?m?...?m种不同的方法．件事共有n12特别提醒： 分类计数原理与“分类”有关，要注意“类”与“类”之间所具有的独立性和并列性； 分步计数原理与“分步”有关，要注意“步”与“步”之间具有的相依性和连续性，应用这两个原理进行正确地分类、分步，做到不重复、不遗漏． 3．排列：从n个不同元素中，任取m(m≤n)个元素，按照一定的顺序排成一列，叫做从n m?nm?n 时叫做全排列. 时叫做选排列，排列个不同元素中取出m个元素的一个，4．排列数：从n个不同元素中，取出m(m≤n)个元素的所有排列的个数，叫做从n个不同m P. 个元素的排列数，用符号表示元素中取出m n n!?m）?Nmn（m?)...()(1n?2n?m1)??,n、?(?Pnn5．排列数公式： n(n?m)!1mmm?mPPP??排列数具有的性质：nn1?n特别提醒： 规定0!=1 1 6．组合：从n个不同的元素中，任取m(m≤n)个不同元素，组成一组，叫做从n个不同元素中取m个不同元素的一个组合. 7．组合数：从n个不同元素中取m(m≤n)个不同元素的所有组合的个数，叫做从n个m C. 个不同元素的组合数，用符号表示不同元素中取出m nm Pn(n?1)(n?2)...(n?m?1)n!mn???C．组合数公式：8 nm)!m!(n?m!mP mmn?mmmm?1C?CC?C?C；②组合数的两个性质：①nnnnn?1特别提醒：排列与组合的联系与区别. 联系：都是从n个不同元素中取出m个元素. 区别：前者是“排成一排”，后者是“并成一组”，前者有顺序关系，后者无顺序关系.

信息学奥赛-并查集

信息学奥赛中的特殊数据结构——并查集 在一些有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，构造图论模型。

ACM题目整理

题目来源：福州大学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 main() { long a,b; while((scanf("%ld%ld",&a,&b))!=EOF) { printf("%ld\n",a+b); } } 详情参考https://www.wendangku.net/doc/7c1282100.html,/faq.php 二、ACM分类 主流算法： 1.搜索//回溯 Problem 1019 猫捉老鼠 Time Limit: 1000 mSec Memory Limit : 32768 KB Problem Description 一只猫和一只老鼠在10*10的迷宫中。迷宫中的每个方格可以是空的，或者含有障碍。猫和老鼠可以进入任意一个空的方格中。当他们相遇时，猫和老鼠在同一个方格中。但是，无论猫或老鼠都不能进入有障碍的方格。我们可以用字符组成的二维数组表示迷宫，如下图所示。

各算法经典例题

矩阵快速幂 hrbust1140 数字和问题 Description 定义一种操作为：已知一个数字，对其各位数字 反复求和，直到剩下的数是一位数不能求和为止。 例如：数字2345，第一次求和得到2 + 3 + 4 + 5 = 14，再对14的各位数字求和得到1 + 4 = 5，得到5将不再求和。 现在请你求出对a^b进行该操作后，求最终得到的数字. Input 第一行，包含两个数字a（0 <= a <= 2000000000）和b（1 <= b <= 2000000000） Output 输出对a^b进行操作后得到的数字是什么 #include #include #include #include #include #include using namespace std; int sum(int x) { return ((x+8)%9+1); } int g(int a,int k) { if(k==0) return 1; if(k==1) return a%9; if(k%2==0) return (g((a%9)*(a%9),k/2)%9); if(k%2==1) return (a%9)*(g((a%9),k-1)%9); } int main() { int a,k; while(scanf("%d%d",&a,&k)!=EOF) { if(a==0)printf("0\n"); else printf("%d\n",sum(g(a,k))); } }

并查集检查网络课程设计报告

数据结构与算法 课程设计报告 课程设计题目：并查集检查网络 专业班级：信息与计算科学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必做50题——模拟

1、POJ 1029 False coin Slyar:又是假币判断问题，跟POJ1013类似，不过这个题用1013那个算法W A了...后来换了种枚举的算法才过...思路就是假币应该在每个不等式中都出现，最后只要看哪个硬币出现的次数和不等式出现的次数相同，如果这个硬币唯一，那它就是确认的假币。 #include #include using namespace std; const int MAX = 1001; int main() { int n, k, p, total = 0; char sign; /* 记录原始数据*/ int t[MAX] = {0}; /* 标记硬币真假*/ int r[MAX] = {0}; /* 记录硬币重量*/ int w[MAX] = {0}; cin >> n >> k; while (k--) { /* 读入原始数据*/ cin >> p; for (int i = 0; i < 2 * p; i++) { cin >> t[i]; } cin >> sign; /* 标记肯定为真的硬币*/ if (sign == '=') { for (int i = 0; i < 2 * p; i++) {

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．（本题8分）为了解学区九年级学生对数学知识的掌握情况，在一次数学检测中，从学区2000名九年级考生中随机抽取部分学生的数学成绩进行调查，并将调查结果绘制成如下图表： ⑴表中a 和b 所表示的数分别为：a= .，b= .； ⑵请在图中补全频数分布直方图； ⑶如果把成绩在70分以上（含70分）定为合格，那么该学区2000名九年级考生数学成绩为合格的学生约有多少名？ 2．为鼓励创业，市政府制定了小型企业的优惠政策，许多小型企业应运而生，某镇统计了该镇1﹣5月新注册小型企业的数量，并将结果绘制成如下两种不完整的统计图： （1）某镇今年1﹣5月新注册小型企业一共有 家．请将折线统计图补充完整； （2）该镇今年3月新注册的小型企业中，只有2家是餐饮企业，现从3月新注册的小型企业中随机抽取2家企业了解其经营状况，请用列表或画树状图的方法求出所抽取的2家企业恰好都是餐饮企业的概率． 3．（12分）一个不透明的口袋装有若干个红、黄、蓝、绿四种颜色的小球，小球除颜色外完全相同，为估计该口袋中四种颜色的小球数量，每次从口袋中随机摸出一球记下颜色并放回，重复多次试验，汇总实验结果绘制如图不完整的条形统计图和扇形统计图．

图形推理经典例题及答案解析真题

【题型】单选题 【题干】把下面的六个图形分为两类，使每一类图形都有各自的共同特征或规律，分类正确的一项是： 【选项】 A．①③④，②⑤⑥ B．①③⑥，②④⑤ C．①④⑥，②③⑤ D．①③⑤，②④⑥ 【答案】C 【解析】属性类。1、4、6轴对称，2、3、5中心对称。 故正确答案为C。 【题型】单选题 【题干】把下面的六个图形分为两类，使每一类图形都有各自的共同特征或规律，分类正确的一项是： 【选项】 A．①⑤⑥，②③④ B．①③⑤，②④⑥ C．①②③，④⑤⑥ D．①②⑥，③④⑤ 【答案】B 【解析】1、3、5是曲线，2、4、6是直线。 故正确答案为B。 【题型】单选题 【题干】把下面的六个图形分为两类，使每一类图形都有各自的共同特征或规律，分类正确的一项是：

【选项】 A．①②③，④⑤⑥ B．①⑤⑥，②③④ C．①②④，③⑤⑥ D．①④⑥，②③⑤ 【答案】C 【解析】考查数量类。1、2、4是一个整体，3、5、6图形是分开的。 故正确答案为C。 【题型】单选题 【题干】把下面的六组图形分为两类，使每一类图形都有各自的共同特征或规律，分类正确的一项是： 【选项】 A．①④⑥，②③⑤ B．①③⑥，②④⑤ C．①③④，②⑤⑥ D．①②④，③⑤⑥ 【答案】A 【解析】考查样式类。1、4、6右边的大图形，在左边的图形的里面，2、3、5左边的大图形在右边的里面。 故正确答案为A。

【题型】单选题 【题干】从所给的四个选项中，选择最合适的一个填入问号处，使之呈现一定的规律性： 【选项】 A．A B．B C．C D．D 【答案】C 【解析】本题属于位置类，题干中每行图形都在逆时针旋转，且每行中第一和第二个图形眼睛旋转后再发生翻转，嘴只是发生旋转，第二和第三个图形眼睛只发生旋转，嘴旋转后再发生翻转。所以选择C选项。 故正确答案为C。

杭电acm部分题目及答案答案

自己刷的题 这是我在杭电做题的记录，希望我的分享对你有帮助！！！ 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.

概率统计例题及练习题(答案)

第八讲 概率统计 【考点透视】 1．了解随机事件的发生存在着规律性和随机事件概率的意义． 2．了解等可能性事件的概率的意义，会用排列组合的基本公式计算一些等可能性事件的概率. 3．了解互斥事件、相互独立事件的意义，会用互斥事件的概率加法公式与相互独立事件的概率乘法公式计算一些事件的概率． 4．会计算事件在n 次独立重复试验中恰好发生k 次的概率． 5． 掌握离散型随机变量的分布列. 6．掌握离散型随机变量的期望与方差. 7．掌握抽样方法与总体分布的估计. 8．掌握正态分布与线性回归. 【例题解析】 考点1. 求等可能性事件、互斥事件和相互独立事件的概率 解此类题目常应用以下知识: (1)等可能性事件(古典概型)的概率：P (A )＝)()(I card A card ＝n m ; 等可能事件概率的计算步骤： ① 计算一次试验的基本事件总数n ; ② 设所求事件A ，并计算事件A 包含的基本事件的个数m ; ③ 依公式()m P A n =求值; ④ 答，即给问题一个明确的答复. (2)互斥事件有一个发生的概率：P (A ＋B )＝P (A )＋P (B ); 特例：对立事件的概率：P (A )＋P (A )＝P (A ＋A )＝1. (3)相互独立事件同时发生的概率：P (A ·B )＝P (A )·P (B ); 特例：独立重复试验的概率：P n (k )＝k n k k n p p C --)1(.其中P 为事件A 在一次试验中发生的概率，此式为二项式[(1-P)+P]n 展开的第k+1项. (4)解决概率问题要注意“四个步骤，一个结合”：

① 求概率的步骤是： 第一步，确定事件性质???? ???等可能事件 互斥事件 独立事件 n 次独立重复试验 即所给的问题归结为四类事件中的某一种. 第二步，判断事件的运算?? ?和事件积事件 即是至少有一个发生，还是同时发生，分别运用相加或相乘事件. 第三步，运用公式()()()()()()()()(1) k k n k n n m P A n P A B P A P B P A B P A P B P k C p p -? =???+=+? ??=??=-??等可能事件: 互斥事件： 独立事件： n 次独立重复试验:求解 第四步，答，即给提出的问题有一个明确的答复. 例1．在五个数字12345，，，，中，若随机取出三个数字，则剩下两个数字都是奇数的概率是 （结果用数值表示）． [考查目的]本题主要考查概率的概念和等可能性事件的概率求法. [解答过程]0.3提示:1 33 5 C 33.54C 10 2 P ===? 例2．一个总体含有100个个体，以简单随机抽样方式从该总体中抽取一个容量为5的样本，则指定的某个个体被抽到的概率为 ． [考查目的]本题主要考查用样本分析总体的简单随机抽样方式，同时考查概率的概念和等可能性事件的概率求法. 用频率分布估计总体分布，同时考查数的区间497.5g~501.5的意义和概率的求法. [解答过程]1.20 提示:51.10020P == 例3从自动打包机包装的食盐中，随机抽取20袋，测得各袋的质量分别为（单位：g ）： 492 496 494 495 498 497 501 502 504 496 497 503 506 508 507 492 496 500 501 499 根据的原理，该自动包装机包装的袋装食盐质量在497.5g~501.5g 之间的概率约为__________． [考查目的]本题主要考查用频率分布估计总体分布，同时考查数的区间497.5g~501.5的意义和概率的求法.

整理出ACM所有题目及答案

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)

排列组合专题总结复习及经典例题详解 .docx

排列组合专题复习及经典例题详解 1.学目 掌握排列、合的解策略 2.重点 （1）特殊元素先安排的策略： （2）合理分与准确分步的策略； （3）排列、合混合先后排的策略； （4）正反、等价化的策略； （5）相捆理的策略； （6）不相插空理的策略． 3.点 合运用解策略解决． 4.学程 : (1)知梳理 1．分数原理（加法原理）：完成一件事，有几法，在第一法中有m1种不同的方法，在第 2 法中有m2种不同的方法??在第n 型法中有m n种不同的方法，那么完成件事共有N m1m2... m n种不同的方法． 2．分步数原理（乘法原理）：完成一件事，需要分成n 个步，做第 1 步有m1种不同的方法，做第 2 步有m2种不同的方法??，做第n 步有m n种不同的方法；那么完成件事共有 N m1 m2...m n种不同的方法． 特提醒： 分数原理与“分”有关，要注意“ ”与“ ”之所具有的独立性和并列性； 分步数原理与“分步”有关，要注意“步”与“步”之具有的相依性和性，用两个原理行正确地分、分步，做到不重复、不漏． 3．排列：从 n 个不同元素中，任取m(m≤n) 个元素，按照一定的序排成一列，叫做从n 个不同元素中取出 m个元素的一个排列，m n叫做排列，m n 叫做全排列. 4．排列数：从 n 个不同元素中，取出m(m≤n) 个元素的所有排列的个数，叫做从n 个不同元素中取出 m个元素的排列数，用符号P n m表示. 5．排列数公式：P n m n(n1)( n2)...( n m1) (n n!（ m n,n、 m N）m)! 排列数具有的性： P n m1P n m mP n m 1 特别提醒： 规定 0!=1

并查集超级易懂讲解

高级数据结构设计－－并查集及实现学习笔记（有趣篇） 并查集的程序设计： 为了解释并查集的原理，我将举一个更有趣的例子。 话说江湖上散落着各式各样的大侠，有上千个之多。他们没有什么正当职业，整天背着剑在外面走来走去，碰到和自己不是一路人的，就免不了要打一架。但大侠们有一个优点就是讲义气，绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”，只要是能通过朋友关系串联起来的，不管拐了多少个弯，都认为是自己人。这样一来，江湖上就形成了一个一个的群落，通过两两之间的朋友关系串联起来。而不在同一个群落的人，无论如何都无法通过朋友关系连起来，于是就可以放心往死了打。但是两个原本互不相识的人，如何判断是否属于一个朋友圈呢？我们可以在每个朋友圈内推举出一个比较有名望的人，作为该圈子的代表人物，这样，每个圈子就可以这样命名“齐达内朋友之队”“罗纳尔多朋友之队”……

两人只要互相对一下自己的队长是不是同一个人，就可以确定敌友关系了。 但是还有问题啊，大侠们只知道自己直接的朋友是谁，很多人压根就不认识队长，要判断自己的队长是谁，只能漫无目的的通过朋友的朋友关系问下去：“你是不是队长？你是不是队长？”这样一来，队长面子上挂不住了，而且效率太低，还有可能陷入无限循环中。于是队长下令，重新组队。队内所有人实行分等级制度，形成树状结构，我队长就是根节点，下面分别是二级队员、三级队员。每个人只要记住自己的上级是谁就行了。遇到判断敌友的时候，只要一层层向上问，直到最高层，就可以在短时间内确定队长是谁了。由于我们关心的只是两个人之间是否连通，至于他们是如何连通的，以及每个圈子内部的结构是怎样的，甚至队长是谁，并不重要。所以我们可以放任队长随意重新组队，只要不搞错敌友关系就好了。于是，门派产生了。 下面我们来看并查集的实现。 int pre[1000]; 这个数组，记录了每个大侠的上级是谁。大侠们从1或者0开始编号（依据题意而定），pre[15]=3就表示15号大侠的上级是3号大侠。如果一个人的上级就是他自己，那说明他就是掌门人了，查找到此为止。也有孤家寡人自成一派的，比如欧阳锋，那么他的上级就是他自己。每个人都只认自己的上级。比如胡青牛同学只知道自己的上级是杨左使。张无忌是谁？不认识！要想知道自己的掌门是谁，只能一级级查上去。find这个函数就是找掌门用的，意义再清楚不过了（路径压缩算法先不论，后面再说）。

ACM竞赛试题集锦

取石子游戏 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

并查集2

并查集。 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题——数学

1、POJ 2249 Binomial Showdown 组合数学。 高精度，也可把分子分母的数组进行两两约分 #include using namespace std; double c(int c,int k) { double a=1; int i,j=2; for(i=c;i>c-k;i--) a=a*i/(c-i+1); return a; } int main() { int n,k; while(scanf("%d%d",&n,&k)!=EOF && (n!=0 || k!=0)) { if(k>n/2 )k=n-k; printf("%.0lf\n",c(n,k)); } return 0; } 2、poj 1023 the fun number system （经典进位制） 题意：一种由2进制衍生出来的进制方法（我们暂且称为“类2进制”）； 标明'n'的位置上原2进制该位的权重要乘上-1，才是现在进制方法该位的权重； 譬如说；pnp对于的能表示的数2来说就是110；即1*2^2+(-1)*1*2^1+1*2^0=2; 算法：这是数论中的进位制问题，我们可以仿照原来的求一个数二进制表示方法； 但首先，我们应该考虑几个问题； ①k位这种类2进制的表示范围； 显然，当给出的'p','n'序列中，我们将所有p的位置都置为1其余位是0，此时最大；当我们将所有n的位置置为1，其余为0，此时最小；不过当我们求最大限max和最小限min时会

有一个溢出问题；比如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 using namespace std; __int64 N,M; char s[100],res[100]={'\0'}; int main() { int T;scanf("%d",&T); int i,j; __int64 _max,_min; char ch; while(T--) { scanf("%I64d",&N); scanf("%s",s); _max=0;_min=0; for(i=0;i_max&&_max>=0)) puts("Impossible"); //注意防止64位数的溢出； else { memset(res,'\0',sizeof(res)); for(i=N-1;i>=0;i--) { int flag=0; if(M&1) //这里不能是平常的%2； { res[i]='1';