liuchuo – 第3页 – 柳婼の blog

1172 Panda and PP Milk – PAT甲级真题

PP milk （盆盆奶）is Pandas’ favorite. They would line up to enjoy it as show in the picture. On the other hand, they could drink in peace only if they believe that the amount of PP milk is fairly distributed, that is, fatter panda can have more milk, and the ones with equal weight may have the same amount. Since they are lined up, each panda can only compare with its neighbor(s), and if it thinks this is unfair, the panda would fight with its neighbor.

Given that the minimum amount of milk a panda must drink is 200 ml. It is only when another bowl of milk is at least 100 ml more than its own that a panda can sense the difference.

Now given the weights of a line of pandas, your job is to help the breeder（饲养员）to decide the minimum total amount of milk that he/she must prepare, provided that the pandas are lined up in the given order.

Input Specification:

Each input file contains one test case. For each case, first a positive integer n (≤10^4) is given as the number of pandas. Then in the next line, n positive integers are given as the weights (in kg) of the pandas, each no more than 200. the numbers are separated by spaces.

Output Specification:

For each test case, print in a line the minimum total amount of milk that the breeder must prepare, to make sure that all the pandas can drink in peace.

Sample Input:

10
180 160 100 150 145 142 138 138 138 140

Sample Output:

3000

Hint:

The distribution of milk is the following:

400 300 200 500 400 300 200 200 200 300

题目大意：大熊猫，俗称“胖达”，会排队吃盆盆奶。它们能和谐吃奶的前提，是它们认为盆盆奶的分配是“公平”的，即：更胖的胖达能吃到更多的奶，等胖的胖达得吃到一样多的奶。另一方面，因为它们是排好队的，所以每只胖达只能看到身边胖达的奶有多少，如果觉得不公平就会抢旁边小伙伴的奶吃。已知一只胖达每次最少要吃 200 毫升的奶，当另一份盆盆奶多出至少 100 毫升的时候，它们才能感觉到是“更多”了，否则没感觉。现在给定一排胖达的体重，请你帮饲养员计算一下，在保持给定队形的前提下，至少应该准备多少毫升的盆盆奶。

分析：使用数组A记录每个熊猫的体重，L[i]表示第i个数的右边有几个连续下降的数（过程中可以有相等的数字，但是只记录不重复的数字的数量），R[i]则表示第i个数左边有几个连续下降的数（也是可以相等但是不记录）。从左到右遍历每一个i，然后看一下它右边有多少个连续下降的数。从右到左同理，看一下i的左边有多少个连续下降的数。对于每一只熊猫，取L[i]和R[i]中较大的那个数*100+200，就是这只熊猫应该喝的牛奶的毫升数。最后计算他们的总和就可以啦。

#include <iostream>
using namespace std;
int n, ans, A[10005], L[10005], R[10005];
int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> A[i];
    for (int i = 1; i < n; i++) {
        int j = i;
        while(j + 1 <= n && A[j] >= A[j + 1]) {
            if (A[j] > A[j + 1]) ++L[i];
            ++j;
        }
    }
    for (int i = n; i > 1; i--) {
        int j = i;
        while(j - 1 >= 1 && A[j] >= A[j - 1]) {
            if (A[j] > A[j - 1]) ++R[i];
            --j;
        }
    }
    for (int i = 1; i <= n; i++) ans += max(L[i], R[i]) * 100 + 200;
    cout << ans;
    return 0;
}

#include <iostream>

using namespace std;

int n, ans, A[10005], L[10005], R[10005];

int main(){

cin >> n;

for (int i = 1; i <= n; i++) cin >> A[i];

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

int j = i;

while(j + 1 <= n && A[j] >= A[j + 1]) {

if (A[j] > A[j + 1]) ++L[i];

++j;

}

for (int i = n; i > 1; i--) {

int j = i;

while(j - 1 >= 1 && A[j] >= A[j - 1]) {

if (A[j] > A[j - 1]) ++R[i];

--j;

}

for (int i = 1; i <= n; i++) ans += max(L[i], R[i]) * 100 + 200;

cout << ans;

return 0;

}

1171 Replacement Selection – PAT甲级真题

When the input is much too large to fit into memory, we have to do external sorting instead of internal sorting. One of the key steps in external sorting is to generate sets of sorted records (also called runs) with limited internal memory. The simplest method is to read as many records as possible into the memory, and sort them internally, then write the resulting run back to some tape. The size of each run is the same as the capacity of the internal memory.

Replacement Selection sorting algorithm was described in 1965 by Donald Knuth. Notice that as soon as the first record is written to an output tape, the memory it used becomes available for another record. Assume that we are sorting in ascending order, if the next record is not smaller than the record we have just output, then it can be included in the run.

For example, suppose that we have a set of input { 81, 94, 11, 96, 12, 99, 35 }, and our memory can sort 3 records only. By the simplest method we will obtain three runs: { 11, 81, 94 }, { 12, 96, 99 } and { 35 }. According to the replacement selection algorithm, we would read and sort the first 3 records { 81, 94, 11 } and output 11 as the smallest one. Then one space is available so 96 is read in and will join the first run since it is larger than 11. Now we have { 81, 94, 96 }. After 81 is out, 12 comes in but it must belong to the next run since it is smaller than 81. Hence we have { 94, 96, 12 } where 12 will stay since it belongs to the next run. When 94 is out and 99 is in, since 99 is larger than 94, it must belong to the first run. Eventually we will obtain two runs: the first one contains { 11, 81, 94, 96, 99 } and the second one contains { 12, 35 }.

Your job is to implement this replacement selection algorithm.

Input Specification:

Each input file contains several test cases. The first line gives two positive integers N (≤10^5) and M (<N/2), which are the total number of records to be sorted, and the capacity of the internal memory. Then N numbers are given in the next line, all in the range of int. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in each line a run (in ascending order) generated by the replacement selection algorithm. All the numbers in a line must be separated by exactly 1 space, and there must be no extra space at the beginning or the end of the line.

Sample Input:

13 3
81 94 11 96 12 99 17 35 28 58 41 75 15

Sample Output:

11 81 94 96 99
12 17 28 35 41 58 75
15

题目大意：当输入数据远远超过内存容量，我们不得不进行外部排序而不是内部排序。外部排序的关键步骤之一是生成一组有限内存的已排序记录（也称为运行集）。最简单的方法是将尽可能多的记录读入内存，对其进行内部排序，然后将生成的运行集写回到某个磁带。每个运行的大小与内部内存的容量相同。替代选择排序算法由Donald Knuth于1965年描述。请注意，一旦第一条记录写入输出磁带，它所使用的内存就会为另一条记录释放出来。假设我们按升序排序，如果下一条记录不比刚刚输出的记录小，那么它可以包含在运行集中。例如，假设我们有一个输入集合{81,94,11,96,12,99,35}，而我们的内存只能排序3条记录。按照最简单的方法，我们将获得三个运行集：{11,81,94}，{12,96,99}和{35}。根据替代选择算法，我们将读取和排序前3条记录{81,94,11} 并输出11作为最小值。然后会有一个空间可用，所以读入96，它会加入第一个运行集，因为它大于11。现在我们有{81,94,96}。81出去后，12进来，但它必须属于下一个运行集，因为它小于81。因此，我们有{94,96,12}，其中12将留在下一个运行集。当94出去，99进来，因为99大于94，它必须属于第一个运行集。最终我们将获得两个运行集：第一个包含{11,81,94,96,99}，第二个包含{12,35}。您的任务是实现这个替代选择排序算法。

分析：A存储输入的数据，创建两个小数先出来的优先队列Q1和Q2，分别表示这一轮正在排序的数列，和下一轮进行排序的数列。index表示当前正在处理的数据的下标，now表示从优先队列里取出来的当前处理的序列段里最小的数。先把M个以内的数据存到Q1里，每次从Q1里取出一个最小的数，并将它输出。看一下下一个要读入的数据（如果有的话）和现在这个最小的数之间的关系。大于等于now，存在Q1里小于现在的now，就把它存到Q2里。如果Q1中的数据全部处理完毕了，就把Q2中的内容交换到Q1里，这样Q1就是下一个要处理的序列段，Q2变成空，可以装新数据。

#include <iostream>
#include <queue>
using namespace std;
int N, M, A[100005], index, now;
priority_queue<int, vector<int>, greater<int>> Q1, Q2;
int main(){
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
        if (i <= M) Q1.push(A[i]);
    }
    index = M + 1;
    while (Q1.size()) {
        now = Q1.top();
        cout << now;
        Q1.pop();
        if(index <= N) {
            if (A[index] < now) Q2.push(A[index]);
            else Q1.push(A[index]);
            ++index;
        }
        if (Q1.size()) cout << ' ';
        else {
            swap(Q1, Q2);
            cout << '\n';
        }
    }
    return 0;
}

#include <iostream>

#include <queue>

using namespace std;

int N, M, A[100005], index, now;

priority_queue<int, vector<int>, greater<int>> Q1, Q2;

int main(){

cin >> N >> M;

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

cin >> A[i];

if (i <= M) Q1.push(A[i]);

}

index = M + 1;

while (Q1.size()) {

now = Q1.top();

cout << now;

Q1.pop();

if(index <= N) {

if (A[index] < now) Q2.push(A[index]);

else Q1.push(A[index]);

++index;

}

if (Q1.size()) cout << ' ';

else {

swap(Q1, Q2);

cout << '\n';

}

return 0;

}

1170 Safari Park – PAT甲级真题

A safari park（野生动物园）has K species of animals, and is divided into N regions. The managers hope to spread the animals to all the regions, but not the same animals in the two neighboring regions. Of course, they also realize that this is an NP complete problem, you are not expected to solve it. Instead, they have designed several distribution plans. Your job is to write a program to help them tell if a plan is feasible.

Input Specification:

Each input file contains one test case. For each case, the first line gives 3 integers: N (0<N≤500), the number of regions; R (≥0), the number of neighboring relations, and K (0<K≤N), the number of species of animals. The regions and the species are both indexed from 1 to N.

Then R lines follow, each gives the indices of a pair of neighboring regions, separated by a space.

Finally there is a positive M (≤20) followed by M lines of distribution plans. Each plan gives N indices of species in a line (the i-th index is the animal in the i-th rigion), separated by spaces. It is guaranteed that any pair of neighboring regions must be different, and there is no duplicated neighboring relations.

Output Specification:

For each plan, print in a line Yes if no animals in the two neighboring regions are the same, or No otherwise. However, if the number of species given in a plan is not K, you must print Error: Too many species. or Error: Too few species. according to the case.

Sample Input:

6 8 3
2 1
1 3
4 6
2 5
2 4
5 4
5 6
3 6
5
1 2 3 3 1 2
1 2 3 4 5 6
4 5 6 6 4 5
2 3 4 2 3 4
2 2 2 2 2 2

Sample Output:

Yes
Error: Too many species.
Yes
No
Error: Too few species.

题目大意：野生动物园有K种动物，分为N个区域。管理人员希望将动物传播到所有区域，但同一种动物不在两个相邻区域。当然，他们也意识到这是一个NP完全问题，不指望你去解决它。相反，他们设计了几个分配方案。你的工作是写一个程序，帮助他们判断一个计划是否可行。

分析：flag标记当前方案是否可行，邻接矩阵E存储连接的区域。使用map<int,vector<int>> A保存对应种类的动物生活在哪个区域。判断A的大小就可以知道有多少种类的动物，和K做比较就可以知道动物数量有没有太多或者太少。遍历所有同种动物，通过邻接矩阵看它们生存的区域之间有没有相邻的。

#include <iostream>
#include <map>
#include <vector>
using namespace std;
int N, R, K, M, flag, E[505][505];
int main() {
    cin >> N >> R >> K;
    for (int i = 1, u, v; i <= R; i++) {
        cin >> u >> v;
        E[u][v] = E[v][u] = 1;
    }
    for (cin >> M; M; M--) {
        map<int, vector<int>> A;
        for (int i = 1, a; i <= N; i++) {
            cin >> a;
            A[a].push_back(i);
        }
        if(A.size() > K) cout << "Error: Too many species.\n";
        else if (A.size() < K) cout << "Error: Too few species.\n";
        else {
            flag = 1;
            for (auto it : A) {
                for (int i = 0; i < it.second.size(); i++) {
                    for (int j = i + 1; j < it.second.size(); j++) {
                        if(E[it.second[i]][it.second[j]]) {
                            flag = 0;
                            break;
                        }
                    }
                }
            }
            if (flag) cout << "Yes\n";
            else cout << "No\n";
        }
        
    }
    return 0;
}

#include <iostream>

#include <map>

#include <vector>

using namespace std;

int N, R, K, M, flag, E[505][505];

int main() {

cin >> N >> R >> K;

for (int i = 1, u, v; i <= R; i++) {

cin >> u >> v;

E[u][v] = E[v][u] = 1;

}

for (cin >> M; M; M--) {

map<int, vector<int>> A;

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

cin >> a;

A[a].push_back(i);

}

if(A.size() > K) cout << "Error: Too many species.\n";

else if (A.size() < K) cout << "Error: Too few species.\n";

else {

flag = 1;

for (auto it : A) {

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

for (int j = i + 1; j < it.second.size(); j++) {

if(E[it.second[i]][it.second[j]]) {

flag = 0;

break;

}

if (flag) cout << "Yes\n";

else cout << "No\n";

}

return 0;

}

1169 The Judger – PAT甲级真题

A game of numbers has the following rules: at the beginning, two distinct positive integers are given by the judge. Then each player in turn must give a number to the judge. The number must be the difference of two numbers that are previously given, and must not be duplicated to any of the existed numbers. The game will run for several rounds. The one who gives a duplicate number or even a wrong number will be kicked out.

Your job is to write a judger program to judge the players’ numbers and to determine the final winners.

Input Specification:

Each input file contains one test case. For each case, the first line gives two distinct positive integers to begin with. Both numbers are in [1,105].

In the second line, two numbers are given: N (2≤N≤10), the number of players, and M (2≤M≤10^3), the number of rounds.

Then N lines follow, each contains M positive integers. The i-th line corresponds to the i-th player (i=1,⋯,N). The game is to start from the 1st player giving his/her 1st number, followed by everybody else giving their 1st numbers in the 1st round; then everyone give their 2nd numbers in the 2nd round, and so on so forth.

Output Specification:

If the i-th player is kicked out in the k-th round, print in a line Round #k: i is out.. The rest of the numbers given by the one who is out of the game will be ignored. If more than one player is out in the same round, print them in increasing order of their indices. When the game is over, print in the last line Winner(s): W1 W2 ... Wn, where W1 ... Wn are the indices of the winners in increasing order. 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. If there is no winner, print No winner. instead.

Sample Input 1:

101 42
4 5
59 34 67 9 7
17 9 8 50 7
25 92 43 26 37
76 51 1 41 40

Sample Output 1:

Round #4: 1 is out.
Round #5: 3 is out.
Winner(s): 2 4

Sample Input 2:

42 101
4 5
59 34 67 9 7
17 9 18 50 49
25 92 58 1 39
102 32 2 6 41

Sample Output 2:

Round #1: 4 is out.
Round #3: 2 is out.
Round #4: 1 is out.
Round #5: 3 is out.
No winner.

题目大意：有一种数字游戏的规则如下：首先由裁判给定两个不同的正整数，然后参加游戏的几个人轮流给出正整数。要求给出的数字必须是前面已经出现的某两个正整数之差，且不能等于之前的任何一个数。游戏一直持续若干轮，中间有写重复或写错的人就出局。本题要求你实现这个游戏的裁判机，自动判断每位游戏者给出的数字是否合法，以及最后的赢家。

分析：使用二维数组A存储每一轮每一个玩家出的数，使用flag2标记是否有人获胜，mark数组中标记某个数是否出现过，out[i]表示第i个人已经出局，used数组中存储已经出现过的数。题目要求是给出的数字必须是前面已经出现的某两个正整数之差，可以转换为现在这个人出的数字，加上已经出过的某个数，看是不是等于另一个已经出过的数字。对于每一轮我们遍历所有人，如果这个人已经出局，则跳过。如果这个数加所有出现过数字，不等于另外一个已经出现过的数字，或者这个数已经出现过了，那么这个人淘汰，否则mark记录一下这个数字已经被使用过，并且添加到已经使用过的数组used中。最后遍历输出赢家，如果没有赢家就输出”No winner.”。

#include <iostream>
#include <vector>
using namespace std;
int N, M, flag2, A[11][1001], mark[200005], out[11];
vector<int> used(2);
int main(){
    cin >> used[0] >> used[1];
    mark[used[0]] = mark[used[1]] = 1;
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    for (int j = 1; j <= M; j++) cin >> A[i][j];
    for (int i = 1; i <= M; i++) 
        for (int j = 1; j <= N; j++) {
            if (out[j]) continue;
            int flag = 0;
            if (mark[A[j][i]]) flag = -1;
            for (auto it : used) {
                if (mark[it + A[j][i]] == 1) {
                    mark[A[j][i]] = 1;
                    flag++;
                    used.push_back(A[j][i]);
                    break;
                }
            }
            if (flag <= 0) {
                out[j] = 1;
                cout << "Round #" << i << ": " << j << " is out.\n";
            }
        }
    for (int i = 1; i <= N; i++) {
        if (!out[i]) {
            if(!flag2) {
                cout << "Winner(s):";
                flag2 = 1;
            }
            cout << " " << i;
        }
    }
    if (!flag2) cout << "No winner.";
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int N, M, flag2, A[11][1001], mark[200005], out[11];

vector<int> used(2);

int main(){

cin >> used[0] >> used[1];

mark[used[0]] = mark[used[1]] = 1;

cin >> N >> M;

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

for (int j = 1; j <= M; j++) cin >> A[i][j];

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

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

if (out[j]) continue;

int flag = 0;

if (mark[A[j][i]]) flag = -1;

for (auto it : used) {

if (mark[it + A[j][i]] == 1) {

mark[A[j][i]] = 1;

flag++;

used.push_back(A[j][i]);

break;

}

if (flag <= 0) {

out[j] = 1;

cout << "Round #" << i << ": " << j << " is out.\n";

}

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

if (!out[i]) {

if(!flag2) {

cout << "Winner(s):";

flag2 = 1;

}

cout << " " << i;

}

if (!flag2) cout << "No winner.";

return 0;

}

1168 Prime Day – PAT甲级真题

The above picture is from Sina Weibo, showing May 23rd, 2019 as a very cool “Prime Day”. That is, not only that the corresponding number of the date 20190523 is a prime, but all its sub-strings ended at the last digit 3 are prime numbers.

Now your job is to tell if a given date is a Prime Day.

Input Specification:

Each input file contains one test case. For each case, a date between January 1st, 0001 and December 31st, 9999 is given, in the format yyyymmdd.

Output Specification:

For each given date, output in the decreasing order of the length of the substrings, each occupies a line. In each line, print the string first, followed by a space, then Yes if it is a prime number, or No if not. If this date is a Prime Day, print in the last line All Prime!.

Sample Input 1:

20190523

Sample Output 1:

20190523 Yes
0190523 Yes
190523 Yes
90523 Yes
0523 Yes
523 Yes
23 Yes
3 Yes
All Prime!

Sample Input 2:

20191231

Sample Output 2:

20191231 Yes
0191231 Yes
191231 Yes
91231 No
1231 Yes
231 No
31 Yes
1 No

题目大意：2019年5月23日是个“全素日”，即不仅20190523本身是个素数，它的任何以末尾数字3结尾的子串都是素数。本题就请你写个程序判断一个给定日期是否是“全素日”。输入按照yyyymmdd的格式给出一个日期。题目保证日期在0001年1月1日到9999年12月31日之间。从原始日期开始，按照子串长度递减的顺序，每行首先输出一个子串和一个空格，然后输出Yes，如果该子串对应的数字是一个素数，否则输出No。如果这个日期是一个全素日，则在最后一行输出All Prime!。

分析：使用num储存合数的个数，如果最后num为0，则表示要输出”All Prime!”。使用string s存储输入的数字。可以使用while循环，每次查询当前数值是不是素数，然后使用erase()函数删除第一个数字，如此循环到s长度为0。可以直接使用函数stoi()，将string转化成int类型。每次我们判断当前的数是不是素数，并直接输出。

#include <iostream>
#include <cmath>
using namespace std;
int num;
string s;
int is_prime(int x) {
    if (x < 2) return 0;
    for (int i = 2; i <= sqrt(x); i++)
        if (x % i == 0) return 0;
    return 1;
}
int main(){
    cin >> s;
    num = s.size();
    while (s.size()) {
        cout << s << ' ' << (is_prime(stoi(s)) ? "Yes" : "No") << '\n';
        if (is_prime(stoi(s))) --num;
        s.erase(s.begin());
    }
    if (num == 0) cout << "All Prime!";
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int num;

string s;

int is_prime(int x) {

if (x < 2) return 0;

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

if (x % i == 0) return 0;

return 1;

}

int main(){

cin >> s;

num = s.size();

while (s.size()) {

cout << s << ' ' << (is_prime(stoi(s)) ? "Yes" : "No") << '\n';

if (is_prime(stoi(s))) --num;

s.erase(s.begin());

}

if (num == 0) cout << "All Prime!";

return 0;

}

1120 买地攻略 – PAT乙级真题

数码城市有土地出售。待售的土地被划分成若干块，每一块标有一个价格。这里假设每块土地只有两块相邻的土地，除了开头和结尾的两块是只有一块邻居的。每位客户可以购买多块连续相邻的土地。

现给定这一系列土地的标价，请你编写程序，根据客户手头的现金量，告诉客户有多少种不同的购买方案。

输入格式：

输入首先在第一行给出两个正整数：N（≤10^4）为土地分割的块数（于是这些块从 1 到 N 顺次编号）；M（≤10^9）为客户手中的现金量。

随后一行给出 N 个正整数，其中第 i 个数字就是第 i 块土地的标价。

题目保证所有土地的总价不超过 10^9。

输出格式：

在一行中输出客户有多少种不同的购买方案。请注意客户只能购买连续相邻的土地。

输入样例：

5 85
38 42 15 24 9

输出样例：

样例解释：

这 11 种不同的方案为：

38
42
15
24
9
38 42
42 15
42 15 24
15 24
15 24 9
24 9

分析：使用pre数组保存土地价格前缀和，pre[i]表示从第一个土地到第i个土地的总价。在计算从第j个房子到第i个土地的总价的时候，只需要计算pre[i]-pre[j-1]即可。两个for循环，枚举所有i与j的值，然后计算出可以购买的方案数量即可。喵喵喵~

#include <iostream>
using namespace std;
int N, M, ans, a, pre[10005];
int main(){
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> a;
        pre[i] = pre[i - 1] + a;
    }
    for (int i = 1; i <= N; i++) {
        for (int j = i; j <= N; j++) {
            if (pre[j] - pre[i - 1] <= M) ++ans;
            else break;
        }
    }
    cout << ans;
    return 0;
}

#include <iostream>

using namespace std;

int N, M, ans, a, pre[10005];

int main(){

cin >> N >> M;

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

cin >> a;

pre[i] = pre[i - 1] + a;

}

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

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

if (pre[j] - pre[i - 1] <= M) ++ans;

else break;

}

cout << ans;

return 0;

}