算法笔记_第九章

第九章上机训练

9(上机)

9.2

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;

//PAT A1020
//重建二叉树
//利用队列层序遍历,即BFS
int in[31],post[31]; //先序；中序；后序
int n;
struct node
{
    node *lchild;
    node *rchild;
    int data;
};

node* create(int postl,int postr,int inl,int inr)
{
    if(postl>postr) return NULL;
    node* root=new node;
    root->data=post[postr];
    int k;
    for(k=inl;k<=inr;k++){
        if(in[k]==post[postr]) break;
    }
    int numleft=k-inl;
    root->lchild=create(postl,postl+numleft-1,inl,k-1);
    root->rchild=create(postl+numleft,postr-1,k+1,inr);
    return root;
}

int num=0;

void BFS(node* root)
{
    queue<node*> q;
    q.push(root);
    while(!q.empty()){
        node* now=q.front();
        q.pop();
        printf("%d",now->data);
        num++;
        if(num<n) printf(" ");
        if(now->lchild!=NULL) q.push(now->lchild);
        if(now->rchild!=NULL) q.push(now->rchild);
    }
    return;
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&post[i]);
    for(int i=0;i<n;i++) scanf("%d",&in[i]);
    node* root=create(0,n-1,0,n-1);
    BFS(root);
    return 0;
}

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 <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;

//PAT A1086
int pre[31],in[31];
int n;
struct node
{
    node* lchild;
    node* rchild;
    int data;
};
node* create(int prel,int prer,int inl,int inr)
{
    if(prel>prer) return NULL;
    node* root=new node;
    root->data=pre[prel];
    int k;
    for(k=inl;k<=inr;k++){
        if(in[k]==pre[prel]) break;
    }
    int numleft=k-inl;
    root->lchild=create(prel+1,prel+numleft,inl,k-1);
    root->rchild=create(prel+numleft+1,prer,k+1,inr);
    return root;
}

int num=0;
void postorder(node* root)
{
    if(root==NULL) return;
    postorder(root->lchild);
    postorder(root->rchild);
    printf("%d",root->data);
    num++;
    if(num<n) printf(" ");
    return;
}

int main()
{
    scanf("%d",&n);
    //getchar();
    //string str;
    char str[5];
    stack<int> st;
    int temp;
    int preindex=0;
    int inindex=0;
    for(int i=0;i<2*n;i++){
        //cin>>str;
        //cout<<str<<endl;
        scanf("%s",str);
        if(strcmp(str,"Push")==0){
            scanf("%d",&temp);
            //printf("%d\n",temp);
            st.push(temp);
            pre[preindex++]=temp;
        }
        else{
            in[inindex++]=st.top();
            st.pop();
        }
    }
    node* root=create(0,n-1,0,n-1);
    postorder(root);
    return 0;
}

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;

//PAT A1102
//这题我直接模仿书上的写的，自己思考走了岔路
const int maxn=110;
struct node
{
    int lchild,rchild;
}Node[maxn];
bool notRoot[maxn]={false};
int n,num=0;

void print(int id)
{
    printf("%d",id);
    num++;
    if(num<n) printf(" ");
    else printf("\n");
    return;
}

void inOrder(int root)
{
    if(root==-1) return;
    inOrder(Node[root].lchild);
    print(root);
    inOrder(Node[root].rchild);
    return;
}

void BFS(int root)
{
    queue<int> q;
    q.push(root);
    while(!q.empty()){
        int now=q.front();
        q.pop();
        print(now);
        if(Node[now].lchild!=-1) q.push(Node[now].lchild);
        if(Node[now].rchild!=-1) q.push(Node[now].rchild);
    }
}

void postOrder(int root)
{
    if(root==-1) return;
    postOrder(Node[root].lchild);
    postOrder(Node[root].rchild);
    swap(Node[root].lchild,Node[root].rchild);
    return;
}

int strToNum(char c)
{
    if(c=='-') return -1;
    else{
        notRoot[c-'0']=true;
        return c-'0';
    }
}

int findRoot()
{
    for(int i=0;i<n;i++){
        if(notRoot[i]==false)
            return i;
    }
}

int main()
{
    char lchild,rchild;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%*c%c %c",&lchild,&rchild);
        Node[i].lchild=strToNum(lchild);
        Node[i].rchild=strToNum(rchild);
    }
    int root=findRoot();
    postOrder(root);
    BFS(root);
    num=0;
    inOrder(root);
    return 0;
}

9.3

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;

//PAT A1079
const int maxn=100010;
struct node
{
    int data=-1;
    vector<int> child;
}Node[maxn];
bool HashTable[maxn]={true};  //是否为根结点
int n;
double p,r,ans=0.0;
void DFS(int index,int depth)
{
    if(Node[index].child.size()==0){
        ans+=Node[index].data*pow(1+r,depth);
        return;
    }
    for(int i=0;i<Node[index].child.size();i++){
        DFS(Node[index].child[i],depth+1);
    }
}

int main()
{
    scanf("%d%lf%lf",&n,&p,&r);
    r/=100;
    int sum,root;
    for(int i=0;i<n;i++){
        scanf("%d",&sum);
        if(sum!=0){
            int temp;
            while(sum--){
                scanf("%d",&temp);
                Node[i].child.push_back(temp);
                HashTable[temp]=false;
            }
        }
        else{
            int temp;
            scanf("%d",&temp);  //weight
            Node[i].data=temp;
        }
    }
    //find root
    for(int i=0;i<n;i++){
        if(HashTable[i]==true){
            root=i;
            break;
        }
    }
    DFS(root,0);
    printf("%.1f\n",p*ans);
    return 0;
}

/*
//PAT A1090
const int maxn=100010;
vector<int> child[maxn];
double p,r;
int maxdepth=0,num=0;

void DFS(int index,int depth)
{
    if(child[index].size()==0){
        if(depth>maxdepth){
            maxdepth=depth;
            num=1;
        }
        else if(depth==maxdepth)
            num++;
        return;
    }
    for(int i=0;i<child[index].size();i++){
        DFS(child[index][i],depth+1);
    }
}

int main()
{
    int n;
    int temp,root;
    scanf("%d%lf%lf",&n,&p,&r);
    r/=100;
    for(int i=0;i<n;i++){
        scanf("%d",&temp);
        if(temp!=-1){
            child[temp].push_back(i);
        }
        else root=i;
    }
    DFS(root,0);
    printf("%.2f %d\n",p*pow(1+r,maxdepth),num);
    return 0;
}
*/

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;

//PAT A1094
const int maxn=101;
struct node
{
    int num;  //num of children
    vector<int> child;
    int layer=1;
}Node[maxn];

bool HashTable[maxn]; //is root or not
int maxsum=0;
int maxge=0;
int level[maxn]={0};
void BFS(int index)
{
    queue<node> q;
    q.push(Node[index]);
    while(!q.empty()){
        node now=q.front();
        q.pop();
        for(int i=0;i<now.child.size();i++){
            Node[now.child[i]].layer=now.layer+1;
            q.push(Node[now.child[i]]);
            level[now.layer+1]++;
        }
    }
    return;
}

int main()
{
    int n,m,k,id;
    scanf("%d%d",&n,&m);
    if(n==1){
        printf("1 1\n");
        return 0;
    }
    for(int i=1;i<=n;i++) HashTable[i]=true;
    while(m--){
        scanf("%d%d",&id,&k);
        //printf("%d %d\n",id,k);
        Node[id].num=k;
        while(k--){
            int temp;
            scanf("%d",&temp);
            //printf("%d\n",temp);
            Node[id].child.push_back(temp);
            HashTable[temp]=false;
        }
    }
    /*
    for(int i=1;i<=n;i++){
        for(int j=0;j<Node[i].num;j++){
            printf("%d ",Node[i].child[j]);
        }
        printf("\n");
    }
    */
    //find root
    int root;
    for(int i=1;i<=n;i++){
        if(HashTable[i]==true){
            root=i;
            break;
        }
    }
    BFS(root);
    for(int i=1;i<=n;i++){
        if(maxsum<level[i]){
            maxsum=level[i];
            maxge=i;
        }
    }
    printf("%d %d\n",maxsum,maxge);
    return 0;
}

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;

//PAT A1106
const int maxn=100010;
struct node
{
    int data=-1;
    vector<int> child;
}Node[maxn];
bool HashTable[maxn];  //是否为根结点
int n=0,num=0;
double p,r,ans=1e12;
void DFS(int index,int depth)
{
    if(Node[index].child.size()==0){
        double price = p*pow(1+r,depth);
        if(price<ans){
            ans=price;
            num=1;
        }
        else if(price==ans){
            num++;
        }
        return;
    }
    for(int i=0;i<Node[index].child.size();i++){
        DFS(Node[index].child[i],depth+1);
    }
}

int main()
{
    scanf("%d%lf%lf",&n,&p,&r);
    for(int i=0;i<n;i++) HashTable[i]=true;
    r/=100;
    int sum,root;
    for(int i=0;i<n;i++){
        scanf("%d",&sum);
        if(sum!=0){
            int temp;
            while(sum--){
                scanf("%d",&temp);
                Node[i].child.push_back(temp);
                HashTable[temp]=false;
            }
        }
    }
    //find root
    for(int i=0;i<n;i++){
        if(HashTable[i]==true){
            root=i;
            break;
        }
    }
    DFS(root,0);
    printf("%.4f %d\n",ans,num);
    return 0;
}

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;

//PAT A1053
const int MAXN=110;

struct node
{
    int weight;
    vector<int> child;
}Node[MAXN];

bool cmp(int a,int b)
{
    return Node[a].weight>Node[b].weight;
}

int n,m,s;
int path[MAXN];
void DFS(int index,int numNode,int sum)
{
    if(sum>s) return;
    if(sum==s){
        if(Node[index].child.size()!=0) return;
        for(int i=0;i<numNode;i++){
            printf("%d",Node[path[i]].weight);
            if(i<numNode-1) printf(" ");
            else printf("\n");
        }
        return;
    }
    for(int i=0;i<Node[index].child.size();i++){
        int child = Node[index].child[i];
        path[numNode]=child;
        DFS(child,numNode+1,sum+Node[child].weight);
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=0;i<n;i++){
        scanf("%d",&Node[i].weight);
    }
    int id,k,child;
    for(int i=0;i<m;i++){
        scanf("%d%d",&id,&k);
        for(int j=0;j<k;j++){
            scanf("%d",&child);
            Node[id].child.push_back(child);
        }
        sort(Node[id].child.begin(),Node[id].child.end(),cmp);
    }
    path[0]=0;
    DFS(0,1,Node[0].weight);
    return 0;
}

/*
//PAT A1004
const int N=110;
vector<int> G[N];
int leaf[N]={0};
int max_h=1;

void DFS(int index,int h)
{
    max_h = max(h,max_h);
    if(G[index].size()==0){
        leaf[h]++;
        return;
    }
    for(int i=0;i<G[index].size();i++){
        DFS(G[index][i],h+1);
    }
}

int main()
{
    int n,m,parent,child,k;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&parent,&k);
        for(int j=0;j<k;j++){
            scanf("%d",&child);
            G[parent].push_back(child);
        }
    }
    DFS(1,1);
    printf("%d",leaf[1]);
    for(int i=2;i<=max_h;i++)
        printf(" %d",leaf[i]);
    return 0;
}
*/

9.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
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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;

//PAT A1043
//第一次写二叉排序，借鉴一下模板
struct node
{
    node* rchild;
    node* lchild;
    int data;
};

vector<int> origin,pre,preM,post,postM;

void insert(node* &root,int data)
{
    if(root==NULL){
        root=new node;
        root->data=data;
        root->lchild=root->rchild=NULL;
        return;
    }
    if(data<root->data) insert(root->lchild,data);
    else insert(root->rchild,data);
}

void preOrder(node* root,vector<int>& vi)
{
    if(root==NULL) return;
    vi.push_back(root->data);
    preOrder(root->lchild,vi);
    preOrder(root->rchild,vi);
}

void preOrderMirror(node* root,vector<int>& vi)
{
    if(root==NULL) return;
    vi.push_back(root->data);
    preOrderMirror(root->rchild,vi);
    preOrderMirror(root->lchild,vi);
}

void postOrder(node* root,vector<int>& vi)
{
    if(root==NULL) return;
    postOrder(root->lchild,vi);
    postOrder(root->rchild,vi);
    vi.push_back(root->data);
}

void postOrderMirror(node* root,vector<int>& vi)
{
    if(root==NULL) return;
    postOrderMirror(root->rchild,vi);
    postOrderMirror(root->lchild,vi);
    vi.push_back(root->data);
}

int main()
{
    int n,temp;
    node* root=NULL;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&temp);
        origin.push_back(temp);
        insert(root,temp);
    }
    preOrder(root,pre);
    preOrderMirror(root,preM);
    postOrder(root,post);
    postOrderMirror(root,postM);
    if(origin==pre){
        printf("YES\n");
        for(int i=0;i<post.size();i++){
            printf("%d",post[i]);
            if(i<post.size()-1) printf(" ");
        }
    }
    else if(origin==preM){
        printf("YES\n");
        for(int i=0;i<postM.size();i++){
            printf("%d",postM[i]);
            if(i<postM.size()-1) printf(" ");
        }
    }
    else printf("NO\n");
    return 0;
}

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;

//PAT A1064
//这题要想到二叉排序树与中序遍历的关系，再结合数组才能想到
//先跟着答案理一下思路
const int maxn=1010;
int number[maxn];
int CBT[maxn];
int n;
int id=0;

void inOrder(int root)
{
    if(root>n) return;
    inOrder(root*2);
    CBT[root]=number[id++];
    inOrder(root*2+1);
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&number[i]);
    }
    sort(number,number+n);
    inOrder(1);
    for(int i=1;i<=n;i++){
        printf("%d",CBT[i]);
        if(i<n) printf(" ");
    }
    return 0;
}

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;

//PAT A1099
const int maxn=110;
struct node
{
    int data;
    int lchild,rchild;
}Node[maxn];

int n;
int in[maxn];
int num=0;

void inOrder(int root)
{
    if(root==-1) return;
    inOrder(Node[root].lchild);
    Node[root].data=in[num++];
    inOrder(Node[root].rchild);
}

void BFS(int root)
{
    queue<int> q;
    q.push(root);
    num=0;
    while(!q.empty()){
        int now=q.front();
        q.pop();
        printf("%d",Node[now].data);
        num++;
        if(num<n) printf(" ");
        if(Node[now].lchild!=-1) q.push(Node[now].lchild);
        if(Node[now].rchild!=-1) q.push(Node[now].rchild);
    }
}

int main()
{
    int lchild,rchild;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&lchild,&rchild);
        Node[i].lchild=lchild;
        Node[i].rchild=rchild;
    }
    for(int i=0;i<n;i++){
        scanf("%d",&in[i]);
    }
    sort(in,in+n);
    inOrder(0);
    BFS(0);
    return 0;
}

9.5

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;

//PAT A1066
//熟记相关AVL模板
struct node
{
    int data;
    int height;
    node *lchild,*rchild;
}*root;

node* newNode(int data)
{
    node* Node=new node;
    Node->data=data;
    Node->height=1;
    Node->lchild=Node->rchild=NULL;
    return Node;
}

int getHeight(node* root)
{
    if(root==NULL) return 0;
    return root->height;
}

void updateHeight(node* root)
{
    root->height=max(getHeight(root->lchild),getHeight(root->rchild))+1;
}

int getBalance(node* root)
{
    return getHeight(root->lchild)-getHeight(root->rchild);
}

//左旋
void L(node* &root)
{
    node* temp=root->rchild;
    root->rchild=temp->lchild;
    temp->lchild=root;
    updateHeight(root);
    updateHeight(temp);
    root=temp;
}

//右旋
void R(node* &root)
{
    node* temp=root->lchild;
    root->lchild=temp->rchild;
    temp->rchild=root;
    updateHeight(root);
    updateHeight(temp);
    root=temp;
}

void insert(node* &root,int data)
{
    if(root==NULL){
        root=newNode(data);
        return;
    }
    if(data<root->data){
        insert(root->lchild,data);
        updateHeight(root);
        if(getBalance(root)==2){
            if(getBalance(root->lchild)==1) R(root);
            else if(getBalance(root->lchild)==-1){
                L(root->lchild);
                R(root);
            }
        }
    }
    else{
        insert(root->rchild,data);
        updateHeight(root);
        if(getBalance(root)==-2){
            if(getBalance(root->rchild)==-1) L(root);
            else if(getBalance(root->rchild)==1){
                R(root->rchild);
                L(root);
            }
        }
    }
}

int main()
{
    int n,data;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&data);
        insert(root,data);
    }
    printf("%d\n",root->data);
    return 0;
}

9.6

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;

//PAT A1107
const int maxn=1010;
int father[maxn];
int course[maxn]={0};
int isRoot[maxn]={0};

int findFather(int x)
{
    int root=x;
    //寻找x的根节点，并存放在root
    while(root!=father[root])
        root=father[root];
    //路径压缩
    while(x!=father[x]){
        int temp=x;
        x = father[x];
        father[temp] = root;
    }
    return root;
}

void Union(int a,int b)
{
    int faA = findFather(a);
    int faB = findFather(b);
    if(faA!=faB) father[faA]=faB;
    return;
}

void init(int n)
{
    for(int i=1;i<=n;i++){
        father[i]=i;
    }
    return;
}

bool cmp(int a,int b)
{
    return a>b;
}

int main()
{
    int n,k,h;
    scanf("%d",&n);
    init(n);
    for(int i=1;i<=n;i++){
        scanf("%d:",&k);
        for(int j=0;j<k;j++){
            scanf("%d",&h);
            if(course[h]==0)
                course[h]=i;
            Union(i,findFather(course[h]));
        }
    }
    for(int i=1;i<=n;i++)
        isRoot[findFather(i)]++;
    int ans=0;
    for(int i=1;i<=n;i++){
        if(isRoot[i]!=0)
            ans++;
    }
    printf("%d\n",ans);
    sort(isRoot+1,isRoot+n+1,cmp);
    for(int i=1;i<=ans;i++){
        printf("%d",isRoot[i]);
        if(i<ans) printf(" ");
    }
    return 0;
}

9.7

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;

//PAT A1098
//自己写的只有23分，测试点2不通过
const int N=110;
int changed[N];
int heap[N],insert2[N];

bool same(int a[],int b[],int n)
{
    for(int i=1;i<=n;i++){
        if(a[i]!=b[i]){
            return false;
        }
    }
    return true;
}

void show(int a[],int n)
{
    for(int i=1;i<=n;i++){
        printf("%d",a[i]);
        if(i<n) printf(" ");
    }
    return;
}

bool insert_sort(int insert2[],int changed[],int n)
{
    bool flag=false;
    //insert sort需要n-1次交换
    for(int i=1;i<=n-1;i++){
        if(i!=1&&same(insert2,changed,n)) flag=true;
        sort(insert2,insert2+i+1);
        if(flag==true) return true;
    }
    return false;
}

void downjust(int low,int high)
{
    int i=low,j=i*2;
    while(j<=high){
        if(j+1<=high&&heap[j+1]>heap[j]) j=j+1;
        if(heap[j]>heap[i]){
            swap(heap[j],heap[i]);
            i=j;
            j=i*2;
        }
        else{
            break;
        }
    }
    return;
}

void heap_sort(int heap[],int n)
{
    bool flag=false;
    //build heap
    for(int i=n/2;i>=1;i--){
        downjust(i,n);
    }
    for(int i=n;i>1;i--){
        if(i!=n&&same(heap,changed,n)) flag=true;
        swap(heap[1],heap[i]);
        downjust(1,i-1);
        if(flag==true){
            show(heap,n);
            return;
        }
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&heap[i]);
        insert2[i]=heap[i];
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&changed[i]);
    }
    //insert sort
    if(insert_sort(insert2,changed,n)){
        printf("Insertion Sort\n");
        show(insert2,n);
    }
    //heap sort
    else{
        printf("Heap Sort\n");
        heap_sort(heap,n);
    }
    return 0;
}

本文作者： xiaoyuyu
本文链接： http://woaixiaoyuyu.github.io/2020/02/15/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E7%AC%AC%E4%B9%9D%E7%AB%A0/
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！
赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码
本站总访问量次 本站访客数人

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

记录成长的点滴<br><br>涉猎颇广的信息技术爱好者<br>希望未来的xiaoyuyu<br>可以成为优秀的工程师