OJ – 第7页 – 柳婼の blog

1115. Counting Nodes in a BST (30)-PAT甲级真题（二叉树的遍历，dfs）

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
Insert a sequence of numbers into an initially empty binary search tree. Then you are supposed to count the total number of nodes in the lowest 2 levels of the resulting tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=1000) which is the size of the input sequence. Then given in the next line are the N integers in [-1000 1000] which are supposed to be inserted into an initially empty binary search tree.

Output Specification:

For each case, print in one line the numbers of nodes in the lowest 2 levels of the resulting tree in the format:

n1 + n2 = n

where n1 is the number of nodes in the lowest level, n2 is that of the level above, and n is the sum.

Sample Input:
9
25 30 42 16 20 20 35 -5 28
Sample Output:
2 + 4 = 6

题目大意：输出一个二叉搜索树的最后两层结点个数a和b，以及他们的和c：“a + b = c”
分析：用链表存储，递归构建二叉搜索树，深度优先搜索，传入的参数为结点和当前结点的深度depth，如果当前结点为NULL就更新最大深度maxdepth的值并return，将每一层所对应的结点个数存储在数组num中，输出数组的最后两个的值～～

#include <iostream>
#include <vector>
using namespace std;
struct node {
    int v;
    struct node *left, *right;
};
node* build(node *root, int v) {
    if(root == NULL) {
        root = new node();
        root->v = v;
        root->left = root->right = NULL;
    } else if(v <= root->v)
        root->left = build(root->left, v);
    else
        root->right = build(root->right, v);
    return root;
}
vector<int> num(1000);
int maxdepth = -1;
void dfs(node *root, int depth) {
    if(root == NULL) {
        maxdepth = max(depth, maxdepth);
        return ;
    }
    num[depth]++;
    dfs(root->left, depth + 1);
    dfs(root->right, depth + 1);
    
}
int main() {
    int n, t;
    scanf("%d", &n);
    node *root = NULL;
    for(int i = 0; i < n; i++) {
        scanf("%d", &t);
        root = build(root, t);
    }
    dfs(root, 0);
    printf("%d + %d = %d", num[maxdepth-1], num[maxdepth-2], num[maxdepth-1] + num[maxdepth-2]);
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

struct node {

int v;

struct node *left, *right;

};

node* build(node *root, int v) {

if(root == NULL) {

root = new node();

root->v = v;

root->left = root->right = NULL;

} else if(v <= root->v)

root->left = build(root->left, v);

else

root->right = build(root->right, v);

return root;

}

vector<int> num(1000);

int maxdepth = -1;

void dfs(node *root, int depth) {

if(root == NULL) {

maxdepth = max(depth, maxdepth);

return ;

}

num[depth]++;

dfs(root->left, depth + 1);

dfs(root->right, depth + 1);

}

int main() {

int n, t;

scanf("%d", &n);

node *root = NULL;

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

scanf("%d", &t);

root = build(root, t);

}

dfs(root, 0);

printf("%d + %d = %d", num[maxdepth-1], num[maxdepth-2], num[maxdepth-1] + num[maxdepth-2]);

return 0;

}

1051. Pop Sequence (25)-PAT甲级真题（栈模拟）

Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, …, N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

Input Specification:

Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.

Output Specification:

For each pop sequence, print in one line “YES” if it is indeed a possible pop sequence of the stack, or “NO” if not.

Sample Input:
5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2
Sample Output:
YES
NO
NO
YES
NO
题目大意：有个容量限制为m的栈，分别把1，2，3，…，n入栈,给出一个系列出栈顺序，问这些出栈顺序是否可能～
分析：按照要求进行模拟。先把输入的序列接收进数组v。然后按顺序1~n把数字进栈，每进入一个数字，判断有没有超过最大范围，超过了就break。如果没超过，设current = 1，从数组的第一个数字开始，看看是否与栈顶元素相等，while相等就一直弹出栈，不相等就继续按顺序把数字压入栈～～最后根据变量flag的bool值输出yes或者no～

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main() {
    int m, n, k;
    scanf("%d %d %d", &m, &n, &k);
    for(int i = 0; i < k; i++) {
        bool flag = false;
        stack<int> s;
        vector<int> v(n + 1);
        for(int j = 1; j <= n; j++)
            scanf("%d", &v[j]);
        int current = 1;
        for(int j = 1; j <= n; j++) {
            s.push(j);
            if(s.size() > m) break;
            while(!s.empty() && s.top() == v[current]) {
                s.pop();
                current++;
            }
        }
        if(current == n + 1) flag = true;
        if(flag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

#include <iostream>

#include <stack>

#include <vector>

using namespace std;

int main() {

int m, n, k;

scanf("%d %d %d", &m, &n, &k);

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

bool flag = false;

stack<int> s;

vector<int> v(n + 1);

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

scanf("%d", &v[j]);

int current = 1;

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

s.push(j);

if(s.size() > m) break;

while(!s.empty() && s.top() == v[current]) {

s.pop();

current++;

}

if(current == n + 1) flag = true;

if(flag) printf("YES\n");

else printf("NO\n");

}

return 0;

}

1004. Counting Leaves (30)-PAT甲级真题(bfs,dfs,树的遍历，层序遍历)

A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.

Input

Each input file contains one test case. Each case starts with a line containing 0 < N < 100, the number of nodes in a tree, and M (< N), the number of non-leaf nodes. Then M lines follow, each in the format:

ID K ID[1] ID[2] … ID[K]
where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID’s of its children. For the sake of simplicity, let us fix the root ID to be 01.

Output

For each test case, you are supposed to count those family members who have no child for every seniority level starting from the root. The numbers must be printed in a line, separated by a space, and there must be no extra space at the end of each line.

The sample case represents a tree with only 2 nodes, where 01 is the root and 02 is its only child. Hence on the root 01 level, there is 0 leaf node; and on the next level, there is 1 leaf node. Then we should output “0 1” in a line.

Sample Input

2 1
01 1 02

Sample Output

0 1

题目大意：给出一棵树，问每一层各有多少个叶子结点～

分析：可以用dfs也可以用bfs～如果用dfs，用二维数组保存每一个有孩子结点的结点以及他们的孩子结点，从根结点开始遍历，直到遇到叶子结点，就将当前层数depth的book[depth]++；标记第depth层拥有的叶子结点数，最后输出～

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v[100];
int book[100], maxdepth = -1;
void dfs(int index, int depth) {
    if(v[index].size() == 0) {
        book[depth]++;
        maxdepth = max(maxdepth, depth);
        return ;
    }
    for(int i = 0; i < v[index].size(); i++)
        dfs(v[index][i], depth + 1);
}
int main() {
    int n, m, k, node, c;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++) {
        scanf("%d %d",&node, &k);
        for(int j = 0; j < k; j++) {
            scanf("%d", &c);
            v[node].push_back(c);
        }
    }
    dfs(1, 0);
    printf("%d", book[0]);
    for(int i = 1; i <= maxdepth; i++)
        printf(" %d", book[i]);
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

vector<int> v[100];

int book[100], maxdepth = -1;

void dfs(int index, int depth) {

if(v[index].size() == 0) {

book[depth]++;

maxdepth = max(maxdepth, depth);

return ;

}

for(int i = 0; i < v[index].size(); i++)

dfs(v[index][i], depth + 1);

}

int main() {

int n, m, k, node, c;

scanf("%d %d", &n, &m);

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

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

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

scanf("%d", &c);

v[node].push_back(c);

}

dfs(1, 0);

printf("%d", book[0]);

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

printf(" %d", book[i]);

return 0;

}

1106. Lowest Price in Supply Chain (25)-PAT甲级真题(dfs,bfs,树的遍历)

A supply chain is a network of retailers（零售商）, distributors（经销商）, and suppliers（供应商）– everyone involved in moving a product from supplier to customer.

Starting from one root supplier, everyone on the chain buys products from one’s supplier in a price P and sell or distribute them in a price that is r% higher than P. Only the retailers will face the customers. It is assumed that each member in the supply chain has exactly one supplier except the root supplier, and there is no supply cycle.

Now given a supply chain, you are supposed to tell the lowest price a customer can expect from some retailers.

Input Specification:

Each input file contains one test case. For each case, The first line contains three positive numbers: N (<=105), the total number of the members in the supply chain (and hence their ID’s are numbered from 0 to N-1, and the root supplier’s ID is 0); P, the price given by the root supplier; and r, the percentage rate of price increment for each distributor or retailer. Then N lines follow, each describes a distributor or retailer in the following format:

Ki ID[1] ID[2] … ID[Ki]

where in the i-th line, Ki is the total number of distributors or retailers who receive products from supplier i, and is then followed by the ID’s of these distributors or retailers. Kj being 0 means that the j-th member is a retailer. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the lowest price we can expect from some retailers, accurate up to 4 decimal places, and the number of retailers that sell at the lowest price. There must be one space between the two numbers. It is guaranteed that the all the prices will not exceed 1010.

Sample Input:
10 1.80 1.00
3 2 3 5
1 9
1 4
1 7
0
2 6 1
1 8
0
0
0
Sample Output:
1.8362 2

题目大意：提供一棵树，在树根处货物的价格为p，从根结点开始每往下一层，该层货物价格将会在父亲结点的价格上增加r%。求叶子结点出能获得的最低价格以及能提供最低价格的叶子结点数
分析：dfs。保存深度的最小值mindepth，以及最小值下该深度的个数minnum。深度优先搜索参数为index和depth，不断遍历index结点的孩子结点，直到当前结点没有孩子结点为止return～

#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
vector<int> v[100005];
int mindepth = 99999999, minnum = 1;
void dfs(int index, int depth) {
    if(mindepth < depth)
        return ;
    if(v[index].size() == 0) {
        if(mindepth == depth)
            minnum++;
        else if(mindepth > depth) {
            mindepth = depth;
            minnum = 1;
        }
    }
    for(int i = 0; i < v[index].size(); i++)
        dfs(v[index][i], depth + 1);
}
int main() {
    int n, k, c;
    double p, r;
    scanf("%d %lf %lf", &n, &p, &r);
    for(int i = 0; i < n; i++) {
        scanf("%d", &k);
        for(int j = 0; j < k; j++) {
            scanf("%d", &c);
            v[i].push_back(c);
        }
    }
    dfs(0, 0);
    printf("%.4f %d", p * pow(1 + r/100, mindepth), minnum);
    return 0;
}

#include <cstdio>

#include <vector>

#include <cmath>

using namespace std;

vector<int> v[100005];

int mindepth = 99999999, minnum = 1;

void dfs(int index, int depth) {

if(mindepth < depth)

return ;

if(v[index].size() == 0) {

if(mindepth == depth)

minnum++;

else if(mindepth > depth) {

mindepth = depth;

minnum = 1;

}

for(int i = 0; i < v[index].size(); i++)

dfs(v[index][i], depth + 1);

}

int main() {

int n, k, c;

double p, r;

scanf("%d %lf %lf", &n, &p, &r);

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

scanf("%d", &k);

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

scanf("%d", &c);

v[i].push_back(c);

}

dfs(0, 0);

printf("%.4f %d", p * pow(1 + r/100, mindepth), minnum);

return 0;

}

1094. The Largest Generation (25)-PAT甲级真题（bfs,dfs,树的遍历）

A family hierarchy is usually presented by a pedigree tree where all the nodes on the same level belong to the same generation. Your task is to find the generation with the largest population.

Input Specification:

Each input file contains one test case. Each case starts with two positive integers N (<100) which is the total number of family members in the tree (and hence assume that all the members are numbered from 01 to N), and M (<N) which is the number of family members who have children. Then M lines follow, each contains the information of a family member in the following format:

ID K ID[1] ID[2] … ID[K]

where ID is a two-digit number representing a family member, K (>0) is the number of his/her children, followed by a sequence of two-digit ID’s of his/her children. For the sake of simplicity, let us fix the root ID to be 01. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the largest population number and the level of the corresponding generation. It is assumed that such a generation is unique, and the root level is defined to be 1.

Sample Input:
23 13
21 1 23
01 4 03 02 04 05
03 3 06 07 08
06 2 12 13
13 1 21
08 2 15 16
02 2 09 10
11 2 19 20
17 1 22
05 1 11
07 1 14
09 1 17
10 1 18
Sample Output:
9 4
题目大意：输入树的结点个数N，结点编号为1~N，非叶子结点个数M，然后输出M个非叶子结点格子的孩子结点的编号，求结点个数最多的一层，根结点的层号为1，输出该层的结点个数以及层号<(▰˘◡˘▰)>
分析：用DFS或者BFS，用DFS就用参数index和level标记当前遍历的结点的编号和层数，一个数组book标记当前层数level所含结点数，最后遍历一遍数组找出最大值。注意：book[level]++;这句话是发生在return语句判断之前的外面，即每遇到一个结点都要进行处理，而不是放在return语句的条件判断里面～～
如果是BFS，就用一个数组level[i]标记i结点所处的层数，它等于它的父亲结点的level的值+1，用一个数组book，book[i]标记i层所拥有的结点数，在遍历的时候每弹出一个结点就将当前结点的层数所对应的book值+1，最后遍历一遍book数组找出最大拥有的结点数和层数～

深度优先dfs方法：

#include <cstdio>
#include <vector>
using namespace std;
vector<int> v[100];
int book[100];
void dfs(int index, int level) {
    book[level]++;
    for(int i = 0; i < v[index].size(); i++)
        dfs(v[index][i], level+1);
}
int main() {
    int n, m, a, k, c;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++) {
        scanf("%d %d",&a, &k);
        for(int j = 0; j < k; j++) {
            scanf("%d", &c);
            v[a].push_back(c);
        }
    }
    dfs(1, 1);
    int maxnum = 0, maxlevel = 1;
    for(int i = 1; i < 100; i++) {
        if(book[i] > maxnum) {
            maxnum = book[i];
            maxlevel = i;
        }
    }
    printf("%d %d", maxnum, maxlevel);
    return 0;
}

#include <cstdio>

#include <vector>

using namespace std;

vector<int> v[100];

int book[100];

void dfs(int index, int level) {

book[level]++;

for(int i = 0; i < v[index].size(); i++)

dfs(v[index][i], level+1);

}

int main() {

int n, m, a, k, c;

scanf("%d %d", &n, &m);

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

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

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

scanf("%d", &c);

v[a].push_back(c);

}

dfs(1, 1);

int maxnum = 0, maxlevel = 1;

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

if(book[i] > maxnum) {

maxnum = book[i];

maxlevel = i;

}

printf("%d %d", maxnum, maxlevel);

return 0;

}

广度优先bfs方法：

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
vector<int> v[100];
int level[100];
int book[100];
int main() {
    int n, m, a, k, c;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++) {
        scanf("%d %d",&a, &k);
        for(int j = 0; j < k; j++) {
            scanf("%d", &c);
            v[a].push_back(c);
        }
    }
    queue<int> q;
    q.push(1);
    level[1] = 1;
    while(!q.empty()) {
        int index = q.front();
        q.pop();
        book[level[index]]++;
        for(int i = 0; i < v[index].size(); i++) {
            level[v[index][i]] = level[index] + 1;
            q.push(v[index][i]);
        }
        
    }
    int maxnum = 0, maxlevel = 1;
    for(int i = 1; i < 100; i++) {
        if(book[i] > maxnum) {
            maxnum = book[i];
            maxlevel = i;
        }
    }
    printf("%d %d", maxnum, maxlevel);
    return 0;
}

#include <cstdio>

#include <vector>

#include <queue>

using namespace std;

vector<int> v[100];

int level[100];

int book[100];

int main() {

int n, m, a, k, c;

scanf("%d %d", &n, &m);

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

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

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

scanf("%d", &c);

v[a].push_back(c);

}

queue<int> q;

q.push(1);

level[1] = 1;

while(!q.empty()) {

int index = q.front();

q.pop();

book[level[index]]++;

for(int i = 0; i < v[index].size(); i++) {

level[v[index][i]] = level[index] + 1;

q.push(v[index][i]);

}

int maxnum = 0, maxlevel = 1;

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

if(book[i] > maxnum) {

maxnum = book[i];

maxlevel = i;

}

printf("%d %d", maxnum, maxlevel);

return 0;

}

1079. Total Sales of Supply Chain (25)-PAT甲级真题（dfs,bfs,树的遍历）

A supply chain is a network of retailers（零售商）, distributors（经销商）, and suppliers（供应商）– everyone involved in moving a product from supplier to customer.

Now given a supply chain, you are supposed to tell the total sales from all the retailers.

Input Specification:

Each input file contains one test case. For each case, the first line contains three positive numbers: N (<=105), the total number of the members in the supply chain (and hence their ID’s are numbered from 0 to N-1, and the root supplier’s ID is 0); P, the unit price given by the root supplier; and r, the percentage rate of price increment for each distributor or retailer. Then N lines follow, each describes a distributor or retailer in the following format:

Ki ID[1] ID[2] … ID[Ki]

where in the i-th line, Ki is the total number of distributors or retailers who receive products from supplier i, and is then followed by the ID’s of these distributors or retailers. Kj being 0 means that the j-th member is a retailer, then instead the total amount of the product will be given after Kj. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the total sales we can expect from all the retailers, accurate up to 1 decimal place. It is guaranteed that the number will not exceed 1010.

Sample Input:
10 1.80 1.00
3 2 3 5
1 9
1 4
1 7
0 7
2 6 1
1 8
0 9
0 4
0 3
Sample Output:
42.4

题目大意：给一棵树，在树根出货物的价格为p，然后从根结点开始每往下走一层，该层的货物价格将会在父亲结点的价格上增加r%，给出每个叶结点的货物量，求他们的价格之和
分析：树的遍历，可以采用dfs或者bfs两种方法。
采用dfs，建立结构体数组保存每一个结点的孩子结点的下标，如果没有孩子结点，就保存这个叶子结点的data（销售的量）。深度优先遍历的递归出口，即当前下标的结点没有孩子结点的时候，就把ans += data（货物量）* pow(1 + r, depth)计算货物量*价格引起的涨幅百分比。如果有孩子结点，就dfs深度优先遍历每一个孩子结点，并且在当前depth层数的基础上+1。最后输出ans * p（销售价格），即总价格

#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
struct node {
    double data;
    vector<int> child;
};
vector<node> v;
double ans = 0.0, p, r;

void dfs(int index, int depth) {
    if(v[index].child.size() == 0) {
        ans += v[index].data * pow(1 + r, depth);
        return ;
    }
    for(int i = 0; i < v[index].child.size(); i++)
        dfs(v[index].child[i], depth + 1);
}
int main() {
    int n, k, c;
    scanf("%d %lf %lf", &n, &p, &r);
    r = r / 100;
    v.resize(n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &k);
        if(k == 0) {
            scanf("%lf", &v[i].data);
        } else {
            for(int j = 0; j < k; j++) {
                scanf("%d", &c);
                v[i].child.push_back(c);
            }
        }
    }
    dfs(0, 0);
    printf("%.1f", ans * p);
    return 0;
}

#include <cstdio>

#include <vector>

#include <cmath>

using namespace std;

struct node {

double data;

vector<int> child;

};

vector<node> v;

double ans = 0.0, p, r;

void dfs(int index, int depth) {

if(v[index].child.size() == 0) {

ans += v[index].data * pow(1 + r, depth);

return ;

}

for(int i = 0; i < v[index].child.size(); i++)

dfs(v[index].child[i], depth + 1);

}

int main() {

int n, k, c;

scanf("%d %lf %lf", &n, &p, &r);

r = r / 100;

v.resize(n);

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

scanf("%d", &k);

if(k == 0) {

scanf("%lf", &v[i].data);

} else {

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

scanf("%d", &c);

v[i].child.push_back(c);

}

dfs(0, 0);

printf("%.1f", ans * p);

return 0;

}