liuchuo – 第202页 – 我不管，反正我最萌～

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;

}

【Objective-C】类与结构体的区别

只能在类里面写方法，不能在结构体里面写方法
类——对象，结构体——值
类——引用类型
- 位于栈上的指针（引用）
- 位于堆上的实体对象
结构体——值类型
- 实例直接位于栈中
拷贝行为：
- classname *a = b; a和b都是指针（指针存储在栈上），都指向同一个对象（对象存储在堆中），对象的值改变，a和b同时改变
- structname a = b; 进行的是值拷贝（复制值后存储在栈上），如果改变b的值，a的值不会跟着改变
传参行为：
- 传参的本质上就是拷贝，因为对象传入的是指针，所以值改变的函数调用完毕之后，对象的值会改变，而结构体的值不会改变（因为结构体是值传递）
- 在main函数调用子函数的时候，系统会为子函数建立一个栈，对象传参后存放的是引用（指针），结构体传参后存储的是结构体的值的拷贝

【Objective-C】栈(stack)和堆(heap)的区别

栈(stack)和堆(heap)的区别：

栈：存储值类型（有时候翻译成“堆栈”）
- 无ARC（自动引用计数）负担，由系统自动管理，以执行函数为单位（一个函数一个栈）
- 空间大小编译时决定（根据参数和局部变量可以确定）
- 函数执行时，系统自动分配一个栈
- 函数执行结束，系统会立即回收stack
- 函数之间通过拷贝值传递
- 具有局限性，大小有限额，超出会stack overflow（栈溢出）（一般是超大递归、死循环情况）
堆：存储引用类型对象
- 分配由程序员手动请求（[a alloc]）(c语言里面的malloc)
- 释放有两种方式，可以手工，也可以ARC机制自动释放
- 函数之间通过拷贝引用（指针）传递
- 具有全局性，总体大小无限制（受限于系统内存整体大小）

【Objective-C】java中的interface与Objective-C中的interface的区别

java中的interface
- interface叫做接口，是一种特殊的抽象类
- 一个接口中，所有方法为公开、抽象方法；所有的属性都是公开、静态、常量。
- 一个类只能继承一个类，但是能实现多个接口，这样可以实现变相的多继承
- 接口和接口之间也可以是继承关系，而且允许接口之间实现多继承
- 类必须实现接口中的方法，否则它是一个抽象类
Objective-C中的@interface
- Objective-C里面的@interface与java里面的interface不一样，就是写在头文件里面的，作为类的一个外界可以调用的函数的声明
@interface RPoint : NSObject @property int x; @property int y; -(void)print; @end

1
2
3
4
5
6
7

@interface RPoint : NSObject
@property int x;
@property int y;

-(void)print;

@end
- 最好将Objective-C中的interface理解为“类的声明部分”，protocol理解为“正式协议”，protocol相当于java中的interface
- interface和implementation共同代表一个类，两者的组合相当于java中的class