并查集--团伙-朋友问题
并查集-朋友问题
2012-12-10 23:15 18人阅读评论(0) 收藏举报例一：
整个组织有n个人，任何两个认识的人不是朋友就是敌人，而且满足：①我朋友的朋友是我的朋友；②我敌人的敌人是我的朋友。所有是朋友的人组成一个团伙。现在，警方委派你协助调查，拥有关于这n个人的m条信息（即某两个人是朋友，或某两个人是敌人），请你计算出这个城市最多可能有多少个团伙。数据范围：2≤N≤1000，1≤M≤1000。
输入数据：第一行包含一个整数N，第二行包含一个整数M，接下来M行描述M条信息，内容为以下两者之一：“F x y”表示x与y是朋友；“E x y”表示x与y是敌人（1≤x≤y≤N）。
输出数据：包含一个整数，即可能的最大团伙数。
样例：
输入：6
4
E 1 4
F 3 5
F 4 6
E 1 2
输出：3
#include
using namespace std;
int root[1001]={0};
int relate[1001][1001]={0};
int father(int n)
{
if(root[n]==-1)
return n;
else
return father(root[n]);
}
int hb(int x,int y)
{
int n,m;
n=father(x);
m=father(y);
if (n root[m]=n; else root[n]=m; return 0; } int main() { int n,m; int i,j,k; char c; int x,y; cin>>n>>m; for(i=1;i<=1001;i++) root[i]=-1; for (i=1;i<=m;i++) { cin>>c>>x>>y; if(c=='E') { relate[y][x]=1;//记录相互的关系 relate[x][y]=1; } if(c=='F') hb(x,y); } for(i=1;i<=n;i++) { //遍历关系，合并我的敌人的敌人即朋友 for(j=1;j { if(relate[i][j]) { for (k=1;k { if (relate[j][k]) hb(k,i); } } } } int s=0; for(i=1;i<=n;i++) { if(root[i]==-1) s++; } cout< return 0; } /*首先，如果两人是朋友，那么就把两人合并。 除此之外，我们再维护一个e[i]，表示i的一个敌人。如果两人是敌人，那么如果e[i]为空，就更新e[i]，否则，就把e[i]和j合并。根据敌人的敌人是朋友的原则，如果j和i是敌人，那么j同e[i]则是朋友，所以合并。同样的，对于i和e[j]，也是如此。最后统计一下根结点就行了。 #include #include #include #include using namespace std; int n,m; const int maxn=1000; int f[maxn+10],e[maxn+10]; int find(int x) { if (f[x]==x) return f[x]; f[x]=find(f[x]); return f[x]; } void together(int a,int b) { int aa=find(a),bb=find(b); f[aa]=f[bb]; } int main() { scanf("%d%d",&n,&m); for (int i=1; i<=n; i++) f[i]=i; while(m--) { char flag=(getchar(),getchar()); int a,b; scanf("%d%d",&a,&b); if(flag=='F') together(a,b); else { if(!e[a]) e[a]=b; else together(e[a],b); if(!e[b]) e[b]=a; else together(e[b],a); } } int ans=0; for(int i=1;i<=n;i++) if(f[i]==i) ans++; printf("%d\n",ans); return 0; } */ 例二： More isbetter Time Limit: 5000/1000 MS (Java/Others) Memory Limit:327680/102400 K (Java/Others) Total Submission(s): 7622 Accepted Submission(s): 2797 Problem Description Mr Wang wants some boys tohelp him with a project. Because the project is rather complex, the moreboys come, the better it will be. Of course there are certain requirements. Mr Wang selected a room big enough to hold the boys. The boy who are not beenchosen has to leave the room immediately. There are 10000000 boys in the roomnumbered from 1 to 10000000 at the very beginning. After Mr Wang's selectionany two of them who are still in this room should be friends (direct orindirect), or there is only one boy left. Given all the direct friend-pairs,you should decide the best way. Input The first line of the inputcontains an integer n (0 ≤ n ≤ 100 000) - the number of direct friend-pairs.The following n lines each contains a pair of numbers A and B separated by asingle space that suggests A and B are direct friends. (A ≠ B, 1 ≤ A, B ≤10000000) Output The output in one linecontains exactly one integer equals to the maximum number of boys Mr Wang maykeep. Sample Input 4 1 2 3 4 5 6 1 6 4 1 2 3 4 5 6 7 8 Sample Output 4 2 Hint A and B are friends(direct or indirect), B and C are friends(direct orindirect), then A and C are also friends(indirect). In the first sample {1,2,5,6} isthe result. In the second sample {1,2},{3,4},{5,6},{7,8} are four kinds of answers. #include #include int f[10000001]; bool root[10000001]; int sum=0; int find(int a); void Unino(int a,int b); int main() { int n,a,b; while(scanf("%d",&n)!=EOF) { for(int j=0;j<10000001;j++) { root[j]=true; f[j]=1; } for(int i=0;i { scanf("%d%d",&a,&b); a=find(a); b=find(b); if(a!=b) { Unino(a,b); } } for(int k=0;k<10000001;k++) { if(f[k]>sum&&root[k]) sum=f[k]; } printf("%d\n",sum); sum=0; } return 0; } int find(int a) { while(!root[a]) a=f[a]; return a; } void Unino(int a,int b) { if(f[a]>f[b]) { f[a]=f[a]+f[b]; f[b]=a; root[b]=false; } else { f[b]=f[a]+f[b]; f[a]=b; root[a]=false; } } 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为例： 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，构造图论模型。 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/6c12533402.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 矩阵快速幂 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 数据结构与算法 课程设计报告 课程设计题目：并查集检查网络 专业班级：信息与计算科学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．（本题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。 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. 第八讲 概率统计 【考点透视】 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的意义和概率的求法. 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.重点 （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 1、公约数和公倍数 https://www.wendangku.net/doc/6c12533402.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这个函数就是找掌门用的，意义再清楚不过了（路径压缩算法先不论，后面再说）。USACO题解(NOCOW整理版)
ACM经典算法及配套练习题
排列组合专题复习及经典例题详解
信息学奥赛-并查集
(2020年编辑)ACM必做50题的解题-数论
ACM题目整理
各算法经典例题
并查集检查网络课程设计报告
ACM必做50题——模拟
统计及概率经典例题(含答案和解析)
图形推理经典例题及答案解析真题
ACM必做50题——数学
杭电acm部分题目及答案答案
概率统计例题及练习题(答案)
整理出ACM所有题目及答案
排列组合专题总结复习及经典例题详解 .docx
ACM数论方面十道基础题目详解
并查集超级易懂讲解