数据结构题集整理

sterne 发布于

因为考试看不到练习的在线题集，所以放一下原题和代码

但是有一说一，因为blog没做目录，这篇翻起来应该相当痛苦（）可恶，为什么时至今日我才发现目录能调出来

1.tree

1-1(funx) 二叉树的遍历

本题要求给定二叉树的4种遍历。

函数接口定义：

1
2
3
4
void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );
void LevelorderTraversal( BinTree BT );

其中BinTree结构定义如下：

1
2
3
4
5
6
7
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

要求4个函数分别按照访问顺序打印出结点的内容，格式为一个空格跟着一个字符。

裁判测试程序样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>
#include <stdlib.h>

typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

BinTree CreatBinTree(); /* 实现细节忽略 */
void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );
void LevelorderTraversal( BinTree BT );

int main()
{
    BinTree BT = CreatBinTree();
    printf("Inorder:");    InorderTraversal(BT);    printf("\n");
    printf("Preorder:");   PreorderTraversal(BT);   printf("\n");
    printf("Postorder:");  PostorderTraversal(BT);  printf("\n");
    printf("Levelorder:"); LevelorderTraversal(BT); printf("\n");
    return 0;
}
/* 你的代码将被嵌在这里 */

输出样例（对于图中给出的树）：

1
2
3
4
Inorder: D B E F A G H C I
Preorder: A B D F E C G H I
Postorder: D E F B H G I C A
Levelorder: A B C D F G I E H

Code Size Limit

16 KB

Time Limit

400 ms

Memory Limit

64 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
BinTree q[10007];
int front=0,rear=0;
void push(BinTree x){
    q[rear++]=x;
}
BinTree pop(){
    return q[front++];
}
void InorderTraversal( BinTree BT ){
    if(BT){
        InorderTraversal(BT->Left);
        printf(" %c",BT->Data);
        InorderTraversal(BT->Right);
    }
}
void PreorderTraversal( BinTree BT ){
    if(BT){
        printf(" %c",BT->Data);
        PreorderTraversal(BT->Left);
        PreorderTraversal(BT->Right);
    }
}
void PostorderTraversal( BinTree BT ){
    if(BT){
        PostorderTraversal(BT->Left);
        PostorderTraversal(BT->Right);
        printf(" %c",BT->Data);
    }
}
void LevelorderTraversal( BinTree BT ){
    if(BT) {
        push(BT);
        while (front != rear) {
            BinTree t = pop();
            printf(" %c", t->Data);
            if (t->Left) push(t->Left);
            if (t->Right) push(t->Right);
        }
    }
}

1-1 Tree Traversals Again

An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.

Figure 1

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: “Push X” where X is the index of the node being pushed onto the stack; or “Pop” meaning to pop one node from the stack.

Output Specification:

For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

1
2
3
4
5
6
7
8
9
10
11
12
13
6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop

Sample Output:

1
3 4 2 6 5 1

Code Size Limit

16 KB

Time Limit

400 ms

Memory Limit

64 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;
int n;
typedef struct node {
    int data;
    node *left, *right;
    bool lisnull,risnull;
    node(){
        left= nullptr;
        right= nullptr;
        lisnull=false;
        risnull=false;
    }
}node,*Tree;
stack<Tree> st;
void CreateTree(Tree &T){//非递归建树模版
    string s;int x;
    cin>>s>>x;
    T->data=x;
    st.push(T);
    while(!st.empty()){
        cin>>s;
        if(s=="Push"){
            cin>>x;
            Tree temp=new node;
            temp->data=x;
            Tree f=st.top();
            if(!f->lisnull) {
                f->left=temp;
                f->lisnull=true;
            }
            else if(!f->risnull) {
                f->right=temp;
                f->risnull=true;
                st.pop();
            }
            st.push(temp);
        }
        else if(s=="Pop"){
            Tree p=st.top();
            if(!p->lisnull){
                p->left= nullptr;
                p->lisnull=true;
            }
            else{
                p->right= nullptr;
                p->risnull=true;
                st.pop();
            }
        }
    }
}
void PostOrder(Tree T){
    if(T){
        PostOrder(T->left);
        PostOrder(T->right);
        cout<<T->data;
        if(--n!=0){cout<<' ';}
    }
}
int main(){
    cin>>n;
    Tree T=new node;
    CreateTree(T);
    PostOrder(T);
}

1-2 还原二叉树

给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。

输入格式:

输入首先给出正整数N（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。

输出格式:

输出为一个整数，即该二叉树的高度。

输入样例:

1
2
3
9
ABDFGHIEC
FDHGIBEAC

输出样例:

1
5

Code Size Limit

16 KB

Time Limit

400 ms

Memory Limit

64 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;
typedef char Elemtype;
typedef struct BiTree{
    Elemtype data;
    BiTree *lchild,*rchild;
}BiTree,*Tree;
const int maxn=10007;
Elemtype pre[maxn],in[maxn];
int cnt=0;

Tree CreateTree(int pre_l,int pre_r,int in_l,int in_r){//DLR LDR的范围
    auto T=(Tree)malloc(sizeof(BiTree));
    T->data=pre[pre_l];
    T->lchild= nullptr;
    T->rchild= nullptr;
    int llen,rlen;
    for(int i=in_l;i<=in_r;i++){
        if(in[i]==T->data){
            llen=i-in_l;
            rlen=in_r-i;
            break;
        }
    }
    if(llen){
        T->lchild=CreateTree(pre_l+1,pre_l+llen,in_l,in_l+llen-1);
    }
    if(rlen){
        T->rchild=CreateTree(pre_r-rlen+1,pre_r,in_r-rlen+1,in_r);
    }
    return T;
}
int getDepth(Tree T){
    if(!T) return 0;
    else return max(getDepth(T->lchild), getDepth(T->rchild))+1;
}
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>pre[i];
    }
    for(int i=1;i<=n;i++){
        cin>>in[i];
    }

    Tree T= CreateTree(1,n,1,n);
    cout<<getDepth(T)<<endl;

    return 0;
}
/*
7
ABCDEFG
CBEDAFG
 */

*前中后序遍历建树模板

啊，我想想放哪了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Tree CreateTree(char in[],char post[],int n){
    if(n<=0) return nullptr;
    node *p=new node;
    p->data=post[n-1];
    int i=0;
    for(;i<n&&(in[i]!=p->data);i++);
    p->l= CreateTree(in,post,i);
    p->r= CreateTree(in+1+i,post+i,n-i-1);
    return p;
}
Tree CreateTree2(int pre1,int pre2,int in1,int in2){
    node *p=new node;
    p->l= nullptr;p->r= nullptr;
    p->data=pre[pre1];
    int i=0;
    while(in[in1+i]!=p->data) i++;
    if(i>0)
        p->l= CreateTree2(pre1+1,pre2+i,in1,in1+i-1);
    if(in1+i<in2)
        p->r= CreateTree2(pre1+i+1,pre2,in1+i+1,in2);
    return p;
}

1-3 玩转二叉树

给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。

输出格式：

在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

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

输出样例：

1
4 6 1 7 5 3 2

Code Size Limit

16 KB

Time Limit

400 ms

Memory Limit

64 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
using namespace std;
typedef int Elemtype;
typedef struct BiTree{
    Elemtype data;
    BiTree *lchild,*rchild;
}BiTree,*Tree;
const int maxn=10007;
Elemtype pre[maxn],in[maxn];
int cnt=0;
int n;
Tree CreateTree(int pre_l,int pre_r,int in_l,int in_r){//DLR LDR的范围 和上一题一样
    auto T=(Tree)malloc(sizeof(BiTree));
    T->data=pre[pre_l];
    T->lchild= nullptr;
    T->rchild= nullptr;
    int llen,rlen;
    for(int i=in_l;i<=in_r;i++){
        if(in[i]==T->data){
            llen=i-in_l;
            rlen=in_r-i;
            break;
        }
    }
    if(llen){
        T->lchild=CreateTree(pre_l+1,pre_l+llen,in_l,in_l+llen-1);
    }
    if(rlen){
        T->rchild=CreateTree(pre_r-rlen+1,pre_r,in_r-rlen+1,in_r);
    }
    return T;
}
void reverse(Tree T){
    if(T){
        auto temp=T->lchild;
        T->lchild=T->rchild;
        T->rchild=temp;
        reverse(T->lchild);
        reverse(T->rchild);
    }
}
Tree q[10007];
int front=0,rear=0;
void push(Tree x){
    q[rear++]=x;
}
Tree pop(){
    return q[front++];
}
void LevelorderTraversal( Tree BT ){
    if(BT) {
        push(BT);
        while (front != rear) {
            Tree t = pop();
            cout<<t->data;
            if(--n!=0) cout<<' ';
            if (t->lchild) push(t->lchild);
            if (t->rchild) push(t->rchild);
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>in[i];
    }
    for(int i=1;i<=n;i++){
        cin>>pre[i];
    }


    Tree T= CreateTree(1,n,1,n);
    reverse(T);
    LevelorderTraversal(T);
    return 0;
}
/*
7
ABCDEFG
CBEDAFG
 */

1-4 小字辈

本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。

输入格式：

输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） —— 简单起见，我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号，其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。

输出格式：

首先输出最小的辈分（老祖宗的辈分为 1，以下逐级递增）。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔，行首尾不得有多余空格。

输入样例：

1
2
9
2 6 5 5 -1 5 6 4 7

输出样例：

1
2
4
1 9

Code Size Limit

16 KB

Time Limit

400 ms

Memory Limit

64 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;

int n,f,maxdep;
vector<int> vec[maxn];
int depth[maxn];
void bfs(){
    memset(depth,0,sizeof(depth));
    queue<int>que;
    que.push(f);
    depth[f]=1;
    maxdep=1;
    while(!que.empty()){
        int temp=que.front();
        que.pop();
        for(int i=0;i<vec[temp].size();i++){
            int node=vec[temp][i];
            depth[node]=depth[temp]+1;
            maxdep=depth[node];
            que.push(node);
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int y;cin>>y;
        if(y==-1) f=i;//根节点=i
        vec[y].push_back(i);
    }
    bfs();
    cout<<maxdep<<endl;
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(depth[i]==maxdep) {
            if(!cnt){
                cout<<i;
                cnt=1;
            }
            else cout<<' '<<i;
        }
    }
}

1-5 列出叶节点

对于给定的二叉树，本题要求你按从上到下、从左到右的顺序输出其所有叶节点。

输入格式：

首先第一行给出一个正整数 N（≤10），为树中结点总数。树中的结点从 0 到 N−1 编号。随后 N 行，每行给出一个对应结点左右孩子的编号。如果某个孩子不存在，则在对应位置给出 “-“。编号间以 1 个空格分隔。

输出格式：

在一行中按规定顺序输出叶节点的编号。编号间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

1
2
3
4
5
6
7
8
9
8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6

输出样例：

1
4 1 5

Code Size Limit

16 KB

Time Limit

400 ms

Memory Limit

64 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
    int left,right;
    int f;
}tree[107];
vector<int> ans;
void init(){
    for(int i=0;i<107;i++){
        tree[i].left=-1;
        tree[i].right=-1;
        tree[i].f=-1;
    }
}
void bfs(int x){
    queue<int>que;
    que.push(x);
    while(!que.empty()){
        int temp=que.front();
        que.pop();
        int l=tree[temp].left,r=tree[temp].right;
        if(l==-1&&r==-1){
            ans.push_back(temp);
        }
        if(l!=-1){
            que.push(l);
        }
        if(r!=-1){
            que.push(r);
        }
    }
}
int main(){
    cin>>n;
    init();
    for(int i=0;i<n;i++){
        string x,y;cin>>x>>y;
        if(x!="-"){
            int t=stoi(x);
            tree[i].left=t;
            tree[t].f=i;
        }
        if(y!="-"){
            int t=stoi(y);
            tree[i].right=t;
            tree[t].f=i;
        }
    }
    for(int i=0;i<n;i++){
        if(tree[i].f==-1){
            bfs(i);
        }
    }
    for(int i=0;i<ans.size();i++){
        if(!i)cout<<ans[i];
        else cout<<' '<<ans[i];
    }
}

1-6 修理牧场

农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数L**i个长度单位，于是他购买了一条很长的、能锯成N块的木头，即该木头的长度是L**i的总和。

但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费为35（大于32）。

请编写程序帮助农夫计算将木头锯成N块的最少花费。

输入格式:

输入首先给出正整数N（≤104），表示要将木头锯成N块。第二行给出N个正整数（≤50），表示每段木块的长度。

输出格式:

输出一个整数，即将木头锯成N块的最少花费。

输入样例:

1
2
8
4 5 1 2 1 3 1 1

输出样例:

1
49

Code Size Limit

16 KB

Time Limit

400 ms

Memory Limit

64 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//huffman树所有非叶节点权值和
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=10007;
typedef long long ll;
struct TreeNode {
    int weight;
    int pos;
    int left,right;
    bool operator<(const TreeNode &a)const{//使用优先队列，重载小于号，使优先队列变为按照weight值从小到大排序
        return weight>a.weight;
    }
    TreeNode() {//结构体构造函数
        weight = inf;//将权的初始值置为
        pos=0;
        left=right=-1;
    };
};
int n;
int a[maxn];
TreeNode T[10*maxn];
ll Huffman(int a[],int n){//通过给定的权值建立哈夫曼树
    ll ans=0;
    priority_queue<TreeNode> que;//优先队列
    for(int i=0;i<n;i++){
        TreeNode temp;
        temp.weight=a[i];
        temp.pos=i;
        T[i]=temp;
        que.push(temp);
    }//构建结点,将结点存入数组中并存入队列
    int cnt=n;
    while(!que.empty()){
        auto n1=que.top();
        que.pop();
        auto n2=que.top();
        que.pop();//取出最小的两个权值并将其从队列中删除
        TreeNode newNode;//建n1和n2的父节点，下面是一些赋值操作
        newNode.weight=n1.weight+n2.weight;//父节点权值等于n1和n2权值之和
        ans+=newNode.weight;
        newNode.pos=cnt;//记录父节点的位置
        newNode.left=n1.pos;//记录左孩子和右孩子在数组中的位置
        newNode.right=n2.pos;
//        T[n1.pos].parent=T[n2.pos].parent=newNode.pos;//记录左孩子和右孩子的父节点的位置
        T[cnt++]=newNode;//将父节点存入数组T中
        if(cnt==2*n-1) break;//已录入全部结点信息  N = 2*n0-1
        que.push(newNode);//将父节点存入队列，进行下一次循环，再取权值最小的两个节点进行连接
    }
    return ans;
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    if(n==1) cout<<0<<endl;
    else cout<<Huffman(a,n)<<endl;
}

1-7 ZigZagging on a Tree

Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences. And it is a simple standard routine to print the numbers in level-order. However, if you think the problem is too simple, then you are too naive. This time you are supposed to print the numbers in “zigzagging order” – that is, starting from the root, print the numbers level-by-level, alternating between left to right and right to left. For example, for the following tree you must output: 1 11 5 8 17 12 20 15.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the inorder sequence and the third line gives the postorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the zigzagging sequence of the tree in a line. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

1
2
3
8
12 11 20 17 1 15 8 5
12 20 17 11 15 8 5 1

Sample Output:

1
1 11 5 8 17 12 20 15

Code Size Limit

16 KB

Time Limit

400 ms

Memory Limit

64 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<bits/stdc++.h>
using namespace std;
const int maxn=50;
typedef struct node{
    node *l,*r;
    int data;
    int depth;
    node(){
        l=r= nullptr;
        data=0;
        depth=0;
    }
}node,*Tree;
int in[maxn],post[maxn];
Tree CreateTree(int in[],int post[],int n){
    if(n<=0) return nullptr;
    node *p=new node;
    p->data=post[n-1];
    int i=0;
    for(;i<n&&(in[i]!=p->data);i++);
    p->l= CreateTree(in,post,i);
    p->r= CreateTree(in+1+i,post+i,n-i-1);
    return p;
}


struct point{
    int data;
    int depth;
    point(){}
    point(int da,int de){
        data=da;
        depth=de;
    }
};
int depth[maxn];
vector<point> ans;
void init(){
    memset(depth,0,sizeof(depth));
}
void Zig(Tree T){//深度反转
    queue<Tree>que;
    T->depth=1;
    que.push(T);
    while(!que.empty()){
        Tree temp=que.front();
        que.pop();
        ans.push_back(point(temp->data,temp->depth));
        int d=temp->depth;
        if(temp->l) {
            temp->l->depth=d+1;
            que.push(temp->l);
        }
        if(temp->r){
            temp->r->depth=d+1;
            que.push(temp->r);
        }
    }
    stack<int>st;
    int cnt=0;
    for(int i=0;i<ans.size();i++){
        if(ans[i].depth%2){
            st.push(ans[i].data);
        }
        else{
            while(!st.empty()){
                if(!cnt) {
                    cout<<st.top();
                    cnt++;
                }
                else cout<<' '<<st.top();
                st.pop();
            }
            cout<<' '<<ans[i].data;
        }
    }
    while(!st.empty()){
        if(!cnt) {
            cout<<st.top();
            cnt++;
        }
        else{
            cout<<' '<<st.top();
        }
        st.pop();
    }
}
int main(){
    int n;cin>>n;
    for(int i=0;i<n;i++){
        cin>>in[i];
    }
    for(int i=0;i<n;i++){
        cin>>post[i];
    }

    Tree T= CreateTree(in,post,n);
    Zig(T);
    return 0;
}

1-8 Path of Equal Weight

Given a non-empty tree with root R, and with weight $W_i$ assigned to each tree node $T_i$. The weight of a path from $R$ to $L$ is defined to be the sum of the weights of all the nodes along the path from R to any leaf node L.

Now given any weighted tree, you are supposed to find all the paths with their weights equal to a given number. For example, let’s consider the tree showed in the following figure: for each node, the upper number is the node ID which is a two-digit number, and the lower number is the weight of that node. Suppose that the given number is 24, then there exists 4 different paths which have the same given weight: {10 5 2 7}, {10 4 10}, {10 3 3 6 2} and {10 3 3 6 2}, which correspond to the red edges in the figure.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 0<N≤100, the number of nodes in a tree, M (<N), the number of non-leaf nodes, and 0<S<230, the given weight number. The next line contains N positive numbers where W**i (<1000) corresponds to the tree node T**i. Then M lines follow, each in the format:

1
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 00.

Output Specification:

For each test case, print all the paths with weight S in non-increasing order. Each path occupies a line with printed weights from the root to the leaf in order. All the numbers must be separated by a space with no extra space at the end of the line.

Note: sequence {A1,A2,⋯,A**n} is said to be greater than sequence {B1,B2,⋯,B**m} if there exists 1≤k<*min*{*n*,*m*} such that *Ai=B**i for i=1,⋯,k, and A**k+1>*B**k+1.

Sample Input:

1
2
3
4
5
6
7
8
9
10
11
20 9 24
10 2 4 3 5 10 2 18 9 7 2 2 1 3 12 1 8 6 2 2
00 4 01 02 03 04
02 1 05
04 2 06 07
03 3 11 12 13
06 1 09
07 2 08 10
16 1 15
13 3 14 16 17
17 2 18 19

Sample Output:

1
2
3
4
10 5 2 7
10 4 10
10 3 3 6 2
10 3 3 6 2

Special thanks to Zhang Yuan and Yang Han for their contribution to the judge’s data.

Code Size Limit

16 KB

Time Limit

400 ms

Memory Limit

64 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
//注：未知原因2个测试点不过
//	max size N
//sorting children only is NOT correct
#include<bits/stdc++.h>
using namespace std;
const int maxn=300;
typedef long long ll;
int n,m;
ll s;
ll weight[maxn];
struct node{
    int num;
    ll w;
    node(int n){
        num=n;
        w=0;
    }
};
struct order{
    int arr[maxn],l;
    order(ll a[],int len){
        l=len;
        for(int i=0;i<len;i++){
            arr[i]=a[i];
        }
    }
};
bool cmp(order &a,order &b){
    for(int i=0;i<a.l&&i<b.l;i++){
        if(a.arr[i]>b.arr[i]) return true;
    }
    return false;
}
vector<node> T[maxn];
vector<ll> route[maxn];
vector<order> output;
void dfs(int x,ll w){
    if(!T[x].size()){
        if(w==s){
            route[x].push_back(weight[x]);
            ll arr[maxn];
            for(int i=0;i<route[x].size();i++){
                arr[i]=route[x][i];
            }
            output.emplace_back(arr,route[x].size());
        }
        return;
    }
    for(int i=0;i<T[x].size();i++){
        int temp=T[x][i].num;
        T[x][i].w=w+weight[temp];
        route[temp]=route[x];
        route[temp].push_back(weight[x]);
        dfs(temp,w+weight[temp]);
    }
}
int main(){
    cin>>n>>m>>s;
    for(int i=0;i<n;i++){
        cin>>weight[i];
    }
    for(int i=0;i<m;i++){
        int num,mm;cin>>num>>mm;
        for(int j=0;j<mm;j++){
            int x;cin>>x;
            T[num].emplace_back(x);
        }
    }
    dfs(0,weight[0]);
    sort(output.begin(),output.end(),cmp);
    for(int i=0;i<output.size();i++){
        for(int j=0;j<output[i].l;j++){
            cout<<output[i].arr[j];
            if(j!=output[i].l-1) cout<<' ';
        }
        cout<<endl;
    }
}

1-9 哈夫曼编码

给定一段文字，如果我们统计出字母出现的频率，是可以根据哈夫曼算法给出一套编码，使得用此编码压缩原文可以得到最短的编码总长。然而哈夫曼编码并不是唯一的。例如对字符串”aaaxuaxz”，容易得到字母 ‘a’、’x’、’u’、’z’ 的出现频率对应为 4、2、1、1。我们可以设计编码 {‘a’=0, ‘x’=10, ‘u’=110, ‘z’=111}，也可以用另一套 {‘a’=1, ‘x’=01, ‘u’=001, ‘z’=000}，还可以用 {‘a’=0, ‘x’=11, ‘u’=100, ‘z’=101}，三套编码都可以把原文压缩到 14 个字节。但是 {‘a’=0, ‘x’=01, ‘u’=011, ‘z’=001} 就不是哈夫曼编码，因为用这套编码压缩得到 00001011001001 后，解码的结果不唯一，”aaaxuaxz” 和 “aazuaxax” 都可以对应解码的结果。本题就请你判断任一套编码是否哈夫曼编码。

输入格式：

首先第一行给出一个正整数 N（2≤N≤63），随后第二行给出 N 个不重复的字符及其出现频率，格式如下：

1
c[1] f[1] c[2] f[2] ... c[N] f[N]

其中c[i]是集合{‘0’ - ‘9’, ‘a’ - ‘z’, ‘A’ - ‘Z’, ‘_’}中的字符；f[i]是c[i]的出现频率，为不超过 1000 的整数。再下一行给出一个正整数 M（≤1000），随后是 M 套待检的编码。每套编码占 N 行，格式为：

1
c[i] code[i]

其中c[i]是第i个字符；code[i]是不超过63个’0’和’1’的非空字符串。

输出格式：

对每套待检编码，如果是正确的哈夫曼编码，就在一行中输出”Yes”，否则输出”No”。

注意：最优编码并不一定通过哈夫曼算法得到。任何能压缩到最优长度的前缀编码都应被判为正确。

输入样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
7
A 1 B 1 C 1 D 3 E 3 F 6 G 6
4
A 00000
B 00001
C 0001
D 001
E 01
F 10
G 11
A 01010
B 01011
C 0100
D 011
E 10
F 11
G 00
A 000
B 001
C 010
D 011
E 100
F 101
G 110
A 00000
B 00001
C 0001
D 001
E 00
F 10
G 11

输出样例：

1
2
3
4
Yes
Yes
No
No

Code Size Limit

16 KB

Time Limit

400 ms

Memory Limit

64 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
//注：我tm上学期就见过你了，抄的代码，爬
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <cstdlib>
#include <map>
#include <bitset>
#include <unordered_map>
#include <ctime>
#include <vector>
#include <queue>
#include <list>

#define R register
#define L long
#define LL long long
#define I inline
#define U unsigned
using namespace std;

I LL read()
{
    R LL   x;
    R bool f;
    R char c;
    for(f=0;(c=getchar())<'0'||c>'9';f=c=='-');
    for(x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');
    return f?-x:x;
}

#define MAXN 1000
struct node
{
    struct node*l,*r;
    int        value;
    char       code;
    bool operator()(const node *a,const node *b)
    {
        return a->value>b->value;
    }
};

struct DataT
{
    int  value;
    char code;
};

DataT Data[MAXN];

int getValue(char code,int n)
{
    for(int i=0;i<n;++i)
        if(Data[i].code==code)
            return Data[i].value;
    return 0;
}

node*newNode()
{
    node*tmp=(node*)malloc(sizeof(node));
    tmp->l=tmp->r=NULL;
    tmp->value=0;
    tmp->code =0;
    return tmp;
}

bool ERR_FLAG=false;

node*addTree(node*rt,char c,char s[],int Datan,int sn,int si)
{
    if(sn==si)
    {
        if(rt!=NULL)
        {
            ERR_FLAG=true;
            return rt;
        }
        else
        {
            node*tmp=newNode();
            tmp->value=getValue(c,Datan)*sn;
            return tmp;
        }
    }
    if(!rt)rt=newNode();
    if(s[si]=='0')
        rt->l=addTree(rt->l,c,s,Datan,sn,si+1);
    else
        rt->r=addTree(rt->r,c,s,Datan,sn,si+1);
    rt->value=((rt->l)?(rt->l->value):0)+((rt->r)?(rt->r->value):0);
    return rt;
}


int ddfs(node *rt,int n)
{
    if(!rt)
        return 0;
    if(rt->l||rt->r)
        rt->value=ddfs(rt->l,n+1)+ddfs(rt->r,n+1);
    else
    {
        rt->value*=n;
    }
    return rt->value;
}
int getAns(int n)
{
    priority_queue <node*,vector<node*>,node> q;
    for(int i=0;i<n;++i)
    {
        node * tmp=newNode();
        *tmp=(node){NULL,NULL,Data[i].value,Data[i].code};
        q.push(tmp);
    }
    
    while(q.size()>1)
    {
        node* t1=q.top();q.pop();
        node* t2=q.top();q.pop();
        node * tmp=newNode();
        tmp->l=t1;
        tmp->r=t2;
        tmp->value=t1->value+t2->value;
        q.push(tmp);
    }
    return  ddfs(q.top(),0);
}


int main()
{
//     freopen("7-1.in","r",stdin);
//  freopen("7-1.out","w",stdout);
    int     n=read();
    for(int i=0;i<n;++i)
    {
        char s[10];
        scanf("%s%d",s,&Data[i].value);
        Data[i].code=s[0];
    }
    int ans=getAns(n);
    for(int t=read();t--;)
    {
        ERR_FLAG=false;
        node    *rt=NULL;
        for(int i  =0;i<n;++i)
        {
            char c[10],s[MAXN];
            scanf("%s%s",c,s);
            if(!ERR_FLAG)
                rt=addTree(rt,c[0],s,n,strlen(s),0);
        }
        printf("%s\n",(!ERR_FLAG&&(!rt||rt->value==ans))?"Yes":"No");
    }
    
    
//     fclose(stdin);
//     fclose(stdout);
    return 0;
}

2.sort

2-1(funx) Iterative Mergesort

How would you implement mergesort without using recursion?

The idea of iterative mergesort is to start from N sorted sublists of length 1, and each time to merge a pair of adjacent sublists until one sorted list is obtained. You are supposed to implement the key function of merging.

Format of functions:

1
void merge_pass( ElementType list[], ElementType sorted[], int N, int length );

The function merge_pass performs one pass of the merge sort that merges adjacent pairs of sublists from list into sorted. N is the number of elements in the list and length is the length of the sublists.

Sample program of judge:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>

#define ElementType int
#define MAXN 100

void merge_pass( ElementType list[], ElementType sorted[], int N, int length );

void output( ElementType list[], int N )
{
    int i;
    for (i=0; i<N; i++) printf("%d ", list[i]);
    printf("\n");
}

void  merge_sort( ElementType list[],  int N )
{
    ElementType extra[MAXN];  /* the extra space required */
    int  length = 1;  /* current length of sublist being merged */
    while( length < N ) { 
        merge_pass( list, extra, N, length ); /* merge list into extra */
        output( extra, N );
        length *= 2;
        merge_pass( extra, list, N, length ); /* merge extra back to list */
        output( list, N );
        length *= 2;
    }
} 


int main()
{
    int N, i;
    ElementType A[MAXN];

    scanf("%d", &N);
    for (i=0; i<N; i++) scanf("%d", &A[i]);
    merge_sort(A, N);
    output(A, N);

    return 0;
}

/* Your function will be put here */

Sample Input:

1
2
10
8 7 9 2 3 5 1 6 4 0

Sample Output:

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

Code Size Limit

16 KB

Time Limit

400 ms

Memory Limit

64 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void merge_pass( ElementType list[], ElementType sorted[], int N, int length ){
    int cnt=0;
    int i;
    for(i=0;i<N&&i+length<N;i+=length*2){
        int p=i,q=i+length;
        while(p<i+length&&q<i+length*2&&q<N){
            if(list[p]<list[q]) sorted[cnt++]=list[p++];
            else sorted[cnt++]=list[q++];
        }
        while(p<i+length) sorted[cnt++]=list[p++];
        while(q<i+length*2&&q<N) sorted[cnt++]=list[q++];
    }
    if(i+length>=N){
        while(i<N) sorted[cnt++]=list[i++];
    }
}

2-2(funx) The Kth Largest in BST

Given a binary search tree, you are supposed to find the node that contains the K-th largest key.

Format of function:

1
BinTree KthLargest ( BinTree T, int K );

where BinTree is defined as the following:

1
2
3
4
5
6
typedef struct TNode *BinTree;
struct TNode{
    int Key;
    BinTree Left;
    BinTree Right;
};

The function KthLargest is supposed to return the pointer that points to the node that contains the K-th largest key in the binary search tree T.

Here T is not empty and all its keys are distinct positive integers. K is positive and is never more than the total number of nodes in the tree.

Sample program of judge:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
#include <stdlib.h>

typedef struct TNode *BinTree;
struct TNode{
    int Key;
    BinTree Left;
    BinTree Right;
};

BinTree BuildTree(); /* details omitted */
BinTree KthLargest ( BinTree T, int K );

int main()
{
    BinTree T, P;
    int K;

    T = BuildTree();
    scanf("%d", &K);
    P = KthLargest(T, K);
    printf("%d\n", P->Key);
    if (P->Left) printf("%d\n", P->Left->Key);
    else printf("NULL\n");
    if (P->Right) printf("%d\n", P->Right->Key);
    else printf("NULL\n");

    return 0;
}
/* Your function will be put here */

Sample Input: (for the following tree)

1
4

Sample Output:

1
2
3
5
NULL
7

Code Size Limit

16 KB

Time Limit

400 ms

Memory Limit

64 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//本质二叉树，RDL
int cnt=0;
BinTree KthLargest ( BinTree T, int K ){
    BinTree P,Q;
    if(T){
        P=KthLargest(T->Right,K);
        if(P) return P;//? 在递归层中返回了T'，要传回
        cnt++;
        if(cnt==K){
            return T;
        }
        Q=KthLargest(T->Left,K);
        if(Q) return Q;
    }
    else return NULL;
}

2-3(funx) Rank a Linked List (II)

A linked list of n nodes is stored in an array of n elements. Each element contains an integer data and a next pointer which is the array index of the next element. It is guaranteed that the given list is linear – that is, every node, except the first one, has a unique previous node; and every node, except the last one, has a unique next node.

You are supposed to write a function to number these nodes in reverse order, starting from the last node, by numbers from 1 to n. These numbers are called the ranks of the nodes.

Format of function:

1
void Ranking( List A[], int n );

where List is defined as the following:

1
2
3
4
5
typedef struct Node {
    int data;
    int next;
    int rank;
} List;

Sample program of judge:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
#include <stdlib.h>

#define NIL -1 //represents the NULL pointer

typedef struct Node {
    int data;
    int next;
    int rank;
} List;

void Ranking( List A[], int n );

int main()
{
    int n, i;
    List *A;
    
    scanf("%d", &n);
    A = (List *)malloc(sizeof(List)*n);
    for (i=0; i<n; i++) scanf("%d", &A[i].next);
    Ranking(A, n);
    for (i=0; i<n; i++) printf("%d ", A[i].rank);
    printf("\n");
    
    return 0;
}

/* Your function will be put here */

Sample Input:

1
2
5
3 -1 0 1 2

Sample Output:

1
3 1 4 2 5

Hint:

The given linked list is stored as 4->2->0->3->1->NULL. Hence the 0th element is ranked 3 since it is the 3rd node counted from the last one in the list; the 1st element is ranked 1 since it is the last node in the list; and so on so forth.

Code Size Limit

16 KB

Time Limit

100 ms

Memory Limit

64 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int vis[100007];
void Ranking( List A[], int n ){
    int head;
    for(int i=0;i<n;i++){
        if(A[i].rank!=-1)
            vis[A[i].next]=1;
    }
    for(int i=0;i<n;i++){
        if(!vis[i]) {
            head=i;
            break;
        }
    }
    int cnt=n;
    A[head].rank=cnt--;
    int temp=A[head].next;
    while(temp!=-1){
        A[temp].rank=cnt--;
        temp=A[temp].next;
    }
}

2-1 两个有序序列的中位数

已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A0,A1,⋯,A**N−1的中位数指A(N−1)/2的值,即第⌊(N+1)/2⌋个数（A0为第1个数）。

输入格式:

输入分三行。第一行给出序列的公共长度N（0<N≤100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。

输出格式:

在一行中输出两个输入序列的并集序列的中位数。

输入样例1:

1
2
3
5
1 3 5 7 9
2 3 4 5 6

输出样例1:

1
4

输入样例2:

1
2
3
6
-100 -10 1 1 1 1
-50 0 2 3 4 5

输出样例2:

1
1

Code Size Limit

16 KB

Time Limit

200 ms

Memory Limit

64 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+7;
int a[maxn];
int n;
int main(){
    cin>>n;
    for(int i=1;i<=n*2;i++){
        cin>>a[i];
    }
    sort(a+1,a+n*2+1);
    cout<<a[(n*2+1)/2]<<endl;
}

2-2 词频统计

请编写程序，对一段英文文本，统计其中所有不同单词的个数，以及词频最大的前10%的单词。

所谓“单词”，是指由不超过80个单词字符组成的连续字符串，但长度超过15的单词将只截取保留前15个单词字符。而合法的“单词字符”为大小写字母、数字和下划线，其它字符均认为是单词分隔符。

输入格式:

输入给出一段非空文本，最后以符号#结尾。输入保证存在至少10个不同的单词。

输出格式:

在第一行中输出文本中所有不同单词的个数。注意“单词”不区分英文大小写，例如“PAT”和“pat”被认为是同一个单词。

随后按照词频递减的顺序，按照词频:单词的格式输出词频最大的前10%的单词。若有并列，则按递增字典序输出。

输入样例：

1
2
3
4
5
6
This is a test.

The word "this" is the word with the highest frequency.

Longlonglonglongword should be cut off, so is considered as the same as longlonglonglonee.  But this_8 is different than this, and this, and this...#
this line should be ignored.

输出样例：

（注意：虽然单词the也出现了4次，但因为我们只要输出前10%（即23个单词中的前2个）单词，而按照字母序，the排第3位，所以不输出。）

1
2
3
23
5:this
4:is

Code Size Limit

16 KB

Time Limit

2000 ms

Memory Limit

64 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
const int maxn=100007;
struct mp{
    string s;
    int n;
}m[maxn];
int num=0;//不同单词数
bool cmp(mp &a,mp &b){
    if(a.n==b.n) return a.s<b.s;
    else return a.n>b.n;
}
int find(string &s){
    transform(s.begin(),s.end(),s.begin(),::tolower);//全转小写
    bool fl=false;
    for(int i=0;i<num;i++){
        if(m[i].s==s){//也可以写成vector
            fl=true;
            m[i].n++;
            return i;
        }
    }
    if(!fl){
        m[num].s=s;
        m[num++].n=1;
    }
}
int main(){
//    map<string,int>mp;
    char c;
    string s="";
    int len=0;//单词长度
    bool inword;
    inword=false;
    while((c=getchar())!='#'){
        if(c=='#') break;
        if(!inword&&(isalpha(c)|| isdigit(c)||c=='_')){
            inword=true;
            len++;
            if(len<=15){
                s+=c;
            }
        }
        else if(inword&&(isalpha(c)|| isdigit(c)||c=='_')){
            len++;
            if(len<=15) s+=c;
        }
        else if(inword&&!(isalpha(c)|| isdigit(c)||c=='_')){
            find(s);
            inword=false;
            len=0;
            s="";
        }
    }
    cout<<num<<endl;
    sort(m,m+num,cmp);
    for(int i=0;i<(num/10);i++){
        cout<<m[i].n<<':'<<m[i].s<<endl;
    }

}

2-3 符号配对

请编写程序检查C语言源程序中下列符号是否配对：/*与*/、(与)、[与]、{与}。

输入格式:

输入为一个C语言源程序。当读到某一行中只有一个句点.和一个回车的时候，标志着输入结束。程序中需要检查配对的符号不超过100个。

输出格式:

首先，如果所有符号配对正确，则在第一行中输出YES，否则输出NO。然后在第二行中指出第一个不配对的符号：如果缺少左符号，则输出?-右符号；如果缺少右符号，则输出左符号-?。

输入样例1：

1
2
3
4
5
6
7
void test()
{
    int i, A[10];
    for (i=0; i<10; i++) { /*/
        A[i] = i;
}
.

输出样例1：

1
2
NO
/*-?

输入样例2：

1
2
3
4
5
6
7
void test()
{
    int i, A[10];
    for (i=0; i<10; i++) /**/
        A[i] = i;
}]
.

输出样例2：

1
2
NO
?-]

输入样例3：

1
2
3
4
5
6
7
8
void test()
{
    int i
    double A[10];
    for (i=0; i<10; i++) /**/
        A[i] = 0.1*i;
}
.

输出样例3：

1
YES

Code Size Limit

16 KB

Time Limit

400 ms

Memory Limit

64 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
//抄的，自己写的在遇到/**/时候寄了
#include<bits/stdc++.h>
using namespace std;
stack<char> st;
char tmp[] = {')','}',']'};
void output(char ch){
    if(ch=='<'){
        cout<<"NO\n/*-?"<<endl;
    }else {
        cout<<"NO\n"<<ch<<"-?"<<endl;
    }
}
bool match(char *c,int len){
    int i=-1;
    int j=0;
    while(++i<len){
        if(c[i]=='/'){
            if(st.empty()) if(c[i + 1] != '*') continue;
            if(c[i+1]=='*'){
                st.push('<');
                ++i;
            }else if(st.top() == '<' && c[i + 1] != '*'){
                cout<<"NO\n/*-?"<<endl;
                return false;
            }
        }else if(c[i]=='*'){
            if(st.empty()){
                if(c[i+1]!='/') continue;
                else{
                    cout<<"NO\n?-*/"<<endl;
                    return false;
                }
            }
            if(st.top() == '<' && c[i + 1] == '/') {
                st.pop();
                ++i;
            }else if(st.top() != '<' && c[i + 1] == '/'){
                output(st.top());
                return false;
            }
        }else if(c[i]=='('||c[i]=='{'||c[i]=='['){
            st.push(c[i]);
        }else if(c[i]==')'||c[i]=='}'||c[i]==']' ){
            if(st.empty()){
                if(c[i]=='}') j=1;
                else if(c[i]==']') j=2;
            }else {
                if(c[i]==')'){
                    if(st.top() == '('){
                        st.pop();
                        continue;
                    }else {
                        output(st.top());
                        return false;
                    }
                }else if(c[i]=='}'){
                    if(st.top() == '{'){
                        st.pop();
                        continue;
                    }else{
                        output(st.top());
                        return false;
                    }
                }else{
                    if(st.top() == '['){
                        st.pop();
                        continue;
                    }else{
                        output(st.top());
                        return false;
                    }
                }
            }
            cout<<"NO\n?-"<<tmp[j]<<endl;
            return false;
        }
    }
    return true;
}
int main(){
    string str;
    while(cin>>str){
        char *c = (char*)str.data();
        if(c[0]=='.'&&c[1]==0)break;
        if(!match(c,str.length())){
            return 0;
        }
    }
    if(st.empty()){
        cout<<"YES"<<endl;
    }else{
        if(st.top() == '<') cout << "NO\n/*-?" << endl;
        else cout << "NO\n" << st.top() << "-?" << endl;
    }
    return 0;
}

2-4 列车调度

火车站的列车调度铁轨的结构如下图所示。

两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{8，4，2，5，3，9，1，6，7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？

输入格式：

输入第一行给出一个整数N (2 ≤ N ≤105)，下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。

输出格式：

在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。

输入样例：

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

输出样例：

1
4

Code Size Limit

16 KB

Time Limit

300 ms

Memory Limit

64 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+7;
int n;
int a[maxn];
set<int>st;
int cnt=0;
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    st.insert(a[0]);
    for(int i=1;i<n;i++){
        int temp=a[i];
        auto iter= st.lower_bound(temp);
        if(iter==st.end()){//全都比temp小
            st.insert(temp);
        }
        else{
            st.erase(iter);
            st.insert(temp);
        }
    }
    cout<<st.size()<<endl;
}

upper_bound&lower_bound

lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

在从大到小的排序数组中，重载lower_bound()和upper_bound()

lower_bound( begin,end,num,greater() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num,greater() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

greater这样写就可以

3.graph

3-1(funx) 邻接表存储图的广度优先遍历

试实现邻接表存储图的广度优先遍历。

函数接口定义：

1
void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) );

其中LGraph是邻接表存储的图，定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* 邻接点的定义 */
typedef struct AdjVNode *PtrToAdjVNode; 
struct AdjVNode{
    Vertex AdjV;        /* 邻接点下标 */
    PtrToAdjVNode Next; /* 指向下一个邻接点的指针 */
};

/* 顶点表头结点的定义 */
typedef struct Vnode{
    PtrToAdjVNode FirstEdge; /* 边表头指针 */
} AdjList[MaxVertexNum];     /* AdjList是邻接表类型 */

/* 图结点的定义 */
typedef struct GNode *PtrToGNode;
struct GNode{  
    int Nv;     /* 顶点数 */
    int Ne;     /* 边数   */
    AdjList G;  /* 邻接表 */
};
typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */

函数BFS应从第S个顶点出发对邻接表存储的图Graph进行广度优先搜索，遍历时用裁判定义的函数Visit访问每个顶点。当访问邻接点时，要求按邻接表顺序访问。题目保证S是图中的合法顶点。

裁判测试程序样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <stdio.h>

typedef enum {false, true} bool;
#define MaxVertexNum 10   /* 最大顶点数设为10 */
typedef int Vertex;       /* 用顶点下标表示顶点,为整型 */

/* 邻接点的定义 */
typedef struct AdjVNode *PtrToAdjVNode; 
struct AdjVNode{
    Vertex AdjV;        /* 邻接点下标 */
    PtrToAdjVNode Next; /* 指向下一个邻接点的指针 */
};

/* 顶点表头结点的定义 */
typedef struct Vnode{
    PtrToAdjVNode FirstEdge; /* 边表头指针 */
} AdjList[MaxVertexNum];     /* AdjList是邻接表类型 */

/* 图结点的定义 */
typedef struct GNode *PtrToGNode;
struct GNode{  
    int Nv;     /* 顶点数 */
    int Ne;     /* 边数   */
    AdjList G;  /* 邻接表 */
};
typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */

bool Visited[MaxVertexNum]; /* 顶点的访问标记 */

LGraph CreateGraph(); /* 创建图并且将Visited初始化为false；裁判实现，细节不表 */

void Visit( Vertex V )
{
    printf(" %d", V);
}

void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) );

int main()
{
    LGraph G;
    Vertex S;

    G = CreateGraph();
    scanf("%d", &S);
    printf("BFS from %d:", S);
    BFS(G, S, Visit);

    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：给定图如下

1
2

输出样例：

1
BFS from 2: 2 0 3 5 4 1 6

Code Size Limit

16 KB

Time Limit

400 ms

Memory Limit

64 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Vertex que[1007];//搓一个最tm简洁的队列
int fro=0,rear=0;
bool vis[MaxVertexNum];
void push(Vertex a){
    que[rear++]=a;
}
Vertex pop(){
    return que[fro++];
}
void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) ){
    for(int i=0;i<MaxVertexNum;i++){
        vis[i]=0;
    }
    push(S);
    vis[S]=true;
    while(fro!=rear){
        Vertex e;
        e=pop();
        Visit(e);
        for(PtrToAdjVNode j=Graph->G[e].FirstEdge;j;j=j->Next){
            if(!vis[j->AdjV]){
                push(j->AdjV);
                vis[j->AdjV]=1;
            }
        }
    }
}

3-2(funx) 邻接矩阵表示及其遍历

本题要求编写函数创建无向图 G 的邻接矩阵存储表示，并求连通分量个数。例如，下图所示一个无向图 G 及其对应的邻接矩阵：

函数接口定义：

1
2
void CreateMGraph(MGraph &G); /* 读入顶点数、边数，以及各条边，创建图 G 的邻接矩阵存储表示 */
int countCC (MGraph G);   /* 已知无向图 G 采用邻接矩阵表示，函数值返回其连通分量个数 */

已知无向图 G 采用邻接矩阵存储，相关类型定义如下：

1
2
3
4
5
6
7
#define MaxVertexNum 100     /* 定义最大顶点数 */
typedef int VertexType;      /* 顶点类型，以整型值编号表示（从 1 开始编号） */
typedef struct{
    int arcs[MaxVertexNum+1][MaxVertexNum+1]; /* 邻接矩阵, 若顶点 i 与 顶点 j 有边相连则 arcs[i][j] 及 arcs[j][i] 均为 1 表示，无边则均为 0 */
    int vexnum;  /* 顶点数 */
    int arcnum;  /* 边数 */
}MGraph;

裁判测试程序样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>

#define MaxVertexNum 100     /* 定义最大顶点数 */

typedef int VertexType;      /* 顶点类型，以整型值编号表示（从 1 开始编号） */
typedef struct{
    int arcs[MaxVertexNum + 1][MaxVertexNum + 1]; /* 无向图的邻接矩阵, 若顶点 i 与 顶点 j 有边相连则 arcs[i][j] 及 arcs[j][i] 均为 1 表示，无边则均为 0 */
    int vexnum;  /* 顶点数 */
    int arcnum;  /* 边数 */
}MGraph;

int visited[MaxVertexNum + 1];  // 顶点是否被访问标志数组

 /* 邻接矩阵编号为 i 的顶点所关联的边存放在行 i 及列 i 中 */

void CreateMGraph(MGraph &G); /* 读入顶点数、边数，以及各条边，创建图 G 的邻接矩阵存储表示 */
int countCC(MGraph G); /* 已知无向图 G 采用邻接矩阵表示，函数值返回其连通分量个数 */

int main()
{
    MGraph G;

    CreateMGraph( G );
    printf("%d\n", countCC( G ));

    return 0;
}

/* 请在这里填写答案 */

输入的第一行为两个整数，分别为图 G 的顶点数 vexnum（0 <= vexnum <= MaxVertexNum） 和边数 arcnum（>= 0），接下来的 arcnum 行是每一条边信息，以关联的两个顶点 i 和 j 给出。
输出为图 G 的连通分量个数。题目保证输入数据正确，无冗余。

输入样例1：

1
2
3
4 2
1 2
4 3

输出样例1：

1
2

输入样例2：

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

输出样例2：

1
1

Code Size Limit

16 KB

Time Limit

400 ms

Memory Limit

64 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
int que[1007];
int fro=0,rear=0;
void push(int a){
    que[rear++]=a;
}
int pop(){
    return que[fro++];
}
void bfs(MGraph&G,int a){
    push(a);
    visited[a]=1;
    while(fro!=rear){
        int b=pop();
        for(int i=1;i<=G.vexnum;i++){
            int x=G.arcs[b][i];
            if(x==1&&!visited[i]){
                visited[i]=1;
                push(i);
            }
        }
    }
}
void CreateMGraph(MGraph &G){
    scanf("%d%d",&G.vexnum,&G.arcnum);
    for(int i=0;i<G.arcnum;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        G.arcs[x][y]=1;
        G.arcs[y][x]=1;
    }
} /* 读入顶点数、边数，以及各条边，创建图 G 的邻接矩阵存储表示 */
int countCC(MGraph G){
    int cnt=0;
    for(int i=0;i<MaxVertexNum+1;i++){
        visited[i]=0;
    }
    for(int i=1;i<=G.vexnum;i++){
        if(!visited[i]){
            cnt++;
            bfs(G,i);
        }
    }
    return cnt;
} /* 已知无向图 G 采用邻接矩阵表示，函数值返回其连通分量个数 */

3-3(funx) Is Topological Order

Write a program to test if a give sequence Seq is a topological order of a given graph Graph.

Format of functions:

1
bool IsTopSeq( LGraph Graph, Vertex Seq[] );

where LGraph is defined as the following:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct AdjVNode *PtrToAdjVNode; 
struct AdjVNode{
    Vertex AdjV;
    PtrToAdjVNode Next;
};

typedef struct Vnode{
    PtrToAdjVNode FirstEdge;
} AdjList[MaxVertexNum];

typedef struct GNode *PtrToGNode;
struct GNode{  
    int Nv;
    int Ne;
    AdjList G;
};
typedef PtrToGNode LGraph;

The function IsTopSeq must return true if Seq does correspond to a topological order; otherwise return false.

Note: Although the vertices are numbered from 1 to MaxVertexNum, they are indexed from 0 in the LGraph structure.

Sample program of judge:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <stdio.h>
#include <stdlib.h>

typedef enum {false, true} bool;
#define MaxVertexNum 10  /* maximum number of vertices */
typedef int Vertex;      /* vertices are numbered from 1 to MaxVertexNum */

typedef struct AdjVNode *PtrToAdjVNode; 
struct AdjVNode{
    Vertex AdjV;
    PtrToAdjVNode Next;
};

typedef struct Vnode{
    PtrToAdjVNode FirstEdge;
} AdjList[MaxVertexNum];

typedef struct GNode *PtrToGNode;
struct GNode{  
    int Nv;
    int Ne;
    AdjList G;
};
typedef PtrToGNode LGraph;

LGraph ReadG(); /* details omitted */

bool IsTopSeq( LGraph Graph, Vertex Seq[] );

int main()
{
    int i, j, N;
    Vertex Seq[MaxVertexNum];
    LGraph G = ReadG();
    scanf("%d", &N);
    for (i=0; i<N; i++) {
        for (j=0; j<G->Nv; j++)
            scanf("%d", &Seq[j]);
        if ( IsTopSeq(G, Seq)==true ) printf("yes\n");
        else printf("no\n");
    }

    return 0;
}

/* Your function will be put here */

Sample Input (for the graph shown in the figure):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
6 8
1 2
1 3
5 2
5 4
2 3
2 6
3 4
6 4
5
1 5 2 3 6 4
5 1 2 6 3 4
5 1 2 3 6 4
5 2 1 6 3 4
1 2 3 4 5 6

Sample Output:

1
2
3
4
5
yes
yes
yes
no
no

Code Size Limit

16 KB

Time Limit

400 ms

Memory Limit

64 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int in[MaxVertexNum];
bool IsTopSeq( LGraph Graph, Vertex Seq[] ){
    for(int i=0;i<=MaxVertexNum;i++){
        in[i]=0;
    }
    for(int i=0;i<Graph->Nv;i++){
        for(PtrToAdjVNode j=Graph->G[i].FirstEdge;j;j=j->Next){
            in[j->AdjV]++;
        }
    }
//    for(int i=0;i<Graph->Nv;i++){
//        printf("%d ",in[i]);
//    }
    bool fl=true;
    for(int i=0;i<Graph->Nv;i++){
        int temp=Seq[i]-1;
        if(in[temp]==0){
            for(PtrToAdjVNode j=Graph->G[temp].FirstEdge;j;j=j->Next){
                in[j->AdjV]--;
            }
        }
        else {
            fl=false;
            break;
        }
    }
    return fl;
}

3-1 畅通工程之最低成本建设问题

某地区经过对城镇交通状况的调查，得到现有城镇间快速道路的统计数据，并提出“畅通工程”的目标：使整个地区任何两个城镇间都可以实现快速交通（但不一定有直接的快速道路相连，只要互相间接通过快速路可达即可）。现得到城镇道路统计表，表中列出了有可能建设成快速路的若干条道路的成本，求畅通工程需要的最低成本。

输入格式:

输入的第一行给出城镇数目N (1<N≤1000)和候选道路数目M≤3N；随后的M行，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号（从1编号到N）以及该道路改建的预算成本。

输出格式:

输出畅通工程需要的最低成本。如果输入数据不足以保证畅通，则输出“Impossible”。

输入样例1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3

输出样例1:

1
12

输入样例2:

1
2
3
4
5
5 4
1 2 1
2 3 2
3 1 3
4 5 4

输出样例2:

1
Impossible

Code Size Limit

16 KB

Time Limit

400 ms

Memory Limit

64 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
const int maxn=1007;
struct node{
    int u,v,w;
    node(int u,int v,int w):u(u),v(v),w(w){};
};
vector<node> E;
int n,m;
bool cmp(node &a,node &b){
    return a.w<b.w;
}
int f[maxn];
void init(){
    for(int i=0;i<maxn;i++){
        f[i]=i;
    }
}
int find(int a){
    if(f[a]==a) return a;
    else return f[a]=find(f[a]);
}
void merge(int a,int b){
    int temp=find(a);
    f[temp]=find(b);
}
bool check(int a,int b){
    return find(a)==find(b);
}
void kruskal(){
    init();
    int cnt=0;
    int ans=0;
    sort(E.begin(),E.end(),cmp);
    for(int i=0;i<m;i++){
        if(!check(E[i].u,E[i].v)){
            merge(E[i].u,E[i].v);
            cnt++;ans+=E[i].w;
        }
    }
    if(cnt<n-1) cout<<"Impossible"<<endl;
    else cout<<ans<<endl;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        E.emplace_back(x,y,z);
    }
    kruskal();
}

3-2 How Long Does It Take

Given the relations of all the activities of a project, you are supposed to find the earliest completion time of the project.

Input Specification:

Each input file contains one test case. Each case starts with a line containing two positive integers N (≤100), the number of activity check points (hence it is assumed that the check points are numbered from 0 to N−1), and M, the number of activities. Then M lines follow, each gives the description of an activity. For the i-th activity, three non-negative numbers are given: S[i], E[i], and L[i], where S[i] is the index of the starting check point, E[i] of the ending check point, and L[i] the lasting time of the activity. The numbers in a line are separated by a space.

Output Specification:

For each test case, if the scheduling is possible, print in a line its earliest completion time; or simply output “Impossible”.

Sample Input 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
9 12
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
5 4 0
4 6 9
4 7 7
5 7 4
6 8 2
7 8 4

Sample Output 1:

1
18

Sample Input 2:

1
2
3
4
5
6
4 5
0 1 1
0 2 2
2 1 3
1 3 4
3 2 5

Sample Output 2:

1
Impossible

Code Size Limit

16 KB

Time Limit

400 ms

Memory Limit

64 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
using namespace std;

const int maxn=107;
const int inf=0x3f3f3f3f;
int n,m;
struct node{
    int to,w;
    node(int to,int w):to(to),w(w){};
};
vector<node> fro[maxn],to[maxn];
int in[maxn];
bool vis[maxn];
queue<int>que;
vector<int>tpo1,tpo2;
int ve[maxn],vl[maxn];
void init(){
    memset(ve,0,sizeof(ve));
    memset(vl,inf,sizeof(vl));
}
void tpo(){
    int cnt=0,ans=0;
    init();
    for(int i=0;i<n;i++){
        if(!in[i]){
            que.push(i);
            vis[i]=true;
            cnt++;
        }
    }
    while(!que.empty()){
        int temp=que.front();
        que.pop();
        tpo1.push_back(temp);
        for(int i=0;i<fro[temp].size();i++){
            int t=fro[temp][i].to;
            ve[t]=max(ve[t],ve[temp]+fro[temp][i].w);
            ans=(ans,ve[t]);
            in[t]--;
            if(in[t]==0&&!vis[t]){
                que.push(t);
                vis[t]=true;
                cnt++;
            }
        }
    }
    if(cnt!=n){
        cout<<"Impossible";
    }
    else cout<<ans;
}


//void critical_path(){
//    init();
//    int ans=0;
//    for(int i=0;i<tpo1.size();i++){
//        int temp=tpo1[i];
//        for(int j=0;j<fro[temp].size();j++){
//            if(ve[fro[temp][j].to]<ve[temp]+fro[temp][j].w){
//                ve[fro[temp][j].to]=ve[temp]+fro[temp][j].w;
//            }
//        }
//    }
//    for(int i=0;i<n;i++){
//        vl[i]=ve[i];
//    }
//    for(int i=0;i<tpo2.size();i++){
//        int temp=tpo2[i];
//        for(int j=0;j<to[temp].size();j++){
//            if(vl[temp]-to[temp][j].w<vl[to[temp][j].to]){
//                vl[to[temp][j].to]=vl[temp]-to[temp][j].w;
//            }
//        }
//    }
//    for(int i=0;i<n;i++){
//        for(int j=0;j<fro[i].size();j++){
//            int e=ve[i];
//            int l=vl[fro[i][j].to]-fro[i][j].w;
//            if(e==l){//突然发现，也许我们的目的根本不是。。。
//                cout<<i<<' '<<fro[i][j].to<<' '<<fro[i][j].w<<endl;
//            }
//        }
//    }
//}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        fro[x].emplace_back(y,z);
        to[y].emplace_back(x,z);
        in[y]++;
    }
    tpo();
//    critical_path();
}

3-3 Harry Potter’s Exam

In Professor McGonagall’s class of Transfiguration, Harry Potter is learning how to transform one object into another by some spells. He has learnt that, to turn a cat into a mouse one can say docamo! To reverse the effect, simply say decamo! Formally speaking, the transfiguration spell to transform between object A and object B is said to be S if there are two spells, doS and deS, to turn A into B and vice versa, respectively.

In some cases, short-cut spells are defined to make transfiguration easier. For example, suppose that the spell to transform a cat to a mouse is docamo, and that to transform a mouse into a fatmouse is dofamo, then to turn a cat into a fatmouse one may say docamodofamo! Or if a shot-cut spell is defined to be cafam, one may get the same effect by saying docafam!

Time is passing by quickly and the Final Exam is coming. By the end of the transfiguration exam, students will be requested to show Professor McGonagall several objects transformed from the initial objects they bring to the classroom. Each of them is allowed to bring 1 object only.

Now Harry is coming to you for help: he needs a program to select the object he must take to the exam, so that the maximum length of any spell he has to say will be minimized. For example, if cat, mouse, and fatmouse are the only three objects involved in the exam, then mouse is the one that Harry should take, since it will take a 6-letter spell to turn a mouse into either a cat or a fatmouse. Cat is not a good choice since it will take at least a 7-letter spell to turn it into a fatmouse. And for the same reason Harry must not take a fatmouse.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive integers N (≤100) and M, which are the total number of objects involved in the exam and the number of spells to be tested, respectively. For the sake of simplicity, the objects are numbered from 1 to N. Then M lines follow, each contains 3 integers, separated by a space: the numbers of two objects, and the length of the spell to transform between them.

Output Specification:

For each test case, print in one line the number of the object which Harry must take to the exam, and the maximum length of the spell he may have to say. The numbers must be separated by a space.

If it is impossible to complete all the transfigurations by taking one object only, simply output 0. If the solution is not unique, output the one with the smallest number.

Sample Input:

1
2
3
4
5
6
7
8
9
10
11
12
6 11
3 4 70
1 2 1
5 4 50
2 6 50
5 6 60
1 3 70
4 6 60
3 6 80
5 1 100
2 4 60
5 2 80

Sample Output:

1
4 70

Code Size Limit

16 KB

Time Limit

400 ms

Memory Limit

64 MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//某天梯赛模拟，故copy
#include<bits/stdc++.h>
using namespace std;
const int maxn=307;
const int inf=0x3f3f3f3f;
int n,m;
int f[maxn][maxn];
struct lenlen{
    int point,len,fl;
}len[maxn];
void init(){
    for(int i=0;i<=n;i++){
        len[i].fl=0;
        for(int j=0;j<=n;j++){
            f[i][j]=inf;
        }
    }
}
bool cmp(lenlen &a,lenlen &b){
    if(a.fl||b.fl){
        return a.fl<b.fl;
    }
    if(a.len==b.len) return a.point<b.point;
    return a.len<b.len;
}
int main(){
    cin>>n>>m;
    init();
    for(int i=0;i<m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        f[x][y]=z;
        f[y][x]=z;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                if(f[j][i]+f[i][k]<f[j][k]){
                    f[j][k]=f[j][i]+f[i][k];
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(j!=i) {
                len[i].point = i;
                if (f[i][j] != inf) len[i].len = max(len[i].len, f[i][j]);
                if (f[i][j] == inf) len[i].fl = 1;
            }
        }
    }
    sort(len+1,len+1+n,cmp);
    if(len[1].fl) cout<<0;
    else{
        cout<<len[1].point<<' '<<len[1].len;
    }

}
STERNE

STERNE

SDUer，大一入门，大二入土，大三老东西！

63
1
20
TOC
  1. 1. 1.tree
    1. 1.1. 1-1(funx) 二叉树的遍历
    2. 1.2. 1-1 Tree Traversals Again
    3. 1.3. 1-2 还原二叉树
    4. 1.4. *前中后序遍历建树模板
    5. 1.5. 1-3 玩转二叉树
    6. 1.6. 1-4 小字辈
    7. 1.7. 1-5 列出叶节点
    8. 1.8. 1-6 修理牧场
    9. 1.9. 1-7 ZigZagging on a Tree
    10. 1.10. 1-8 Path of Equal Weight
    11. 1.11. 1-9 哈夫曼编码
  2. 2. 2.sort
    1. 2.1. 2-1(funx) Iterative Mergesort
    2. 2.2. 2-2(funx) The Kth Largest in BST
    3. 2.3. 2-3(funx) Rank a Linked List (II)
    4. 2.4. 2-1 两个有序序列的中位数
    5. 2.5. 2-2 词频统计
    6. 2.6. 2-3 符号配对
    7. 2.7. 2-4 列车调度
    8. 2.8. upper_bound&lower_bound
  3. 3. 3.graph
    1. 3.1. 3-1(funx) 邻接表存储图的广度优先遍历
    2. 3.2. 3-2(funx) 邻接矩阵表示及其遍历
    3. 3.3. 3-3(funx) Is Topological Order
    4. 3.4. 3-1 畅通工程之最低成本建设问题
    5. 3.5. 3-2 How Long Does It Take
    6. 3.6. 3-3 Harry Potter’s Exam
NOTICE

这里还什么都没有呢喵~

CATEGORYS
TAGS
ACM Arc CCPC HPC bot c cpp deeplearning games hexo java maths pyqt python qt recommends review sql srtp test