【题解】最长不下降子序列2
【题目描述】
设有由n(1≤n≤200)个不相同的整数组成的数列，记为:b(1)、b(2)、……、b(n)且b(i)≠b(j)(i≠j)，若存在i1<i2<i3<…<ie 且有b(i1)<b(i2)<…<b(ie)则称为长度为e的不下降序列。程序要求，当原数列出之后，求出最长的不下降序列。
例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。
例中13，16，18，19，21，22，63就是一个长度为7的不下降序列，同时也有7 ，9，16，18，19，21，22，63组成的长度为8的不下降序列。
【输入描述】
第一行为n,第二行为用空格隔开的n个整数。
【输出描述】
第一行为输出最大个数max。
第二行为max个整数形成的不下降序列,答案可能不唯一，输出一种就可以了。
【样例输入】
14 13 7 9 16 38 24 37 18 44 19 21 22 63 15
【样例输出】
max=8 7 9 16 18 19 21 22 63
【题解】求最长不下降序列
【题目描述】
设有由n(1≤n≤200)个不相同的整数组成的数列，记为:b(1)、b(2)、……、b(n)且b(i)≠b(j)(i≠j)，若存在i1<i2<i3<…<ie 且有b(i1)<b(i2)<…<b(ie)则称为长度为e的不下降序列。程序要求，当原数列出之后，求出最长的不下降序列的长度。
例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。
例中13，16，18，19，21，22，63就是一个长度为7的不下降序列，同时也有7 ，9，16，18，19，21，22，63组成的长度为8的不下降序列。
【输入描述】
第一行为n,第二行为用空格隔开的n个整数。
【输出描述】
第一行为输出最大个数max
【样例输入1】
14 13 7 9 16 38 24 37 18 44 19 21 22 63 15
【样例输出1】
max=8
【样例输入2】
7 1 7 3 5 9 4 8
【样例输出2】
max=4
【题解】寻找祖先
【题目描述】
给出充足的父子关系，请你编写程序找到某个人的最早的祖先。
规定每个人的名字都没有空格，且没有任意两个人的名字相同。最多可能有1000组父子关系，总人数最多可能达到50000人，家谱中的记载不超过30代。
【输入描述】
输入由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系中父亲只有一行，儿子可能有若干行；用#name的形式描写一组父子关系中的父亲的名字，用+name的形式描写一组父子关系中的儿子的名字，儿子的名字一定紧接着父亲的名字出现；
接下来用?name的形式表示要求该人的最早的祖先；（?name一定在父子关系描述结束之后出现）
最后用单独的一个$表示文件结束。
【输出描述】
按照输入文件的要求顺序，求出每一个要找祖先的人的祖先，格式：本人的名字+一个空格+祖先的名字+回车。
【样例输入】
#George +Rodney #Arthur +Gareth +Walter #Gareth +Edward ?Edward ?Walter ?Rodney ?Arthur $
【样例输出】
Edward Arthur Walter Arthur Rodney George Arthur Arthur
【题解】选班委
【题目描述】
小 T 和他的小伙伴们到 CZ 中学的创新实验班报到后的第一件事就是选班委，班主任 R 老师走上讲台宣布了选举办法，首先让全班 40 位同学依次上讲台做自我介绍，然后按照 职位一个一个依次进行选举，先选班长，再选学习委员……，选举办法是每人投一票，谁 的票数最高就选谁担任这个职位，最后围棋高手小 W 颇具大将风范被选为班长，学神小 Z 当选为学习委员那是众望所归，小 S 则有天生一副好嗓子，不但歌唱得好，并且能将多种 动物的叫声模仿得惟妙惟肖，因此当选为文体委员。小 T 同学在本次选举中负责计票，他 觉得手工计票太慢了，且容易出错，因此想请你编一个程序实现机器计票功能。这个程序 要能实现以下功能：全班共有 n 个同学，依次用 1 到 n 编号，共有 m 个人（包括班主任和 任课老师等）参与了投票，每张选票上写有一个同学的编号，得票最多的同学当选。
【输入描述】
输入数据第一行包含两个用空格隔开的正整数 n 和 m，其中 n≤200，m≤2000。
第二行有 m 个用空格隔开的不超过 n 的正整数，表示这 m 张选票上所写的编号。
【输出描述】
输出得票最多的那个同学的编号。如果同时有两名以上同学得票最多，输出编号最小的那个同学的编号。
【样例输入】
3 4 1 3 2 1
【样例输出】
1
【样例解释】
全班共有 3 位同学，共有 4 人进行了投票，其中有 2 人选了 1 号同学，选 2 号和 3 号
同学的都只有 1 人，最后 1 号同学得 2 票，2 号和 3 号同学各得 1 票，1 号同学得票最多， 当选班委。
【数据范围】
20%的数据满足：n≤3，m≤20
60%的数据满足：n≤100，m≤500
70%的数据满足：得票最多的同学是唯一的
100%的数据满足：n≤200，m≤2000
【题解】校运会
【题目描述】
校运会上，一共有N个参赛选手，已知N个选手的名字。然后老师告诉你M句话，话的内容是学生A与学生B在同一组里。如果学生A与学生B在同一组里，学生B与学生C也在同一组里，就说明学生A与学生C在同一组。
然后老师问你K句话，即学生X和学生Y是否在同一组里。若是，输出Yes，否则输出No。
【输入描述】
第一行N和M。
接下来N行输入每一个同学的名字。
再往下M行每行输入两个名字，且保证这两个名字都在上面 N行中出现过，表示这两个参赛选手在同一个组里。
接下来输入K。
最后输入K个老师的询问。
【输出描述】
对于每一个循环，输出Yes或者No
【样例输入】
10 6 Jack Mike ASDA Michel brabrabra HeHe HeHE papapa HeY Obama Jack Obama HeHe HeHE brabrabra HeHe Obama ASDA papapa Obama Obama HeHE 3 Mike Obama HeHE Jack papapa brabrabra
【样例输出】
No. Yes. Yes.
【数据范围】
2<=N<=2*10^4 1<=M<=10^6 1<=K<=10^6
【题解】合根植物
【题目描述】
w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。
这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。
如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？
【输入描述】
第一行，两个整数m，n，用空格分开，表示格子的行数、列数（1<m,n<1000）。
接下来一行，一个整数k，表示下面还有k行数据(0<k<100000)
接下来k行，第2+k行两个整数a，b，表示编号为a的小格子和编号为b的小格子合根了。
格子的编号一行一行，从上到下，从左到右编号。
比如：5 * 4 的小格子，编号：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
【输出描述】
一行，表示有多少株?
【样例输入】
5 4 16 2 3 1 5 5 9 4 8 7 8 9 10 10 11 11 12 10 14 12 16 14 18 17 18 15 19 19 20 9 13 13 17
【样例输出】
5
【数据结构】并查集2
【题解】亲戚
【题目描述】
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
规定：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