1087 有多少不同的值(20 分)-PAT乙级真题

当自然数 n 依次取 1、2、3、……、N 时,算式 ⌊n/2⌋+⌊n/3⌋+⌊n/5⌋ 有多少个不同的值?(注:⌊x⌋ 为取整函数,表示不超过 x 的最大自然数,即 x 的整数部分。)

输入格式:
输入给出一个正整数 N(2≤N≤104​​)。

输出格式:
在一行中输出题面中算式取到的不同值的个数。

输入样例:
2017
输出样例:
1480

分析:把i/2 + i/3 + i/n的值插入到set中,输出set的size就是算式中不同值的个数~

1090 危险品装箱(25 分)-PAT乙级真题

集装箱运输货物时,我们必须特别小心,不能把不相容的货物装在一只箱子里。比如氧化剂绝对不能跟易燃液体同箱,否则很容易造成爆炸。

本题给定一张不相容物品的清单,需要你检查每一张集装箱货品清单,判断它们是否能装在同一只箱子里。

输入格式:
输入第一行给出两个正整数:N (≤10^4) 是成对的不相容物品的对数;M (≤100) 是集装箱货品清单的单数。

随后数据分两大块给出。第一块有 N 行,每行给出一对不相容的物品。第二块有 M 行,每行给出一箱货物的清单,格式如下:

K G[1] G[2] … G[K]
其中 K (≤1000) 是物品件数,G[i] 是物品的编号。简单起见,每件物品用一个 5 位数的编号代表。两个数字之间用空格分隔。

输出格式:
对每箱货物清单,判断是否可以安全运输。如果没有不相容物品,则在一行中输出 Yes,否则输出 No。

输入样例:
6 3
20001 20002
20003 20004
20005 20006
20003 20001
20005 20004
20004 20006
4 00001 20004 00002 20003
5 98823 20002 20003 20006 10010
3 12345 67890 23333
输出样例:
No
Yes
Yes

分析:用map存储每一个货物的所有不兼容货物~在判断给出的一堆货物是否是相容的时候,判断任一货物的不兼容货物是否在这堆货物中~如果存在不兼容的货物,则这堆货物不能相容~如果遍历完所有的货物,都找不到不兼容的两个货物,则这堆货物就是兼容的~

L2-028 秀恩爱分得快-PAT团体程序设计天梯赛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排在最前面

L2-024. 部落-PAT团体程序设计天梯赛GPLT

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

输入格式:
输入在第一行给出一个正整数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

 

L2-018. 多项式A除以B -PAT团体程序设计天梯赛GPLT

这仍然是一道关于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

具体代码如下:

[Python] L1-056 猜数字-PAT团体程序设计天梯赛GPLT

一群人坐在一起,每人猜一个 100 以内的数,谁的数字最接近大家平均数的一半就赢。本题就要求你找出其中的赢家。

输入格式:
输入在第一行给出一个正整数N(<= 10^4^)。随后 N 行,每行给出一个玩家的名字(由不超过8个英文字母组成的字符串)和其猜的正整数(<= 100)。

输出格式:
在一行中顺序输出:大家平均数的一半(只输出整数部分)、赢家的名字,其间以空格分隔。题目保证赢家是唯一的。

输入样例:
7
Bob 35
Amy 28
James 98
Alice 11
Jack 45
Smith 33
Chris 62

输出样例:
22 Amy

PS:感谢github用户@zhuzihao-hz提供的pull request~