Code – 第67页

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

#include <cstdio>
#include <set>
using namespace std;
int father[10010];
int findFather(int x) {
    while (x != father[x])
        x = father[x];
    return x;
}
set<int> total;
void unionFather(int a, int b) {
    total.insert(a);
    total.insert(b);
    int fa = findFather(a), fb = findFather(b);
    if (fa < fb) father[fb] = fa;
    else father[fa] = fb;
}
int main() {
    for (int i = 0; i <= 10000; i++) father[i] = i;
    int n, k, t, s, q;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &k, &t);
        if (k == 1) unionFather(t, t);
        for (int j = 1; j < k; j++) {
            scanf("%d",&s);
            unionFather(t, s);
        }
    }
    set<int> cnt;
    for (auto it = total.begin(); it != total.end(); it++) 
        cnt.insert(findFather(*it));
    printf("%lu %lu\n", total.size(), cnt.size());
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        scanf("%d %d", &t, &s);
        printf("%c\n", findFather(t) == findFather(s) ? 'Y' : 'N');
    }
    return 0;
}

#include <cstdio>

#include <set>

using namespace std;

int father[10010];

int findFather(int x) {

while (x != father[x])

x = father[x];

return x;

}

set<int> total;

void unionFather(int a, int b) {

total.insert(a);

total.insert(b);

int fa = findFather(a), fb = findFather(b);

if (fa < fb) father[fb] = fa;

else father[fa] = fb;

}

int main() {

for (int i = 0; i <= 10000; i++) father[i] = i;

int n, k, t, s, q;

scanf("%d", &n);

for (int i = 0; i < n; i++) {

scanf("%d %d", &k, &t);

if (k == 1) unionFather(t, t);

for (int j = 1; j < k; j++) {

scanf("%d",&s);

unionFather(t, s);

}

set<int> cnt;

for (auto it = total.begin(); it != total.end(); it++)

cnt.insert(findFather(*it));

printf("%lu %lu\n", total.size(), cnt.size());

scanf("%d", &q);

for (int i = 0; i < q; i++) {

scanf("%d %d", &t, &s);

printf("%c\n", findFather(t) == findFather(s) ? 'Y' : 'N');

}

return 0;

}

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

具体代码如下：

#include <cstdio>
#include <cmath>
using namespace std;
int nonNegativeNum(double c[], int start) {
    int cnt = 0;
    for (int i = start; i >= 0; i--)
        if (abs(c[i]) + 0.05 >= 0.1) cnt++;
    return cnt;
}
void printPoly(double c[], int start) {
    printf("%d", nonNegativeNum(c, start));
    if (nonNegativeNum(c, start) == 0) printf(" 0 0.0");
    for (int i = start; i >= 0; i--)
        if (abs(c[i]) + 0.05 >= 0.1)
            printf(" %d %.1f", i, c[i]);
}
double c1[3000], c2[3000], c3[3000];
int main() {
    int m = 0, n = 0, t = 0, max1 = -1, max2= -1;
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%d", &t);
        max1 = max1 > t ? max1 : t;
        scanf("%lf", &c1[t]);
    }
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &t);
        max2 = max2 > t ? max2 : t;
        scanf("%lf", &c2[t]);
    }
    int t1 = max1, t2 = max2;
    while (t1 >= t2) {
        double c = c1[t1] / c2[t2];
        c3[t1 - t2] = c;
        for (int i = t1, j = t2; j >= 0; j--, i--) c1[i] -= c2[j] * c;
        while (abs(c1[t1]) < 0.000001) t1--;
    }
    printPoly(c3, max1 - max2);
    printf("\n");
    printPoly(c1, t1);
    return 0;
}

#include <cstdio>

#include <cmath>

using namespace std;

int nonNegativeNum(double c[], int start) {

int cnt = 0;

for (int i = start; i >= 0; i--)

if (abs(c[i]) + 0.05 >= 0.1) cnt++;

return cnt;

}

void printPoly(double c[], int start) {

printf("%d", nonNegativeNum(c, start));

if (nonNegativeNum(c, start) == 0) printf(" 0 0.0");

for (int i = start; i >= 0; i--)

if (abs(c[i]) + 0.05 >= 0.1)

printf(" %d %.1f", i, c[i]);

}

double c1[3000], c2[3000], c3[3000];

int main() {

int m = 0, n = 0, t = 0, max1 = -1, max2= -1;

scanf("%d", &m);

for (int i = 0; i < m; i++) {

scanf("%d", &t);

max1 = max1 > t ? max1 : t;

scanf("%lf", &c1[t]);

}

scanf("%d", &n);

for (int i = 0; i < n; i++) {

scanf("%d", &t);

max2 = max2 > t ? max2 : t;

scanf("%lf", &c2[t]);

}

int t1 = max1, t2 = max2;

while (t1 >= t2) {

double c = c1[t1] / c2[t2];

c3[t1 - t2] = c;

for (int i = t1, j = t2; j >= 0; j--, i--) c1[i] -= c2[j] * c;

while (abs(c1[t1]) < 0.000001) t1--;

}

printPoly(c3, max1 - max2);

printf("\n");

printPoly(c1, t1);

return 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～

N = int(input())
a = []
b = []
for i in range(N):
    temp = input().split()
    a.append(temp[0])
    b.append(int(temp[-1]))
mean2 = sum(b) / 2 / N
m = abs(int(b[0]) - mean2)
k = 0
for i in range(N):
    if abs(int(b[i]) - mean2) < m:
        m = abs(int(b[i] - mean2))
        k = i
print(str(int(mean2)) + ' ' + a[k])

N = int(input())

a = []

b = []

for i in range(N):

temp = input().split()

a.append(temp[0])

b.append(int(temp[-1]))

mean2 = sum(b) / 2 / N

m = abs(int(b[0]) - mean2)

k = 0

for i in range(N):

if abs(int(b[i]) - mean2) < m:

m = abs(int(b[i] - mean2))

k = i

print(str(int(mean2)) + ' ' + a[k])

[Python] L1-055 谁是赢家-PAT团体程序设计天梯赛GPLT

某电视台的娱乐节目有个表演评审环节，每次安排两位艺人表演，他们的胜负由观众投票和3名评委投票两部分共同决定。规则为：如果一位艺人的观众票数高，且得到至少1名评委的认可，该艺人就胜出；或艺人的观众票数低，但得到全部评委的认可，也可以胜出。节目保证投票的观众人数为奇数，所以不存在平票的情况。本题就请你用程序判断谁是赢家。

输入格式：
输入第一行给出 2 个不超过 1000 的正整数 Pa 和 Pb，分别是艺人 a 和艺人 b 得到的观众票数。题目保证这两个数字不相等。随后第二行给出 3 名评委的投票结果。数字 0 代表投票给 a，数字 1 代表投票给 b，其间以一个空格分隔。

输出格式：
按以下格式输出赢家：
The winner is x: P1 + P2
其中 x 是代表赢家的字母，P1 是赢家得到的观众票数，P2 是赢家得到的评委票数。

输入样例：
327 129
1 0 1

输出样例：
The winner is a: 327 + 1

PS：感谢github用户@zhuzihao-hz提供的pull request～

N = input().split()
M = input().split()
if N[0] > N[1]:
    if '0' in M:
        k = 0
        for i in M:
            if i == '0':
                k = k + 1
        print('The winner is a: ' + N[0] + ' + ' + str(k))
    else:
        print('The winner is b: ' + N[1] + ' + 3')
else:
    if '1' in M:
        k = 0
        for i in M:
            if i == '1':
                k = k + 1
        print('The winner is b: ' + N[1] + ' + ' + str(k))
    else:
        print('The winner is a: ' + N[0] + ' + 3')

N = input().split()

M = input().split()

if N[0] > N[1]:

if '0' in M:

k = 0

for i in M:

if i == '0':

k = k + 1

print('The winner is a: ' + N[0] + ' + ' + str(k))

else:

print('The winner is b: ' + N[1] + ' + 3')

else:

if '1' in M:

k = 0

for i in M:

if i == '1':

k = k + 1

print('The winner is b: ' + N[1] + ' + ' + str(k))

else:

print('The winner is a: ' + N[0] + ' + 3')

[Python] L1-053 电子汪-PAT团体程序设计天梯赛GPLT

据说汪星人的智商能达到人类4岁儿童的水平，更有些聪明汪会做加法计算。比如你在地上放两堆小球，分别有1只球和2只球，聪明汪就会用“汪！汪！汪！”表示1加2的结果是3。
本题要求你为电子宠物汪做一个模拟程序，根据电子眼识别出的两堆小球的个数，计算出和，并且用汪星人的叫声给出答案。

输入格式：
输入在一行中给出两个[1, 9]区间内的正整数A和B，用空格分隔。

输出格式：
在一行中输出A+B个“Wang!”。

输入样例：
2 1

输出样例：
Wang!Wang!Wang!

PS：感谢github用户@zhuzihao-hz提供的pull request～

N = input().split()
for i in range(int(N[0]) + int(N[1])):
    print('Wang!', end='')

N = input().split()

for i in range(int(N[0]) + int(N[1])):

print('Wang!', end='')

[Python] L1-052 2018我们要赢-PAT团体程序设计天梯赛GPLT

2018年天梯赛的注册邀请码是“2018wmyy”，意思就是“2018我们要赢”。本题就请你用汉语拼音输出这句话。

输入格式：
本题没有输入。

输出格式：
在第一行中输出：“2018”；第二行中输出：“wo3 men2 yao4 ying2 !”。

输入样例：
本题没有输入。

输出样例：
2018
wo3 men2 yao4 ying2 !

PS：感谢github用户@zhuzihao-hz提供的pull request～

print('2018')
print('wo3 men2 yao4 ying2 !')

1 2	print('2018') print('wo3 men2 yao4 ying2 !')