Code – 第18页 – 柳婼の blog

L2-031 深入虎穴 (25 分)-PAT 团体程序设计天梯赛 GPLT

著名的王牌间谍 007 需要执行一次任务，获取敌方的机密情报。已知情报藏在一个地下迷宫里，迷宫只有一个入口，里面有很多条通路，每条路通向一扇门。每一扇门背后或者是一个房间，或者又有很多条路，同样是每条路通向一扇门…… 他的手里有一张表格，是其他间谍帮他收集到的情报，他们记下了每扇门的编号，以及这扇门背后的每一条通路所到达的门的编号。007 发现不存在两条路通向同一扇门。

内线告诉他，情报就藏在迷宫的最深处。但是这个迷宫太大了，他需要你的帮助 —— 请编程帮他找出距离入口最远的那扇门。

输入格式：
输入首先在一行中给出正整数 N（<105），是门的数量。最后 N 行，第 i 行（1≤i≤N）按以下格式描述编号为 i 的那扇门背后能通向的门：

K D[1] D[2] … D[K]
其中 K 是通道的数量，其后是每扇门的编号。

输出格式：
在一行中输出距离入口最远的那扇门的编号。题目保证这样的结果是唯一的。

输入样例：
13
3 2 3 4
2 5 6
1 7
1 8
1 9
0
2 11 10
1 13
0
0
1 12
0
0

输出样例：
12

分析：用Edge储存编号为i的门可以通向的门，因为门可以从这里走过去，也可以从那里走过来，所以不要忘记从可以通向的那个门朝第i号门建边。vis[i]表示第i个门是否访问过，使用BFS从1号门出发走一遍，用one来保存队列中门的编号，根据结果唯一以及BFS的特性，最后一个one即是最远的那个门～

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
int N, K, D, one, vis[100001];
vector<int> Edge[100001];
queue<int> Q;
int main() {
    cin >> N;
    for (int i = 1; i <= N; ++i) {
        cin >> K;
        while(K--) {
            cin >> D;
            Edge[D].push_back(i);
            Edge[i].push_back(D);
        }
    }
    Q.push(1);
    vis[1] = 1;
    while(!Q.empty()) {
        one = Q.front();
        Q.pop();
        for (auto v:Edge[one]) {
            if (vis[v]) continue;
            vis[v] = 1;
            Q.push(v);
        }
    }
    cout << one;
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>

int N, K, D, one, vis[100001];

vector<int> Edge[100001];

queue<int> Q;

int main() {

cin >> N;

for (int i = 1; i <= N; ++i) {

cin >> K;

while(K--) {

cin >> D;

Edge[D].push_back(i);

Edge[i].push_back(D);

}

Q.push(1);

vis[1] = 1;

while(!Q.empty()) {

one = Q.front();

Q.pop();

for (auto v:Edge[one]) {

if (vis[v]) continue;

vis[v] = 1;

Q.push(v);

}

cout << one;

return 0;

}

L2-030 冰岛人 (25 分)-PAT 团体程序设计天梯赛 GPLT

2018年世界杯，冰岛队因1:1平了强大的阿根廷队而一战成名。好事者发现冰岛人的名字后面似乎都有个“松”（son），于是有网友科普如下：

冰岛人沿用的是维京人古老的父系姓制，孩子的姓等于父亲的名加后缀，如果是儿子就加 sson，女儿则加 sdottir。因为冰岛人口较少，为避免近亲繁衍，本地人交往前先用个 App 查一下两人祖宗若干代有无联系。本题就请你实现这个 App 的功能。

输入格式：
输入首先在第一行给出一个正整数 N（1<N≤105），为当地人口数。随后 N 行，每行给出一个人名，格式为：名姓（带性别后缀），两个字符串均由不超过 20 个小写的英文字母组成。维京人后裔是可以通过姓的后缀判断其性别的，其他人则是在姓的后面加 m 表示男性、f 表示女性。题目保证给出的每个维京家族的起源人都是男性。

随后一行给出正整数 M，为查询数量。随后 M 行，每行给出一对人名，格式为：名1 姓1 名2 姓2。注意：这里的姓是不带后缀的。四个字符串均由不超过 20 个小写的英文字母组成。

题目保证不存在两个人是同名的。

输出格式：
对每一个查询，根据结果在一行内显示以下信息：

若两人为异性，且五代以内无公共祖先，则输出 Yes；
若两人为异性，但五代以内（不包括第五代）有公共祖先，则输出 No；
若两人为同性，则输出 Whatever；
若有一人不在名单内，则输出 NA。
所谓“五代以内无公共祖先”是指两人的公共祖先（如果存在的话）必须比任何一方的曾祖父辈分高。

输入样例：
15
chris smithm
adam smithm
bob adamsson
jack chrissson
bill chrissson
mike jacksson
steve billsson
tim mikesson
april mikesdottir
eric stevesson
tracy timsdottir
james ericsson
patrick jacksson
robin patricksson
will robinsson
6
tracy tim james eric
will robin tracy tim
april mike steve bill
bob adam eric steve
tracy tim tracy tim
x man april mikes

输出样例：
Yes
No
No
Whatever
Whatever
NA

分析：通过判断姓氏末位的字母来判断性别以及是否是维京人，如果是维京人还需要切割尾缀并将父亲姓名存储，之后再查询的时候，进入check函数内，枚举五代内的关系，判断是否有公共祖先～Record[A]用来存储A的性别以及父亲姓名，最后按题意输出～

#include <bits/stdc++.h>
using namespace std;
#define pis pair<int, string>
int N, M;
string fName, sName, temp;
map<string, pis> Record;
string check(string a, string b) {
    int cnt1 = 0, cnt2;
    while (a != "") {
        cnt2 = 0;
        string b2 = b;
        while (b2 != "") {
            if (a == b2 && (cnt1 < 4 || cnt2 < 4)) return "No\n";
            if (cnt1 >= 4 && cnt2 >= 4) return "Yes\n";
            b2 = Record[b2].second;
            cnt2++;
        }
        a = Record[a].second;
        cnt1++;
    }
    return "Yes\n";
}
int main() {
    cin >> N;
    while(N--){
        cin >> fName >> sName;
        if (sName.back() == 'n') Record[fName] = {1, sName.substr(0, sName.length() - 4)};
        else if (sName.back() == 'r') Record[fName] = {0, sName.substr(0, sName.length() - 7)};
        else if (sName.back() == 'm') Record[fName].first = 1;
        else Record[fName].first = 0;
    }
    cin >> M;
    while(M--){
        cin >> fName >> temp >> sName >> temp;
        if (!Record.count(fName) || !Record.count(sName)) cout << "NA\n";
        else if(Record[fName].first == Record[sName].first) cout << "Whatever\n";
        else cout << check(fName, sName);
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define pis pair<int, string>

int N, M;

string fName, sName, temp;

map<string, pis> Record;

string check(string a, string b) {

int cnt1 = 0, cnt2;

while (a != "") {

cnt2 = 0;

string b2 = b;

while (b2 != "") {

if (a == b2 && (cnt1 < 4 || cnt2 < 4)) return "No\n";

if (cnt1 >= 4 && cnt2 >= 4) return "Yes\n";

b2 = Record[b2].second;

cnt2++;

}

a = Record[a].second;

cnt1++;

}

return "Yes\n";

}

int main() {

cin >> N;

while(N--){

cin >> fName >> sName;

if (sName.back() == 'n') Record[fName] = {1, sName.substr(0, sName.length() - 4)};

else if (sName.back() == 'r') Record[fName] = {0, sName.substr(0, sName.length() - 7)};

else if (sName.back() == 'm') Record[fName].first = 1;

else Record[fName].first = 0;

}

cin >> M;

while(M--){

cin >> fName >> temp >> sName >> temp;

if (!Record.count(fName) || !Record.count(sName)) cout << "NA\n";

else if(Record[fName].first == Record[sName].first) cout << "Whatever\n";

else cout << check(fName, sName);

}

return 0;

}

L2-029 特立独行的幸福 (25 分)-PAT 团体程序设计天梯赛 GPLT

对一个十进制数的各位数字做一次平方和，称作一次迭代。如果一个十进制数能通过若干次迭代得到 1，就称该数为幸福数。1 是一个幸福数。此外，例如 19 经过 1 次迭代得到 82，2 次迭代后得到 68，3 次迭代后得到 100，最后得到 1。则 19 就是幸福数。显然，在一个幸福数迭代到 1 的过程中经过的数字都是幸福数，它们的幸福是依附于初始数字的。例如 82、68、100 的幸福是依附于 19 的。而一个特立独行的幸福数，是在一个有限的区间内不依附于任何其它数字的；其独立性就是依附于它的的幸福数的个数。如果这个数还是个素数，则其独立性加倍。例如 19 在区间[1, 100] 内就是一个特立独行的幸福数，其独立性为 2×4=8。

另一方面，如果一个大于1的数字经过数次迭代后进入了死循环，那这个数就不幸福。例如 29 迭代得到 85、89、145、42、20、4、16、37、58、89、…… 可见 89 到 58 形成了死循环，所以 29 就不幸福。

本题就要求你编写程序，列出给定区间内的所有特立独行的幸福数和它的独立性。

输入格式：
输入在第一行给出闭区间的两个端点：1<A<B≤104。

输出格式：
按递增顺序列出给定闭区间 [A,B] 内的所有特立独行的幸福数和它的独立性。每对数字占一行，数字间以 1 个空格分隔。

如果区间内没有幸福数，则在一行中输出 SAD。

输入样例 1：
10 40

输出样例 1：
19 8
23 6
28 3
31 4
32 3
注意：样例中，10、13 也都是幸福数，但它们分别依附于其他数字（如 23、31 等等），所以不输出。其它数字虽然其实也依附于其它幸福数，但因为那些数字不在给定区间 [10, 40] 内，所以它们在给定区间内是特立独行的幸福数。

输入样例 2：
110 120

输出样例 2：
SAD

分析：1、判断一个数是不是特立独行的幸福数，同时累计其独立性。2、判断其是不是素数，是的话独立性需要乘二。用num[i]储存第i个元素的独立性，用notIndep[i]表示第i各数不是特立独行的幸福数——将所有迭代产生的数标记为1，ans用来储存可能的幸福数，mark用来存储一个数迭代过程中产生的数，如果重复则说明不是幸福数～

#include <bits/stdc++.h>
using namespace std;
int A, B, flag, num[10001], notIndep[10001];
bool isPrime(int a) {
    if (a == 1) return false;
    for (int i = 2; i <= sqrt(a); i++)
        if (a % i == 0) return false;
    return true;
}
bool isIndep(int x) {
    set<int> mark;
    int X = x, temp1, temp2;
    while (X != 1) {
        mark.insert(X);
        temp1 = 0;
        while (X) {
            temp2 = X % 10;
            X /= 10;
            temp1 += temp2 * temp2;
        }
        num[x]++;
        notIndep[temp1] = 1;
        X = temp1;
        if (mark.count(X)) return false;
    } 
    return true;
}
int main() {
    cin >> A >> B;
    vector<int> ans;
    for (int i = A; i <= B; i++)
        if (isIndep(i)) ans.push_back(i);
    for (int i = 0; i < ans.size(); i++) {
        if (isPrime(ans[i])) num[ans[i]] <<= 1;
        if (!notIndep[ans[i]]) {
            cout << ans[i] << ' ' << num[ans[i]] << endl;
            flag = 1;
        }
    }
    if (!flag) cout << "SAD"; 
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int A, B, flag, num[10001], notIndep[10001];

bool isPrime(int a) {

if (a == 1) return false;

for (int i = 2; i <= sqrt(a); i++)

if (a % i == 0) return false;

return true;

}

bool isIndep(int x) {

set<int> mark;

int X = x, temp1, temp2;

while (X != 1) {

mark.insert(X);

temp1 = 0;

while (X) {

temp2 = X % 10;

X /= 10;

temp1 += temp2 * temp2;

}

num[x]++;

notIndep[temp1] = 1;

X = temp1;

if (mark.count(X)) return false;

}

return true;

}

int main() {

cin >> A >> B;

vector<int> ans;

for (int i = A; i <= B; i++)

if (isIndep(i)) ans.push_back(i);

for (int i = 0; i < ans.size(); i++) {

if (isPrime(ans[i])) num[ans[i]] <<= 1;

if (!notIndep[ans[i]]) {

cout << ans[i] << ' ' << num[ans[i]] << endl;

flag = 1;

}

if (!flag) cout << "SAD";

return 0;

}

L1-080 乘法口诀数列 (20 分)-PAT 团体程序设计天梯赛 GPLT

本题要求你从任意给定的两个 1 位数字 a1和 a2 开始，用乘法口诀生成一个数列 {an}，规则为从 a1 开始顺次进行，每次将当前数字与后面一个数字相乘，将结果贴在数列末尾。如果结果不是 1 位数，则其每一位都应成为数列的一项。

输入格式：
输入在一行中给出 3 个整数，依次为 a1、a2 和 n，满足 0≤a1 ,a2≤9，0<n≤103。

输出格式：
在一行中输出数列的前 n 项。数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：
2 3 10

输出样例：
2 3 6 1 8 6 8 4 8 4

样例解释：
数列前 2 项为 2 和 3。从 2 开始，因为 2×3=6，所以第 3 项是 6。因为 3×6=18，所以第 4、5 项分别是 1、8。依次类推…… 最后因为第 6 项有 6×8=48，对应第 10、11 项应该是 4、8。而因为只要求输出前 10 项，所以在输出 4 后结束。

分析：用A[i]表示数列的第i项，用last表示当前空着的位置，用sum表示第i项与第i+1项的乘积，如果大于10，则需要用两个位置来储存，最后输出前n项～

#include <bits/stdc++.h>
using namespace std;
int A, B, flag, num[10001], notIndep[10001];
bool isPrime(int a) {
    if (a == 1) return false;
    for (int i = 2; i <= sqrt(a); i++)
        if (a % i == 0) return false;
    return true;
}
bool isIndep(int x) {
    set<int> mark;
    int X = x, temp1, temp2;
    while (X != 1) {
        mark.insert(X);
        temp1 = 0;
        while (X) {
            temp2 = X % 10;
            X /= 10;
            temp1 += temp2 * temp2;
        }
        num[x]++;
        notIndep[temp1] = 1;
        X = temp1;
        if (mark.count(X)) return false;
    } 
    return true;
}
int main() {
    cin >> A >> B;
    vector<int> ans;
    for (int i = A; i <= B; i++)
        if (isIndep(i)) ans.push_back(i);
    for (int i = 0; i < ans.size(); i++) {
        if (isPrime(ans[i])) num[ans[i]] <<= 1;
        if (!notIndep[ans[i]]) {
            cout << ans[i] << ' ' << num[ans[i]] << endl;
            flag = 1;
        }
    }
    if (!flag) cout << "SAD"; 
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int A, B, flag, num[10001], notIndep[10001];

bool isPrime(int a) {

if (a == 1) return false;

for (int i = 2; i <= sqrt(a); i++)

if (a % i == 0) return false;

return true;

}

bool isIndep(int x) {

set<int> mark;

int X = x, temp1, temp2;

while (X != 1) {

mark.insert(X);

temp1 = 0;

while (X) {

temp2 = X % 10;

X /= 10;

temp1 += temp2 * temp2;

}

num[x]++;

notIndep[temp1] = 1;

X = temp1;

if (mark.count(X)) return false;

}

return true;

}

int main() {

cin >> A >> B;

vector<int> ans;

for (int i = A; i <= B; i++)

if (isIndep(i)) ans.push_back(i);

for (int i = 0; i < ans.size(); i++) {

if (isPrime(ans[i])) num[ans[i]] <<= 1;

if (!notIndep[ans[i]]) {

cout << ans[i] << ' ' << num[ans[i]] << endl;

flag = 1;

}

if (!flag) cout << "SAD";

return 0;

}

L1-079 天梯赛的善良 (20 分)-PAT 团体程序设计天梯赛 GPLT

天梯赛是个善良的比赛。善良的命题组希望将题目难度控制在一个范围内，使得每个参赛的学生都有能做出来的题目，并且最厉害的学生也要非常努力才有可能得到高分。

于是命题组首先将编程能力划分成了 106个等级（太疯狂了，这是假的），然后调查了每个参赛学生的编程能力。现在请你写个程序找出所有参赛学生的最小和最大能力值，给命题组作为出题的参考。

输入格式：
输入在第一行中给出一个正整数 N（≤2×104），即参赛学生的总数。随后一行给出 N 个不超过 106的正整数，是参赛学生的能力值。

输出格式：
第一行输出所有参赛学生的最小能力值，以及具有这个能力值的学生人数。第二行输出所有参赛学生的最大能力值，以及具有这个能力值的学生人数。同行数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：
10
86 75 233 888 666 75 886 888 75 666

输出样例：
75 3
888 2

分析：用A记录每个数字出现了多少次，用maxn记录最大的那个数，用minn记录最小的那个数～

#include <bits/stdc++.h>
using namespace std;
map<int, int> A;
int n, minn = INT_MAX, maxn = INT_MIN;
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        A[t]++;
        if (minn > t) minn = t;
        if (maxn < t) maxn = t;
    }
    cout << minn << ' ' << A[minn] << '\n' << da << ' ' << A[maxn];
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

map<int, int> A;

int n, minn = INT_MAX, maxn = INT_MIN;

int main() {

cin >> n;

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

int t;

cin >> t;

A[t]++;

if (minn > t) minn = t;

if (maxn < t) maxn = t;

}

cout << minn << ' ' << A[minn] << '\n' << da << ' ' << A[maxn];

return 0;

}

L1-078 吉老师的回归 (15 分)-PAT 团体程序设计天梯赛 GPLT

曾经在天梯赛大杀四方的吉老师决定回归天梯赛赛场啦！

为了简化题目，我们不妨假设天梯赛的每道题目可以用一个不超过 500 的、只包括可打印符号的字符串描述出来，如：Problem A: Print “Hello world!”。

众所周知，吉老师的竞赛水平非常高超，你可以认为他每道题目都会做（事实上也是……）。因此，吉老师会按照顺序看题并做题。但吉老师水平太高了，所以签到题他就懒得做了（浪费时间），具体来说，假如题目的字符串里有 qiandao 或者 easy（区分大小写）的话，吉老师看完题目就会跳过这道题目不做。

现在给定这次天梯赛总共有几道题目以及吉老师已经做完了几道题目，请你告诉大家吉老师现在正在做哪个题，或者吉老师已经把所有他打算做的题目做完了。

提醒：天梯赛有分数升级的规则，如果不做签到题可能导致团队总分不足以升级，一般的选手请千万不要学习吉老师的酷炫行为！

输入格式：
输入第一行是两个正整数 N,M (1≤M≤N≤30)，表示本次天梯赛有 N 道题目，吉老师现在做完了 M 道。

接下来 N 行，每行是一个符合题目描述的字符串，表示天梯赛的题目内容。吉老师会按照给出的顺序看题——第一行就是吉老师看的第一道题，第二行就是第二道，以此类推。

输出格式：
在一行中输出吉老师当前正在做的题目对应的题面（即做完了 M 道题目后，吉老师正在做哪个题）。如果吉老师已经把所有他打算做的题目做完了，输出一行 Wo AK le。

输入样例 1：
5 1
L1-1 is a qiandao problem.
L1-2 is so…easy.
L1-3 is Easy.
L1-4 is qianDao.
Wow, such L1-5, so easy.
输出样例 1：
L1-4 is qianDao.
输入样例 2：
5 4
L1-1 is a-qiandao problem.
L1-2 is so easy.
L1-3 is Easy.
L1-4 is qianDao.
Wow, such L1-5, so!!easy.
输出样例 2：
Wo AK le

分析：用getline整行输入带空格字符串，用cnt记录非签到题数量，并查询其中是否带有”qiandao”或”easy”，当cnt等于m时，用ans记录当前正在做的题目对应的题面。如果cnt的数量小于等于m，则表示已经AK～

#include <bits/stdc++.h>
using namespace std;
int n, m, cnt;
string s, ans;
int check(string a) {
    for (int i = 0; i < a.length(); i++)
        if (a.substr(i, 7) == "qiandao" || a.substr(i, 4) == "easy") return 1;
    return 0;
}
int main() {
    cin >> n >> m;
    getchar();
    for (int i = 0; i < n; i++) {
        getline(cin, s);
        if (check(s)) continue;
        else {
            if (cnt == m) ans = s;
            cnt++;
        }
    }
    if (cnt <= m) cout << "Wo AK le";
    else cout << ans;
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int n, m, cnt;

string s, ans;

int check(string a) {

for (int i = 0; i < a.length(); i++)

if (a.substr(i, 7) == "qiandao" || a.substr(i, 4) == "easy") return 1;

return 0;

}

int main() {

cin >> n >> m;

getchar();

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

getline(cin, s);

if (check(s)) continue;

else {

if (cnt == m) ans = s;

cnt++;

}

if (cnt <= m) cout << "Wo AK le";

else cout << ans;

return 0;

}