liuchuo – 第9页 – 柳婼の blog

L1-083 谁能进图书馆-PAT团体程序设计天梯赛GPLT

为了保障安静的阅读环境，有些公共图书馆对儿童入馆做出了限制。例如“12 岁以下儿童禁止入馆，除非有 18 岁以上（包括 18 岁）的成人陪同”。现在有两位小/大朋友跑来问你，他们能不能进去？请你写个程序自动给他们一个回复。

输入格式：

输入在一行中给出 4 个整数：

禁入年龄线陪同年龄线询问者1的年龄询问者2的年龄

这里的禁入年龄线是指严格小于该年龄的儿童禁止入馆；陪同年龄线是指大于等于该年龄的人士可以陪同儿童入馆。默认两个询问者的编号依次分别为 1 和 2；年龄和年龄线都是 [1, 200] 区间内的整数，并且保证 陪同年龄线 严格大于 禁入年龄线。

输出格式：

在一行中输出对两位询问者的回答，如果可以进就输出 年龄-Y，否则输出 年龄-N，中间空 1 格，行首尾不得有多余空格。

在第二行根据两个询问者的情况输出一句话：

如果两个人必须一起进，则输出 qing X zhao gu hao Y，其中 X 是陪同人的编号， Y 是小孩子的编号；
如果两个人都可以进但不是必须一起的，则输出 huan ying ru guan；
如果两个人都进不去，则输出 zhang da zai lai ba；
如果一个人能进一个不能，则输出 X: huan ying ru guan，其中 X 是可以入馆的那个人的编号。

输入样例 1：

12 18 18 8

输出样例 1：

18-Y 8-Y
qing 1 zhao gu hao 2

输入样例 2：

12 18 10 15

输出样例 2：

10-N 15-Y
2: huan ying ru guan

#include <iostream>
using namespace std;
int prohibit, accompany, q1, q2;
int main() {
    cin >> prohibit >> accompany >> q1 >> q2;
    cout << q1 << '-';
    if (q1 >= prohibit && q2 >= prohibit) cout << "Y " << q2 << "-Y\nhuan ying ru guan";
    else if (q1 < prohibit && q2 < prohibit) cout << "N " << q2 << "-N\nzhang da zai lai ba";
    else if (q1 >= accompany) cout << "Y " << q2 << "-Y\nqing 1 zhao gu hao 2";
    else if (q2 >= accompany) cout << "Y " << q2 << "-Y\nqing 2 zhao gu hao 1";
    else if (q1 >= prohibit) cout << "Y " << q2 << "-N\n1: huan ying ru guan";
    else cout << "N " << q2 << "-Y\n2: huan ying ru guan";
    return 0;
}

#include <iostream>

using namespace std;

int prohibit, accompany, q1, q2;

int main() {

cin >> prohibit >> accompany >> q1 >> q2;

cout << q1 << '-';

if (q1 >= prohibit && q2 >= prohibit) cout << "Y " << q2 << "-Y\nhuan ying ru guan";

else if (q1 < prohibit && q2 < prohibit) cout << "N " << q2 << "-N\nzhang da zai lai ba";

else if (q1 >= accompany) cout << "Y " << q2 << "-Y\nqing 1 zhao gu hao 2";

else if (q2 >= accompany) cout << "Y " << q2 << "-Y\nqing 2 zhao gu hao 1";

else if (q1 >= prohibit) cout << "Y " << q2 << "-N\n1: huan ying ru guan";

else cout << "N " << q2 << "-Y\n2: huan ying ru guan";

return 0;

}

L1-082 种钻石-PAT团体程序设计天梯赛GPLT

2019年10月29日，中央电视台专题报道，中国科学院在培育钻石领域，取得科技突破。科学家们用金刚石的籽晶片作为种子，利用甲烷气体在能量作用下形成碳的等离子体，慢慢地沉积到钻石种子上，一周“种”出了一颗 1 克拉大小的钻石。

本题给出钻石的需求量和人工培育钻石的速度，请你计算出货需要的时间。

输入格式：

输入在一行中给出钻石的需求量 N（不超过 10^7 的正整数，以微克拉为单位）和人工培育钻石的速度 v（1≤v≤200，以微克拉/天为单位的整数）。

输出格式：

在一行中输出培育 N 微克拉钻石需要的整数天数。不到一天的时间不算在内。

输入样例：

102000 130

输出样例：

784

#include <iostream>
using namespace std;
int N, v;
int main() {
    cin >> N >> v;
    cout << N / v;
    return 0;
}

#include <iostream>

using namespace std;

int N, v;

int main() {

cin >> N >> v;

cout << N / v;

return 0;

}

L1-081 今天我要赢-PAT团体程序设计天梯赛GPLT

2018 年我们曾经出过一题，是输出“2018 我们要赢”。今年是 2022 年，你要输出的句子变成了“我要赢！就在今天！”然后以比赛当天的日期落款。

输入格式：

本题没有输入。

输出格式：

输出分 2 行。在第一行中输出 I'm gonna win! Today!，在第二行中用 年年年年-月月-日日 的格式输出比赛当天的日期。已知比赛的前一天是 2022-04-22。

输入样例：

无

输出样例（第二行的内容要你自己想一想，这里不给出）：

I’m gonna win! Today!
这一行的内容我不告诉你…… 你要自己输出正确的日期呀~

#include <iostream>
using namespace std;
int main() {
    cout << "I'm gonna win! Today!\n2022-04-23";
    return 0;
}

#include <iostream>

using namespace std;

int main() {

cout << "I'm gonna win! Today!\n2022-04-23";

return 0;

}

A Cartesian tree is a binary tree constructed from a sequence of distinct numbers. The tree is heap-ordered, and an inorder traversal returns the original sequence. For example, given the sequence { 8, 15, 3, 4, 1, 5, 12, 10, 18, 6 }, the min-heap Cartesian tree is shown by the figure.

Your job is to output the level-order traversal sequence of the min-heap Cartesian tree.

Input Specification:

Each input file contains one test case. Each case starts from giving a positive integer N (≤30), and then N distinct numbers in the next line, separated by a space. All the numbers are in the range of int.

Output Specification:

For each test case, print in a line the level-order traversal sequence of the min-heap Cartesian tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the beginning or the end of the line.

Sample Input:

10
8 15 3 4 1 5 12 10 18 6

Sample Output:

1 3 5 8 4 6 15 10 12 18

题目大意：笛卡尔树，是由一系列不同数字构成的二叉树。树是堆排序的，中序遍历返回原始序列。例如，给定序列{8, 15, 3, 4, 1, 5, 12, 10, 18, 6}，小顶堆笛卡尔树如图所示。你的工作是输出小顶堆笛卡尔树的层序遍历序列。输入格式：给一个正整数N，接下来一行给出N个不同的数字，用空格分隔。所有数字都在int范围内。输出格式：在一行中输出小顶堆笛卡尔树的层序遍历。一行中的所有数字必须用一个空格隔开，并且行首和行尾不得有多余的空格。
分析：中序遍历保存在In数组中，层序遍历结果保存在映射map<int, int> ans中。本题需要将小顶堆的中序遍历转化为层次遍历。我们知道，在小顶堆中，数值最小的那个元素为根结点，对于其任何子树也一样。所以我们只要在中序遍历中找到最小的那个数作为当前的根结点，左边的所有数都归左子树，右边所有数都归右子树。将根结点的序号设为1，左孩子的序号为它的两倍，右孩子的序号为它的两倍+1，最后根据序号顺序输出ans即为层序遍历的顺序。哇呜。

#include <iostream>
#include <map>
using namespace std;
int n, In[32];
map<int, int> ans;
void deal(int index, int L, int R) {
    if (L > R) return;
    int pos = L;
    for (int i = L + 1; i <= R; i++)
        if (In[i] < In[pos]) pos = i;
    ans[index] = In[pos];
    deal(index << 1, L, pos - 1);
    deal(index << 1 | 1, pos + 1, R);
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> In[i];
    deal(1, 0, n - 1);
    for (auto it : ans) {
        if (it.first != 1) cout << ' ';
        cout << it.second;
    }
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int n, In[32];

map<int, int> ans;

void deal(int index, int L, int R) {

if (L > R) return;

int pos = L;

for (int i = L + 1; i <= R; i++)

if (In[i] < In[pos]) pos = i;

ans[index] = In[pos];

deal(index << 1, L, pos - 1);

deal(index << 1 | 1, pos + 1, R);

}

int main() {

cin >> n;

for (int i = 0; i < n; i++) cin >> In[i];

deal(1, 0, n - 1);

for (auto it : ans) {

if (it.first != 1) cout << ' ';

cout << it.second;

}

return 0;

}

1166 Summit – PAT甲级真题

A summit (峰会) is a meeting of heads of state or government. Arranging the rest areas for the summit is not a simple job. The ideal arrangement of one area is to invite those heads so that everyone is a direct friend of everyone.

Now given a set of tentative arrangements, your job is to tell the organizers whether or not each area is all set.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N (≤ 200), the number of heads in the summit, and M, the number of friendship relations. Then M lines follow, each gives a pair of indices of the heads who are friends to each other. The heads are indexed from 1 to N.

Then there is another positive integer K (≤ 100), and K lines of tentative arrangement of rest areas follow, each first gives a positive number L (≤ N), then followed by a sequence of L distinct indices of the heads. All the numbers in a line are separated by a space.

Output Specification:

For each of the K areas, print in a line your advice in the following format:

if in this area everyone is a direct friend of everyone, and no friend is missing (that is, no one else is a direct friend of everyone in this area), print Area X is OK..
if in this area everyone is a direct friend of everyone, yet there are some other heads who may also be invited without breaking the ideal arrangement, print Area X may invite more people, such as H. where H is the smallest index of the head who may be invited.
if in this area the arrangement is not an ideal one, then print Area X needs help. so the host can provide some special service to help the heads get to know each other.

Here X is the index of an area, starting from 1 to K.

Sample Input:

8 10
5 6
7 8
6 4
3 6
4 5
2 3
8 2
2 7
5 3
3 4
6
4 5 4 3 6
3 2 8 7
2 2 3
1 1
2 4 6
3 3 2 1

Sample Output:

Area 1 is OK.
Area 2 is OK.
Area 3 is OK.
Area 4 is OK.
Area 5 may invite more people, such as 3.
Area 6 needs help.

题目大意：为峰会安排休息区，一个理想的安排是邀请这些领导人，每个人互相之间都是直接朋友。给定一套暂定的安排，判断每个区域是否都已准备就绪。输入格式：第一行给一个正整数N，表示峰会的首领数量，以及一个正整数M，表示友谊关系的数量。接下来是M行，每行给出一对互为朋友的领导人的编号。领导人的编号从1到N。然后给出另一个正整数K，接下来是K行暂定的休息区，每行给出一个正整数L，然后是一系列L个不同的领导人编号。一行中所有数字都用空格分隔。输出格式：对于K个休息区的每一个，请按以下格式将您的建议输出在一行中：如果在这个休息区每个人都互相是直接朋友，并且没有朋友漏掉（即没有其他人是这个休息区每个人的直接朋友），就输出Area X is OK.如果在这个休息区每个人都是每个人的直接朋友，但在不破坏理想安排的情况下，可能还会邀请一些其他领导人，就输出Area X may invite more people, such as H. H是可以被邀请的领导人的最小编号。如果该休息区的安排不理想，则输出Area X needs help. 这样主持人可以提供一些特别的服务帮助领导人们互相了解。
分析：二维数组A作为邻接矩阵存储两个人是否是好朋友，如果是u和v好朋友就将数组A[u][v] = A[v][u] = 1；集合temp存储待检查的序列号。先检查所有的人是不是互相都为好朋友，如果不是的话，直接输出needs help。然后，检查剩下的所有人中，是否有人是他们所有人的好朋友、但是没有被邀请的，如果没有，就输出is OK. 否则输出may invite more people, such as f. 其中f为可以被邀请的领导人的最小编号~

#include <iostream>
#include <set>
using namespace std;
int n, m, k, l, u, v, s, e, f, f2, A[201][201];
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        A[u][v] = A[v][u] = 1;
    }
    cin >> k;
    for (int i = 1; i <= k; i++) {
        f = 0;
        set<int> temp;
        cin >> l;
        for (int j = 0; j < l; j++) {
            cin >> e;
            for (auto it : temp) 
                if (!A[e][it]) f = 1;
            temp.insert(e);
        }
        cout << "Area " << i;
        if (f) {
            cout << " needs help.\n";
        } else {
            for (int i = 1; i <= n; i++) {
                f2 = 1;
                if (temp.count(i)) continue;
                for (auto it : temp) {
                    if (!A[i][it]) {
                        f2 = 0;
                        break;
                    }
                }
                if (f2) {
                    f = i;
                    break;
                }
            }
            if (!f) 
                cout << " is OK.\n";
            else 
                cout << " may invite more people, such as " << f << ".\n"; 
        }
    }
    return 0;
}

#include <iostream>

#include <set>

using namespace std;

int n, m, k, l, u, v, s, e, f, f2, A[201][201];

int main() {

cin >> n >> m;

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

cin >> u >> v;

A[u][v] = A[v][u] = 1;

}

cin >> k;

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

f = 0;

set<int> temp;

cin >> l;

for (int j = 0; j < l; j++) {

cin >> e;

for (auto it : temp)

if (!A[e][it]) f = 1;

temp.insert(e);

}

cout << "Area " << i;

if (f) {

cout << " needs help.\n";

} else {

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

f2 = 1;

if (temp.count(i)) continue;

for (auto it : temp) {

if (!A[i][it]) {

f2 = 0;

break;

}

if (f2) {

f = i;

break;

}

if (!f)

cout << " is OK.\n";

else

cout << " may invite more people, such as " << f << ".\n";

}

return 0;

}

1165 Block Reversing – PAT甲级真题

Given a singly linked list L. Let us consider every K nodes as a block (if there are less than K nodes at the end of the list, the rest of the nodes are still considered as a block). Your job is to reverse all the blocks in L. For example, given L as 1→2→3→4→5→6→7→8 and K as 3, your output must be 7→8→4→5→6→1→2→3.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤105) which is the total number of nodes, and a positive K (≤N) which is the size of a block. The address of a node is a 5-digit nonnegative integer, and NULL is represented by −1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is an integer, and Next is the position of the next node.

Output Specification:

For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

00100 8 3
71120 7 88666
00000 4 99999
00100 1 12309
68237 6 71120
33218 3 00000
99999 5 68237
88666 8 -1
12309 2 33218

Sample Output:

71120 7 88666
88666 8 00000
00000 4 99999
99999 5 68237
68237 6 00100
00100 1 12309
12309 2 33218
33218 3 -1

题目大意：给定一个单链表L，将每K个结点看成一个区块（链表最后若不足K个结点，也看成一个区块），请编写程序将L中所有区块的链表反转。例如：给定L为1→2→3→4→5→6→7→8，K为3，则输出应该为7→8→4→5→6→1→2→3。每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址、结点总个数正整数N(≤10的五次方)、以及正整数K(≤N)，即区块的大小。结点的地址是5位非负整数，NULL 地址用−1表示。接下来有N行，每行格式为：Address Data Next，其中Address是结点地址，Data是该结点保存的整数数据，Next是下一个结点的地址。对于每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。
分析：L为输入链表，ans为答案链表，二维数组E为区块链表。先将链表数据记录在结构体A中，遍历A将链表正确顺序记录在链表L中，然后需要重新定义链表长度n（因为有输入中有无效的假结点信息）。遍历链表L，将每K个结点所分隔成的区块保存在二维数组E中，再从后往前将区块链表E中的值添加到答案链表ans中，最后根据格式输出ans链表就好啦~

#include <iostream>
#include <vector>
using namespace std;
struct node {
    int data, next;
}A[100001];
vector<int> L, ans, E[100001];
int s, n , a, t, k, mark, cnt, c;
int main() {
    cin >> s >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a;
        cin >> A[a].data >> A[a].next;
    }
    t = s;
    while (t != -1) {
        L.push_back(t);
        t = A[t].next;
    }
    n = L.size();
    for (int i = 0; i < n; i++) {
        E[c].push_back(L[i]);
        cnt++;
        if (cnt == k && i != n - 1) {
            cnt = 0;
            c++;
        }
    }
    for (int i = c; i >= 0; i--)
        for (auto it : E[i]) 
            ans.push_back(it);
    for (int i = 1; i < n; i++) 
        printf("%05d %d %05d\n", ans[i - 1], A[ans[i - 1]].data, ans[i]);
    printf("%05d %d -1", ans.back(), A[ans.back()].data);
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

struct node {

int data, next;

}A[100001];

vector<int> L, ans, E[100001];

int s, n , a, t, k, mark, cnt, c;

int main() {

cin >> s >> n >> k;

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

cin >> a;

cin >> A[a].data >> A[a].next;

}

t = s;

while (t != -1) {

L.push_back(t);

t = A[t].next;

}

n = L.size();

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

E[c].push_back(L[i]);

cnt++;

if (cnt == k && i != n - 1) {

cnt = 0;

c++;

}

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

for (auto it : E[i])

ans.push_back(it);

for (int i = 1; i < n; i++)

printf("%05d %d %05d\n", ans[i - 1], A[ans[i - 1]].data, ans[i]);

printf("%05d %d -1", ans.back(), A[ans.back()].data);

return 0;

}

作者： liuchuo

L1-083 谁能进图书馆-PAT团体程序设计天梯赛GPLT

输入格式：

输出格式：

输入样例 1：

输出样例 1：

输入样例 2：

输出样例 2：

L1-082 种钻石-PAT团体程序设计天梯赛GPLT

输入格式：

输出格式：

输入样例：

输出样例：

L1-081 今天我要赢-PAT团体程序设计天梯赛GPLT

输入格式：

输出格式：

输入样例：

输出样例（第二行的内容要你自己想一想，这里不给出）：

1167 Cartesian Tree – PAT甲级真题

Input Specification:

Output Specification:

Sample Input:

Sample Output:

1166 Summit – PAT甲级真题

Input Specification:

Output Specification:

Sample Input:

Sample Output:

1165 Block Reversing – PAT甲级真题

Input Specification:

Output Specification:

Sample Input:

Sample Output: