【题解】亲戚
【题目描述】
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。
【输入描述】
第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。
以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Mi和Mj具有亲戚关系。
接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。
【输出描述】
P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系
【样例输入】
6 5 3 1 2 1 5 3 4 5 2 1 3 1 4 2 3 5 6
【样例输出】
Yes Yes No
【题解】宴会
【题目描述】
今人不见古时月，今月曾经照古人。
梦回长安，大唐风华，十里长安花，一日看尽。
唐长安城是当时世界上规模最大、建筑最宏伟、规划布局最为规范化的一座都城。其营建 制度规划布局的特点是规模空前、创设皇城、三城层环、六坡利用、布局对称、街衢宽阔、坊 里齐整、形制划一、渠水纵横、绿荫蔽城、郊环祀坛。而所谓的十里长安街，位于长安城的中 轴线上，即唐长安城的朱雀大街，又称承天门大街。唐朝官员们住在各个“坊”里，上朝下朝 都需要通过朱雀大街。
为了保持各大家族的联系和友谊，各官员往往会每月办一次宴会。为了方便描述，我们把 朱雀大街看成一个数轴，各官员所居住的“坊”缩略为数轴上的一个坐标点。大家决定选一处 地点（该地点是数轴上的某一个点，不一定坐标点）办宴会。由于唐朝宵禁严格，大家又都希 望交流时间尽可能长，因此想要使宴会开始时间尽可能早。又因为大唐注重礼仪，因此，参加 宴会的官员会花一定时间盛装打扮过后才前往宴会地点（不一定是坐标点）。 更具体地，一条纵向的街道上（相当于一维坐标）有 n 个人居住，其中第i个人居住在xi （非负整数） 位置（坐标点）上。每月他们会选择在 x0（数轴上的某一个点，不一定坐标点） 出举办宴会。 已知第 i 个人从 xi 出发前往宴会地点 x0 处需要花费 |xi-x0| 的时间，另外，他还需要花费 ti的时间进行打扮，换言之，他共需要花费 |xi-x0| + ti 的时间到达宴会举办处。 假设初始时刻为 0 。
这 n 个人开始打扮和出发前往宴会处，他们想要使得宴会的开始时间 尽可能早，于是向你求助，请你帮助他们确定好最优的宴会举办地点 x0。 注：|xi-x0| 表示xi 与 x0 之差的绝对值，且题目中 n 个人的居住地点坐标均为整数。
【输入描述】
第一行一个正整数 T，表示测试数据的组数。
接下来对于每组测试数据（注意：每组测试数据有 3 行数据，以下共 3*T 行数据）：
第一行一个正整数 n，表示总官员人数。
第二行共 n 个非负整数x1,x2,x3,...xn 分别表示这 n 个人在数轴上的坐标。
第三行共 n 个非负整数t1,t2,t3...tn分别表示这 n 个人出发前的打扮时间
【输出描述】
共输出 T 行数据，对于每组测试数据，输出一行一个实数（如果是整数按整数输出，如果有 小数，保留 1 位小数输出），表示使宴会开始时间最早的最优举办地点坐标x0。（很显然，x0是唯一的）
【样例输入】
7 1 0 3 2 3 1 0 0 2 1 4 0 0 3 1 2 3 0 0 0 3 1 2 3 4 1 2 3 3 3 3 5 3 3 6 5 4 7 2 10 4 3 2 5 1 4 6
【样例输出】
0 2 2.5 2 1 3 6
【样例说明】
初始时刻为 0。 对于第一组测试数据只有 1 个人，坐标为 0，打扮时间为 3，很显然 x0 就定在坐标 0 处，使 得宴会开始时间为 3 且最早。
对于第二组测试数据有 2 个人，坐标分别为 3、1，打扮时间均为 0，很显然 x0 定在坐标 2 处，使得宴会开始时间为 1 且最早。
对于第三组测试数据有 2 个人，坐标分别为 1、4，打扮时间均为 0，很显然 x0 定在坐标 2.5 处，使得宴会开始时间为 1.5 且最早。
【数据范围】
对于 30% 的数据,T=1，1<=n<=100, 0<=xi, ti<=1000;
对于 60% 的数据，T<=n<=10^4, 0<=xi, ti<=10^5；
对于100%的数据，1<=T<=10^3, 1<=n<=10^5, 0<=xi, ti<=10^8,且保证所有测试数据的n加起来都不超过2*10^5
【图】并查集—基本概念
1.引入
对于一个集合S={a1, a2, …, an-1, an}，我们还可以对集合S进一步划分: S1,S2,…,Sm-1,Sm，我们希望能够快速确定S中的两两元素是否属于S的同一子集。
举个栗子，S={0，1, 2, 3, 4, 5, 6}，如果我们按照一定的规则对集合S进行划分,假设划分后为S1={1, 2, 4}, S2={3, 6}，S3={0, 5}，任意给定两个元素，我们如何确定它们是否属于同一子集？某些合并子集后，又如何确定两两关系？基于此类问题便出现了并查集这种数据结构。
2.概念
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。
并查集的思想是用一个数组表示了整片森林（parent），树的根节点唯一标识了一个集合，我们只要找到了某个元素的的树根，就能确定它在哪个集合里。
3.作用
并查集可以高效的对元素进行分组（合并在一起），并且能快速的查询两个元素是否属于同一组。
4.基本操作
合并：合并两个集合。join函数
查找：判断两个元素是否在一个集合。find函数
5.过程解释
假如有两个集合，之间的关系可以用下面的图像表示：
一开始，分成两组，1和2是同一组，1和3是同一组，那么有没有什么办法可以将这两组练习起来。我们将1视为2的父级，1可以视为3的父级
这样，我们可以把图片划分成下面这样：
那么如果我们有其他的数据，比如下面的4，5，6这样表示
那么新问题来了，这两个集合如果在一块应该怎么表示呢？很简单，让这两个集合中的‘老大’打一架，谁赢了，谁就是两个集合共同的‘老大’。
假如 编号1 赢了，那么集合应该变成下面这样：
也就1成了所有人的‘老大’
那么也就是形成了一个等级严格的树形结构。
从数据结构上看，我们关注的重点是两个数据之间是否连通。
那么看下面这个例子
对于上面这个图，我们如何界定两个节点之间是否有关系呢？比如下面这两个题：
(1)问：2和3之间是否存在关系？
(2)问：3和7之间是否存在关系？
对于问题(1)，我们从图中可以很明显的看出，2和3之间有关系，因为他们有共同的’老大‘。
对于问题(2), 我们从图中也可以明显的看出，3和7之间没有关系，因为从3开始往上找，发现老大是1，而从7开始找，我们发现老大是4，这两个老大（根节点）不一样，说明没有关系。
在做题中，也就是我们输入每组的对应关系如下，
1 2 1 3 4 5 4 6 6 7
然后询问任意两个数（节点）之间有没有关系?
6.代码实现
（1）初始化
我们用f数组表示父级元素节点，初始化代码如下
int f[100]; //父节点 //初始化 n个元素 void Init() { //使每个元素的根节点是其本身 //即初始时每个元素都是单独的 for(int i=1; i<=n; i++){ f[i]=i; } }’每个节点都是自己的父节点‘
（2）查询操作
查询操作有两种实现方式，一种是递归实现，另一种是非递归实现。
递归实现：
int find(int x){ if(f[x] == x) return x; else return find(f[x]);}一层一层访问父节点，直至根节点（根节点的标志就是父节点是本身）。要判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同即可。
非递归实现：
int find(int x) { while(f[x] != x) { //直到元素的父节点是它本身，表示已经查询到了树的根 x= f[x]; return x; //返回根节点对应的元素 }（3）合并
void merge(int a, int b) { //先找到两个元素对应的根对应的元素 int fa = find(a); int fb = find(b); if(fa==fb) return; else f[fa]=fb; //否则令元素 a的根指向元素 b的根 }合并操作也是很简单的，先找到两个集合的代表元素，然后将前者的父节点设为后者即可。当然也可以将后者的父节点设为前者。
【题解】高精度除法
【题目描述】
高精除以高精，求它们的商和余数。
【输入描述】
输入两个低于300位的正整数。
【输出描述】
输出商和余数。
【样例输入】
1231312318457577687897987642324567864324567876543245671425346756786867867867 1231312318767141738178325678412414124141425346756786867867867
【样例输出】
999999999748590 179780909068307566598992807564736854549985603543237528310337
【题解】大整数乘法
【题目描述】
求两个不超过200位的非负整数的积。
【输入描述】
有两行，每行是一个不超过200位的非负整数，没有多余的前导0。
【输出描述】
一行，即相乘后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。
【样例输入】
12345678900 98765432100
【样例输出】
1219326311126352690000