【PTA】PAT (Advanced Level) Practice 1004-1006

• 1004 Counting Leaves
• • 代码
• 1005 Spell It Right
• • 代码
• 1006 Sign In and Sign Out
• • 代码

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

Input Specification:
Each input file contains one test case. Each case starts with a line containing 0

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.

The input ends with N being 0. That case must NOT be processed.

Output Specification:
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

翻译：
有一个家谱，呈树状结构，现在要数出每一层有多少个叶子结点。

输入样例：
第一行：树中的节点数0 后续M行：父节点 子节点个数 子节点[1] 子节点[2]…

一开始按照惯性思维想要构造二叉树，但是仔细读题发现一个父结点可以有多个子结点，所以转换思路。

构造结构体对应每一个结点，含有父结点、是否有孩子、当前结点在第几层的信息。

#include
using namespace std;
struct Node{
    int level;//当前节点在第几层
    int flag;//是否有孩子
    int father;//父节点
};
    int sum[105];
int main()
{
    struct Node nodes[105];
    int n,m;
    cin>>n>>m;
    int maxlevel=1;
    int nowNode, nowNodeNumber, childNode;
    int i,j;
    //初始化
    for(i=0;i<=n;i++){
        nodes[i].level=0;
        nodes[i].flag=0;
        nodes[i].father=0;
    }
    //这一句话很重要
    nodes[1].level=1;
    //输入
    while(m--){
        cin>>nowNode;
        cin>>nowNodeNumber;
        
        if(nowNodeNumber!=0)
            nodes[nowNode].flag=1;
        
        while(nowNodeNumber--){
            cin>>childNode;
            nodes[childNode].father=nowNode;
        }
    }
    //将每个节点在第几层给算出来
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            //如果有一个点的父亲标识是自己，那么它就是你的儿子，那么他的等级，应该是你的等级+1
            if(nodes[j].father==i){
                nodes[j].level=nodes[i].level+1;
            }
        }
    }
    //查询每一层有多少个叶子节点，记录在sum数组里面
    for(i=1;i<=n;i++){
        if(nodes[i].flag!=1 && nodes[i].level>0){
            sum[nodes[i].level]++;
        }
        //记录最大的等级，用于最后的输出
        if(nodes[i].level>maxlevel){
            maxlevel=nodes[i].level;
        }
    }
    for(i=1;i
        cout< 
1005 Spell It Right 
Given a non-negative integer N, your task is to compute the sum of all the digits of N, and output every digit of the sum in English.
 
Input Specification:
 Each input file contains one test case. Each case occupies one line which contains an N (≤10^100 ).
 
Output Specification:
 For each test case, output in one line the digits of the sum in English words. There must be one space between two consecutive words, but no extra space at the end of a line.
 
Sample Input:
 
 
 
12345
 
 
Sample Output:
 
 
 
one five
 
 
翻译：
 将输入的一串数字一个个加起来，输出加和数字对应的英文。
 
代码 
字符串a转成数字的方法：
 
 
 
a-‘0’
 
 
#include
using namespace std;
int main(){
    string a;
    cin>>a;
    int sum=0;
    for(int i=0;i
        sum+=(a[i]-'0');
    }
    string s=to_string(sum);
    string arr[10]={"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
    cout< 
1006 Sign In and Sign Out 
At the beginning of every day, the first person who signs in the computer room will unlock the door, and the last one who signs out will lock the door. Given the records of signing in’s and out’s, you are supposed to find the ones who have unlocked and locked the door on that day.
 
Input Specification:
 Each input file contains one test case. Each case contains the records for one day. The case starts with a positive integer M, which is the total number of records, followed by M lines, each in the format:
 
 
 
ID_number Sign_in_time Sign_out_time
 
 
where times are given in the format HH:MM:SS, and ID_number is a string with no more than 15 characters.
 
Output Specification:
 For each test case, output in one line the ID numbers of the persons who have unlocked and locked the door on that day. The two ID numbers must be separated by one space.
 
Note: It is guaranteed that the records are consistent. That is, the sign in time must be earlier than the sign out time for each person, and there are no two persons sign in or out at the same moment.
 
Sample Input:
 3
 CS301111 15:30:28 17:00:10
 SC3021234 08:00:00 11:25:25
 CS301133 21:45:00 21:58:40
 
Sample Output:
 SC3021234 CS301133
 
翻译：
 每天第一个到的人开门，最后一个到的人锁门。找出开门和锁门的人。
 
输入：
 有n个同学
 某个同学的学号 到达的时间 离开的时间
 
代码 
难点：
 网上的C语言代码可以采用
 
 
 
scanf(“%d:%d:%d %d:%d:%d”, &h1, &m1, &s1, &h2, &m2, &s2);
 
 
很方便地把时间里面“：”给分离出来。
 但是C++是cin输入。
 但是在查资料后得知
 
 
 
C++添加的string字符串是一个类，该类对运算符>、<和==进行了重载，能够直接比较两个字符串的大小。
 
 
#include
using namespace std;
struct Student{
    string id;
    string in;
    string out;
};
int main()
{
    int n;
    cin>>n;
    struct Student s[20];
    for(int i=0;i
        cin>>s[i].id>>s[i].in>>s[i].out;
    }
    string unlock,lock;
    string early="24:00:00",late="00:00:00";
    for(int i=0;i
        if(s[i].in
            unlock=s[i].id;
            early=s[i].in;
        }
        if(s[i].out>late){
            lock=s[i].id; 
            late=s[i].out;
        }
    }
    cout< 
END