Code – 柳婼の blog

1175 Professional Ability Test – PAT甲级真题

Professional Ability Test (PAT) consists of several series of subject tests. Each test is divided into several levels. Level A is a prerequisite (前置要求) of Level B if one must pass Level A with a score no less than S in order to be qualified to take Level B. At the mean time, one who passes Level A with a score no less than S will receive a voucher（代金券）of D yuans (Chinese dollar) for taking Level B.

At the moment, this PAT is only in design and hence people would make up different plans. A plan is NOT consistent if there exists some test T so that T is a prerequisite of itself. Your job is to test each plan and tell if it is a consistent one, and at the mean time, find the easiest way (with minimum total S) to obtain the certificate of any subject test. If the easiest way is not unique, find the one that one can win the maximum total value of vouchers.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N (≤1000) and M, being the total numbers of tests and prerequisite relations, respectively. Then M lines follow, each describes a prerequisite relation in the following format:

T1 T2 S D

where T1 and T2 are the indices (from 0 to N−1) of the two distinct tests; S is the minimum score (in the range (0, 100]) required to pass T1 in order to be qualified to take T2; and D is the value of the voucher (in the range (0, 500]) one can receive if one passes T1 with a score no less than S and plan to take T2. It is guaranteed that at most one pair of S and D are defined for a prerequisite relation.

Then another positive integer K (≤N) is given, followed by K queries of tests. All the numbers in a line are separated by spaces.

Output Specification:

Print in the first line Okay. if the whole plan is consistent, or Impossible. if not.

If the plan is consistent, for each query of test T, print in a line the easiest way to obtain the certificate of this test, in the format:

T0->T1->…->T

However, if T is the first level of some subject test (with no prerequisite), print You may take test T directly. instead.

If the plan is impossible, for each query of test T, check if one can take it directly or not. If the answer is yes, print in a line You may take test T directly.; or print Error. instead.

Sample Input 1:

8 15
0 1 50 50
1 2 20 20
3 4 90 90
3 7 90 80
4 5 20 20
7 5 10 10
5 6 10 10
0 4 80 60
3 1 50 45
1 4 30 20
1 5 50 20
2 4 10 10
7 2 10 30
2 5 30 20
2 6 40 60
8
0 1 2 3 4 5 6 7

Sample Output 1:

Okay.
You may take test 0 directly.
0->1
0->1->2
You may take test 3 directly.
0->1->2->4
0->1->2->4->5
0->1->2->6
3->7

Sample Input 2:

4 5
0 1 1 10
1 2 2 10
3 0 4 10
3 2 5 10
2 0 3 10
2
3 1

Sample Output 2:

Impossible.
You may take test 3 directly.
Error.

题目大意：PAT由一系列学科测试组成。每个测试被划分为几个级别。如果要资格参加 Level B，那么必须以不低于 S 的分数通过 Level A，Level A 就成为 Level B 的前置要求。同时，以不低于 S 的分数通过 Level A 的人将获得一张代金券，用于参加 Level B。目前，这个PAT仅处于设计阶段，因此人们可以制定不同的计划。如果存在某个测试 T，使得 T 是其自身的前提条件，那么该计划就不一致。您的任务是测试每个计划，并判断它是否一致，并同时找出获得任何学科测试证书的最简单方法（具有最小总分S）。如果最简单的方法不唯一，找出一个可以获得最大代金券总额的方法。

分析：node结构用来存储最短路中的结点信息，其中重载了小于号(<)的运算规则，让优先队列能以题目要求的顺序排列。bian是用来存储边信息的结构体。E是存储边信息的邻接表，Dis中存储最短路的距离，存的是从源点到第i个点所要考的最少分数和可以获得的最多的代金券。f用来标记是否有环，为1时表示有环，对应题目中说明的，某个课程是自己的前置课程。in和in2都用来存储每个结点的入度，Last数组存储最短路中每个结点的前一个结点是什么。
首先，我们可以用构造拓扑排序的方法判断一下图中是否存在环。可以使用bfs，将当前入度为0的结点存在队列里，取出后将其所有能到达的结点的入度减1，最后看一下能让入度为0的结点有多少，每次把他们存在S中，最后看S的大小和N之间的关系，如果全部都能拿到，则说明无环。
先建立一个初始点，这里用1002当初始点，然后把入度为0的结点和这个初始点连接上。这样只要使用1002当作起点，然后用Dijkstra计算最短的路径，和对应的每个结点上一步的结点是什么。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct node {
    int v, score, voucher;
    bool operator < (const node &x) const {
        if(score != x.score) return score > x.score;
        else return voucher < x.voucher;
    }
};
struct bian {
    int next, S, D;
};
vector<bian> E[1005];
vector<pair<int,int>> Dis(1005, {2e9, -1});
int N, M, T1, T2, S, D, f, T, in[1005], in2[1005], Last[1005];
queue<int> DAG;
int huan() {
    vector<int> S;
    while(DAG.size()) {
        int now = DAG.front();
        DAG.pop();
        S.push_back(now);
        for(auto it : E[now]) {
            in2[it.next]--;
            if(!in2[it.next]) DAG.push(it.next);
        }
    }
    return S.size() == N;
}
void dijkstra() {
    vector<int> vis(1005);
    priority_queue<node> Q;
    Q.push({1002, 0, 0});
    Dis[1002].first = Dis[1002].second = 0;
    while(Q.size()) {
        node now = Q.top();
        Q.pop();
        if(vis[now.v]) continue;
        vis[now.v] = 1;
        Dis[now.v].first = now.score;
        Dis[now.v].second = now.voucher;
        for (auto it : E[now.v]) {
            if(vis[it.next]) continue;
            if((Dis[it.next].first > Dis[now.v].first + it.S) || ((Dis[it.next].first == Dis[now.v].first + it.S) && (Dis[it.next].second < Dis[now.v].second + it.D))) {
                Dis[it.next].first = Dis[now.v].first + it.S;
                Dis[it.next].second = Dis[now.v].second + it.D;
                Last[it.next] = now.v;
                Q.push({it.next, Dis[it.next].first, Dis[it.next].second});
            }
        }
    }
    return;
}

int main() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> T1 >> T2 >> S >> D;
        E[T1].push_back({T2, S, D});
        in[T2]++, in2[T2]++;
    }
    for (int i = 0; i < N; i++) {
        if (in[i] == 0) {
            E[1002].push_back({i, 0, 0});
            DAG.push(i);
        }
    }
    f = huan();
    dijkstra();
    cin >> T;
    if(f) cout << "Okay.\n";
    else cout << "Impossible.\n";
    for (int i = 1, q; i <= T; i++) {
        cin >> q;
        if(!in[q]) cout << "You may take test " << q << " directly.\n";
        else if(!f) cout << "Error.\n";
        else {
            vector<int> path;
            int now = q;
            while(q != 1002) {
                path.push_back(q);
                q = Last[q];
            }
            for (int j = path.size() - 1; j >= 0; j--) {
                cout << path[j];
                if(j) cout << "->";
            }
            cout << '\n';
        }
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

struct node {

int v, score, voucher;

bool operator < (const node &x) const {

if(score != x.score) return score > x.score;

else return voucher < x.voucher;

}

};

struct bian {

int next, S, D;

};

vector<bian> E[1005];

vector<pair<int,int>> Dis(1005, {2e9, -1});

int N, M, T1, T2, S, D, f, T, in[1005], in2[1005], Last[1005];

queue<int> DAG;

int huan() {

vector<int> S;

while(DAG.size()) {

int now = DAG.front();

DAG.pop();

S.push_back(now);

for(auto it : E[now]) {

in2[it.next]--;

if(!in2[it.next]) DAG.push(it.next);

}

return S.size() == N;

}

void dijkstra() {

vector<int> vis(1005);

priority_queue<node> Q;

Q.push({1002, 0, 0});

Dis[1002].first = Dis[1002].second = 0;

while(Q.size()) {

node now = Q.top();

Q.pop();

if(vis[now.v]) continue;

vis[now.v] = 1;

Dis[now.v].first = now.score;

Dis[now.v].second = now.voucher;

for (auto it : E[now.v]) {

if(vis[it.next]) continue;

if((Dis[it.next].first > Dis[now.v].first + it.S) || ((Dis[it.next].first == Dis[now.v].first + it.S) && (Dis[it.next].second < Dis[now.v].second + it.D))) {

Dis[it.next].first = Dis[now.v].first + it.S;

Dis[it.next].second = Dis[now.v].second + it.D;

Last[it.next] = now.v;

Q.push({it.next, Dis[it.next].first, Dis[it.next].second});

}

return;

}

int main() {

cin >> N >> M;

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

cin >> T1 >> T2 >> S >> D;

E[T1].push_back({T2, S, D});

in[T2]++, in2[T2]++;

}

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

if (in[i] == 0) {

E[1002].push_back({i, 0, 0});

DAG.push(i);

}

f = huan();

dijkstra();

cin >> T;

if(f) cout << "Okay.\n";

else cout << "Impossible.\n";

for (int i = 1, q; i <= T; i++) {

cin >> q;

if(!in[q]) cout << "You may take test " << q << " directly.\n";

else if(!f) cout << "Error.\n";

else {

vector<int> path;

int now = q;

while(q != 1002) {

path.push_back(q);

q = Last[q];

}

for (int j = path.size() - 1; j >= 0; j--) {

cout << path[j];

if(j) cout << "->";

}

cout << '\n';

}

return 0;

}

1174 Left-View of Binary Tree – PAT甲级真题

The left-view of a binary tree is a list of nodes obtained by looking at the tree from left hand side and from top down. For example, given a tree shown by the figure, its left-view is { 1, 2, 3, 4, 5 }

Given the inorder and preorder traversal sequences of a binary tree, you are supposed to output its left-view.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤20), which is the total number of nodes in the tree. Then given in the following 2 lines are the inorder and preorder traversal sequences of the tree, respectively. All the keys in the tree are distinct positive integers in the range of int.

Output Specification:

For each case, print in a line the left-view of the tree. All the numbers in a line are separated by exactly 1 space, and there must be no extra space at the beginning or the end of the line.

Sample Input:

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

Sample Output:

1 2 3 4 5

题目大意：二叉树的左视图是通过从左侧向右上方查看树而获得的结点列表。例如，给定如图所示的树，其左视图为{1,2,3,4,5}。给定二叉树的中序遍历和前序遍历序列，输出其左视图。

分析：pre与in数组分别存储前序和中序遍历的结果，t存储某一层最左边的结点值，ins、ine分别表示当前操作在中序遍历数组中的起始位置与终止位置，prerootindex表示当前的子树根结点在前缀序列中的位置，level表示现在处于第几层，pos表示当前子树根结点在中序遍历数组中的位置。用前序和中序遍历的序列可以唯一确定一棵树。由于是从左到右的顺序遍历树的，所以每次判断当前层的t数组中没有元素（值为0）的时候，就表示这一层最左边的结点是现在这一个。

#include <iostream>
using namespace std;
int N, pre[30], in[30], t[30];
void deal(int ins, int ine, int prerootindex, int level) {
    if (ins > ine) return;
    if (t[level] == 0) {
        t[level] = pre[prerootindex];
    }
    int pos = ins;
    while(in[pos] != pre[prerootindex]) ++pos;
    deal(ins, pos - 1, prerootindex + 1, level + 1);
    deal(pos + 1, ine, prerootindex + 1 + pos - ins, level + 1);
}
int main(){
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> in[i];
    for (int i = 1; i <= N; i++) cin >> pre[i];
    deal(1, N, 1, 1);
    for (int i = 1; t[i]; i++) {
        if (i != 1) cout << ' ';
        cout << t[i];
    }
    return 0;
}

#include <iostream>

using namespace std;

int N, pre[30], in[30], t[30];

void deal(int ins, int ine, int prerootindex, int level) {

if (ins > ine) return;

if (t[level] == 0) {

t[level] = pre[prerootindex];

}

int pos = ins;

while(in[pos] != pre[prerootindex]) ++pos;

deal(ins, pos - 1, prerootindex + 1, level + 1);

deal(pos + 1, ine, prerootindex + 1 + pos - ins, level + 1);

}

int main(){

cin >> N;

for (int i = 1; i <= N; i++) cin >> in[i];

for (int i = 1; i <= N; i++) cin >> pre[i];

deal(1, N, 1, 1);

for (int i = 1; t[i]; i++) {

if (i != 1) cout << ' ';

cout << t[i];

}

return 0;

}

1173 How Many Ways to Buy a Piece of Land – PAT甲级真题

The land is for sale in CyberCity, and is divided into several pieces. Here it is assumed that each piece of land has exactly two neighboring pieces, except the first and the last that have only one. One can buy several contiguous（连续的） pieces at a time. Now given the list of prices of the land pieces, your job is to tell a customer in how many different ways that he/she can buy with a certain amount of money.

Input Specification:

Each input file contains one test case. Each case first gives in a line two positive integers: N (≤10^4), the number of pieces of the land (hence the land pieces are numbered from 1 to N in order), and M (≤10^9), the amount of money that your customer has.

Then in the next line, N positive integers are given, where the i-th one is the price of the i-th piece of the land.

It is guaranteed that the total price of the land is no more than 10^9.

Output Specification:

For each test case, print the number of different ways that your customer can buy. Notice that the pieces must be contiguous.

Sample Input:

5 85
38 42 15 24 9

Sample Output:

Hint:

The 11 different ways are:

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;

}

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;

}