算法笔记_第七章

第七章书上的题目+上机训练

7(书)

7.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
#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 A1052
struct Node
{
    int key;
    int next;
    int address;
    bool flag=false;
}node[100001];

bool cmp(Node a,Node b)
{
    if(a.flag==false||b.flag==false) return a.flag>b.flag;
    else return a.key<b.key;
}

int main()
{
    int n,head;
    scanf("%d%d",&n,&head);
    int address,next,key;
    for(int i=0;i<n;i++){
        scanf("%d%d%d",&address,&key,&next);
        node[address].address=address;
        node[address].next=next;
        node[address].key=key;
    }
    int count=0;
    int p=head;
    while(p!=-1){
        node[p].flag=true;
        count++;
        p=node[p].next;
    }
    if(count==0) printf("0 -1");
    else{
        sort(node,node+100001,cmp);
        printf("%d %05d\n",count,node[0].address);
        for(int i=0;i<count;i++){
            if(i!=count-1)
                printf("%05d %d %05d\n",node[i].address,node[i].key,node[i+1].address);
            else
                printf("%05d %d -1\n",node[i].address,node[i].key);
        }
    }
    return 0;
}

/*
//PAT A1032
struct node
{
    char data;
    int next;
    bool flag=false;
}node[100001];

int main()
{
    int address1,address2,n;
    scanf("%d%d%d",&address1,&address2,&n);
    int address,next;
    char data;
    for(int i=0;i<n;i++){
        scanf("%d %c %d",&address,&data,&next);
        node[address].data=data;
        node[address].next=next;
    }
    int p;
    for(p=address1;p!=-1;p=node[p].next) node[p].flag=true;
    for(p=address2;p!=-1;p=node[p].next) if(node[p].flag==true) break;
    if(p!=-1) printf("%05d",p);
    else printf("-1");
    return 0;
}
*/

7(上机)

7.1

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 <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>

using namespace std;

//PAT A1051
stack<int> now;
int a[1001];

int main()
{
    int m,n,k;
    scanf("%d%d%d",&m,&n,&k);
    while(k--){
        while(!now.empty()) now.pop();
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        bool flag=true;
        int out=1;
        for(int i=1;i<=n;i++){
            now.push(i);
            if(now.size()>m){
                flag=false;
                break;
            }
            while(!now.empty()&&now.top()==a[out]){
                now.pop();
                out++;
            }
        }
        if(now.empty()==true&&flag==true) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

7.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
#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>

using namespace std;

//PAT A1051
stack<int> now;
int a[1001];

int main()
{
    int m,n,k;
    scanf("%d%d%d",&m,&n,&k);
    while(k--){
        while(!now.empty()) now.pop();
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        bool flag=true;
        int out=1;
        for(int i=1;i<=n;i++){
            now.push(i);
            if(now.size()>m){
                flag=false;
                break;
            }
            while(!now.empty()&&now.top()==a[out]){
                now.pop();
                out++;
            }
        }
        if(now.empty()==true&&flag==true) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

7.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
#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 B1025
struct Node
{
    int address,next,data;
    int order=100002;
}node[100001];

bool cmp(Node a,Node b)
{
    return a.order<b.order;
}

int main()
{
    int head,n,k;
    int temp;
    scanf("%d%d%d",&head,&n,&k);
    while(n--){
        scanf("%d",&temp);
        scanf("%d%d",&node[temp].data,&node[temp].next);
        node[temp].address=temp;
    }
    int p=head;
    int count=0;
    while(p!=-1){
        node[p].order=++count;
        p=node[p].next;
    }
    sort(node,node+100001,cmp);
    n=count;
    for(int i=0;i<n/k;i++){
        for(int j=(i+1)*k-1;j>i*k;j--){
            printf("%05d %d %05d\n",node[j].address,node[j].data,node[j-1].address);
        }
        printf("%05d %d ",node[i*k].address,node[i*k].data);
        if(i<n/k-1) printf("%05d\n",node[(i+2)*k-1].address);
        else{
            if(n%k==0) printf("-1\n");
            else{
                printf("%05d\n",node[(i+1)*k].address);
                for(int i=n/k*k;i<n;i++){
                    printf("%05d %d ",node[i].address,node[i].data);
                    if(i<n-1) printf("%05d\n",node[i+1].address);
                    else printf("-1\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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#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 A1097
const int MAX=100001;

struct Node
{
    int key,address,next;
    int order=2*MAX;
}node[MAX];

bool cmp(Node a,Node b)
{
    return a.order<b.order;
}

bool HashTable[2*MAX]={0};

int main()
{
    int head,n;
    int address,key,next;
    scanf("%d%d",&head,&n);
    while(n--){
        scanf("%d %d %d",&address,&key,&next);
        node[address].address=address;
        node[address].next=next;
        node[address].key=key;
    }
    int count=0;
    int remove=0;
    int p=head;
    while(p!=-1){
        if(!HashTable[abs(node[p].key)]){
            HashTable[abs(node[p].key)]=true;
            node[p].order=++count;
        }
        else{
            node[p].order=MAX+remove++;
        }
        p=node[p].next;
    }
    sort(node,node+MAX,cmp);
    n=count+remove;
    for(int i=0;i<n;i++){
        if(i!=count-1&&i!=n-1){
            printf("%05d %d %05d\n",node[i].address,node[i].key,node[i+1].address);
        }
        else{
            printf("%05d %d -1\n",node[i].address,node[i].key);
        }
    }
    return 0;
}

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

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码
来发评论吧~
Powered By Valine
v1.5.2
本站总访问量43185次 本站访客数33984人