标签： GPLT

古人云：秀恩爱，分得快。
互联网上每天都有大量人发布大量照片，我们通过分析这些照片，可以分析人与人之间的亲密度。如果一张照片上出现了 K 个人，这些人两两间的亲密度就被定义为 1/K。任意两个人如果同时出现在若干张照片里，他们之间的亲密度就是所有这些同框照片对应的亲密度之和。下面给定一批照片，请你分析一对给定的情侣，看看他们分别有没有亲密度更高的异性朋友？
输入格式：
输入在第一行给出 2 个正整数：N（不超过1000，为总人数——简单起见，我们把所有人从 0 到 N-1 编号。为了区分性别，我们用编号前的负号表示女性）和 M（不超过1000，为照片总数）。随后 M 行，每行给出一张照片的信息，格式如下：
K P[1] … P[K]
其中 K（<= 500）是该照片中出现的人数，P[1] ~ P[K] 就是这些人的编号。最后一行给出一对异性情侣的编号 A 和 B。同行数字以空格分隔。题目保证每个人只有一个性别，并且不会在同一张照片里出现多次。
输出格式：
首先输出“A PA”，其中 PA 是与 A 最亲密的异性。如果 PA 不唯一，则按他们编号的绝对值递增输出；然后类似地输出“B PB”。但如果 A 和 B 正是彼此亲密度最高的一对，则只输出他们的编号，无论是否还有其他人并列。
输入样例 1：
10 4
4 -1 2 -3 4
4 2 -3 -5 -6
3 2 4 -5
3 -6 0 2
-3 2
输出样例 1：
-3 2
2 -5
2 -6
输入样例 2：
4 4
4 -1 2 -3 0
2 0 -3
2 2 -3
2 -1 2
-3 2
输出样例 2：
-3 2

分析：1.此题考查的是对 0 -0 的特殊处理。当遇到 0 时候把此人转为1000存储, 所以读数据的时候要以字符串形式读取
2.遍历每张照片，把与男主女主对应的异性亲密度用sum数字累加起来， 并维护maxn[1] maxn[2]， 为男主女主的最亲密值 和ans[1], ans[2]容器，为最亲密异性id。
3.判断男主女主是否互为最亲密，如果是，输出并return 0， 否则分别输出他们的最亲密好友
4.注意输出时候，因为把0当1000存储，会导致0号人排在最后，这是不符题意的，输出之前排个序，让1000排在最前面

在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。

输入格式：
输入在第一行给出一个正整数N（<= 10^4^），是已知小圈子的个数。随后N行，每行按下列格式给出一个小圈子里的人：
K P[1] P[2] … P[K]
其中K是小圈子里的人数，P[i]（i=1, .., K）是小圈子里每个人的编号。这里所有人的编号从1开始连续编号，最大编号不会超过10^4^。
之后一行给出一个非负整数Q（<= 10^4^），是查询次数。随后Q行，每行给出一对被查询的人的编号。

输出格式：
首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询，如果他们属于同一个部落，则在一行中输出“Y”，否则输出“N”。

输入样例：
4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7
输出样例：
10 2
Y
N

这仍然是一道关于A/B的题，只不过A和B都换成了多项式。你需要计算两个多项式相除的商Q和余R，其中R的阶数必须小于B的阶数。

输入格式：
输入分两行，每行给出一个非零多项式，先给出A，再给出B。每行的格式如下：

N e[1] c[1] … e[N] c[N]
其中N是该多项式非零项的个数，e[i]是第i个非零项的指数，c[i]是第i个非零项的系数。各项按照指数递减的顺序给出，保证所有指数是各不相同的非负整数，所有系数是非零整数，所有整数在整型范围内。

输出格式：
分两行先后输出商和余，输出格式与输入格式相同，输出的系数保留小数点后1位。同行数字间以1个空格分隔，行首尾不得有多余空格。注意：零多项式是一个特殊多项式，对应输出为0 0 0.0。但非零多项式不能输出零系数（包括舍入后为0.0）的项。在样例中，余多项式其实有常数项-1/27，但因其舍入后为0.0，故不输出。

输入样例：
4 4 1 2 -3 1 -1 0 -1
3 2 3 1 -2 0 1
输出样例：
3 2 0.3 1 0.2 0 -1.0
1 1 -3.1

分析：对于两个多项式A和B，题目给出的必定不会是连续降幂的，根据多项式的除法原理，我们需要缺幂项补零。例如，题中给出的$x^4-3x^2-x-1$是缺3次幂的，将缺幂项补上之后，就变成了$x^4+0x^3-3x^2-x-1$。由此，我们可以用一个数组来保存一个多项式，即数组的下标对应多项式的指数，下标对应的单元表示多项式的系数，如数组[-1, -1, -3, 0, 1]。
若已知A多项式的最高次幂为t1, B多项式的最高次幂为t2, 则第一次除法商的最高次幂为t1 – t2, 最高次幂的系数为A[t1] / B[t2], 然后用A[i] -= B[i – (t1 – t2)] * A[t1] / B[t2], 其中i从A的最高次幂t1到大于等于t1 – t2, 这样就算完成了一个除法了。例如A = [-1, -1, -3, 0, 1], B = [1, -2, 3], 则t1 = 4, t2= 2, 所以第一次除法商的最高次幂为2, 系数为A[4] / A[2] = 0.3, 循环A[i] -= B[i – (t1 – t2)] * A[t1] / B[t2], i从4到2, 得到新的A=[-1, -1, -10/3, 2/3, 0], 然后重复上面的步骤, 直到A的最高项幂次小于B的最高项幂次, 此时的A就是余项。

[两个可能会让结果出现非零项多项式的测试用例]
1 2 1
1 3 1

1 2 1
1 2 1
[一个比较好算一点的一般测试用例]
3 3 1 2 -12 0 -42
2 1 1 0 -3
// ouput
3 2 1.0 1 -9.0 0 -27.0
1 0 -123.0

具体代码如下：

给定一个单链表 L~1~→L~2~→…→L~n-1~→L~n~，请编写程序将链表重新排列为 L~n~→L~1~→L~n-1~→L~2~→…。例如：给定L为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3。

输入格式：

每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数，即正整数N (<= 10^5^)。结点的地址是5位非负整数，NULL地址用-1表示。

接下来有N行，每行格式为：

Address Data Next

其中Address是结点地址；Data是该结点保存的数据，为不超过10^5^的正整数；Next是下一结点的地址。题目保证给出的链表上至少有两个结点。

输出格式：

对每个测试用例，顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。

输入样例：
00100 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

输出样例：
68237 6 00100
00100 1 99999
99999 5 12309
12309 2 00000
00000 4 33218
33218 3 -1

分析：用结构体｛id, data, next｝存储节点信息，模拟链表。先遍历一遍链表，把有用数节点存起来（甲级乙级中，姥姥为了加大难度，加了好多不在链表中的干扰数据）然后从后往前交替输出,（先把顺序存在ans中,待会统一输出），l, r代表将要输出的节点位置，当（l-1）-（r+1） == 1时都遍历一遍了，可退出循环~

对于在中国大学MOOC学习“数据结构”课程的学生，想要获得一张合格证书，总评成绩必须达到 60 分及以上，并且有另加福利：总评分在 [G, 100] 区间内者，可以得到 50 元 PAT 代金券；在 [60, G) 区间内者，可以得到 20 元PAT代金券。全国考点通用，一年有效。同时任课老师还会把总评成绩前 K 名的学生列入课程“名人堂”。本题就请你编写程序，帮助老师列出名人堂的学生，并统计一共发出了面值多少元的 PAT 代金券。

输入格式：
输入在第一行给出 3 个整数，分别是 N（不超过 10 000 的正整数，为学生总数）、G（在 (60,100) 区间内的整数，为题面中描述的代金券等级分界线）、K（不超过 100 且不超过 N 的正整数，为进入名人堂的最低名次）。接下来 N 行，每行给出一位学生的账号（长度不超过15位、不带空格的字符串）和总评成绩（区间 [0, 100] 内的整数），其间以空格分隔。题目保证没有重复的账号。

输出格式：
首先在一行中输出发出的 PAT 代金券的总面值。然后按总评成绩非升序输出进入名人堂的学生的名次、账号和成绩，其间以 1 个空格分隔。需要注意的是：成绩相同的学生享有并列的排名，排名并列时，按账号的字母序升序输出。

输入样例：
10 80 5
cy@zju.edu.cn 78
cy@pat-edu.com 87
1001@qq.com 65
uh-oh@163.com 96
test@126.com 39
anyone@qq.com 87
zoe@mit.edu 80
jack@ucla.edu 88
bob@cmu.edu 80
ken@163.com 70

输出样例：
360
1 uh-oh@163.com 96
2 jack@ucla.edu 88
3 anyone@qq.com 87
3 cy@pat-edu.com 87
5 bob@cmu.edu 80
5 zoe@mit.edu 80

分析：给每个大于60分的学生发20块，如果还有人同时大于G，在发30块。把所有学生生排序后，重新排名。第一个学生为第一名,以后的学生如果分数和前一个学生并列，他的名次和前一个同学名次一样，否则他的名次为下标加一

本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。

输入格式：
输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） —— 简单起见，我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号，其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。

输出格式：
首先输出最小的辈分（老祖宗的辈分为 1，以下逐级递增）。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔，行首尾不得有多余空格。

输入样例：
9
2 6 5 5 -1 5 6 4 7

输出样例：
4
1 9

分析：广度优先搜索最长路径问题（深搜可能会超时），老祖宗的父母即root的id用0表示 ，队列中的结构体成员分别是，人的编号和所处层数。