基础数据结构刷题记录

发表于 更新于 分类于 本文字数： 11k 阅读时长 ≈ 10 分钟
  • 栈
  • 队列
  • 链表
  • 并查集

洛谷P1449（栈和逆序表达式）

水题

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<cstdio>
#include<cstring>
#include<stack>
using namespace std;

int main()
{
    char str[10001];
    scanf("%s", str);
    int len = strlen(str);
    int num = 0;
    stack<int> s;
    for(int i = 0; i < len; ++i)
    {
        if(str[i] >= '0' && str[i] <= '9')
        {
            num *= 10;
            num += str[i] - '0';
        }
        else if(str[i] == '.')
        {
            s.push(num);
            num = 0;
        }
        else if(str[i] == '@')
        {
            printf("%d\n", s.top());
            s.pop();
        }
        else
        {
            int a = s.top();
            s.pop();
            int b = s.top();
            s.pop();
            if(str[i] == '-')
                s.push(b - a);
            else if(str[i] == '+')
                s.push(b + a);
            else if(str[i] == '*')
                s.push(b * a);
            else if(str[i] == '/')
                s.push(b / a);
        }
    }
    return 0;
}

洛谷P1739（栈）

水题

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
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;

int main()
{
    int flag = 1;
    stack<char> s;
    char str[300];
    scanf("%s", str);
    int len = strlen(str);
    for(int i = 0; i < len; ++i)
    {
        if(str[i] == '(')
            s.push(str[i]);
        if(str[i] == ')')
        {
            if(s.empty())
                flag = 0;
            else
                s.pop();
        }
    }
    if(!s.empty())
        flag = 0;
    if(flag)
        printf("YES\n");
    else
        printf("NO\n");
    return 0;
}

洛谷P1115（？）

分在洛谷的线性数据结构里，但我好像不是这么做的

  • ai表示第i个数，a[i]表示前i项和
  • ai……aj和最大的话，那么这段长度为a[j]-a[i]
  • 即a[i]最小的时候，以aj结尾的最长序列和可以一步算出
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
#include<cstdio>

const int MAX_N = 2e5 + 1;
const int INF = 1e9;

int a[MAX_N];

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
    {
        scanf("%d", &a[i]);
        a[i] = a[i] + a[i-1]; //储存前i项和
    }
    int min = 0;
    int ans = a[0];
    for(int i = 1; i < n; ++i)
    {
        min = min > a[i-1] ? a[i-1] : min;
        ans = ans < a[i] - min ? a[i] - min : ans;
    }
    printf("%d\n", ans);
    return 0;
}

洛谷P1160（双向链表）

简单题，初学可练手

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
#include<cstdio>
#include<cstdlib>

typedef struct Node
{
    int data;
    Node *left;
    Node *right;
} Node;

Node *book[100001]; //记录每个点的地址

Node *head = (Node *)malloc(sizeof(Node)); //头结点
Node *q = (Node *)malloc(sizeof(Node)); //第一个结点

Node *find(int num) //寻找结点
{
    if(book[num])
        return book[num];
    return NULL;
}

void insert(int num1, int d, int num2) //插入结点
{
    //在num1的左/右插入num2
    Node *p = find(num1);
    Node *t = (Node *)malloc(sizeof(Node));
    t->data = num2;
    if(!d && p->left == head)
    {
        t->left = head;
        t->right = p;
        head->right = t;
        p->left = t;
    }
    else if(!d)
    {
        t->left = p->left;
        t->right = p;
        p->left->right = t;
        p->left = t;
    }
    else if(d && p->right == NULL)
    {
        t->right = NULL;
        t->left = p;
        p->right = t;
    }
    else if(d)
    {
        t->right = p->right;
        t->left = p;
        p->right->left = t;
        p->right = t;
    }
    book[num2] = t;
}

void del(int num) //删除结点
{
    Node *p = find(num);
    if(!p)
        return;
    if(p->left ==NULL && p->right == NULL)
    {
        ;
    }
    else if(p->left == NULL)
    {
        p->right->left = NULL;
    }
    else if(p->right == NULL)
    {
        p->left->right = NULL;
    }
    else
    {
        p->left->right = p->right;
        p->right->left = p->left;
    }
    free(p);
    book[num] = NULL;
}

int main()
{
    for(int i = 0; i < 100001; ++i)
        book[i] = NULL;

    head->left = NULL;
    head->right = q;
    q->data = 1;
    q->left = head;
    q->right = NULL;
    book[1] = q;

    int n;
    scanf("%d", &n);
    for(int i = 2; i < n + 1; ++i)
    {
        int num1, num2, d;
        num2 = i;
        scanf("%d%d", &num1, &d);
        insert(num1, d, num2);
    }

    int m;
    scanf("%d", &m);
    for(int i = 0; i < m; ++i)
    {
        int num;
        scanf("%d", &num);
        del(num);
    }

    Node *p = head->right;
    while(p)
    {
        printf("%d ", p->data);
        p = p->right;
    }
    
    printf("\n");
    return 0;
}

洛谷P1996（单向链表）

初学练手的简单题

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<cstdio>
#include<cstdlib>
using namespace std;

typedef struct Node
{
    int data;
    struct Node * next;
} Node;

int n, m;
int size = 1;

Node *init()
{
    Node *q, *head;
    head = (Node *)malloc(sizeof(Node));
    head->data = 1;
    q = head;
    for(int i = 2; i <= n; ++i)
    {
        Node *p = (Node *)malloc(sizeof(Node));
        p->data = i;
        q->next = p;
        if(i == n)
            p->next = head;
        else
            q = p;
        size++;
    }
    return head;
}

void solve(Node *head)
{
    Node *q;
    Node *p = (Node *)malloc(sizeof(Node));
    p = head;
    while(size > 0)
    {
        for(int i = 1; i < m - 1; ++i)
        {
            q = p->next;
            p = q;
        }
            Node *t = q->next;
            q->next = q->next->next;
            printf("%d ", t->data);
            free(t);
            size--;
            if(size)
                p = q->next;
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    if(!n)
        return 0;
    else
    {
        Node *head = init();
        solve(head);
    }
    return 0;
}

洛谷P2661（图论+并查集，最小环问题）

简单题，但是要思考一下

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
//图论最小环问题, 并查集
#include<cstdio>
#include<algorithm>
using namespace std;

const int MAX_N = 2e5 + 2;

int par[MAX_N];
int d[MAX_N];//记录到根节点的长度

int n;
int ans = 2e9;

void init() //初始化
{
    for(int i = 0; i <= n; ++i)
    {
        par[i] = i;
        d[i] = 0;
    }
}

int find(int x) //查询根节点并更新距离
{
    if(x == par[x])
        return x;
    else
    {
        int last= par[x];
        par[x] = find(par[x]); //查找途中，把每个点都连向根节点
        d[x] += d[last];
    }
    return par[x];
}

bool same(int x, int y)
{
    return find(x) == find(y);
}

void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    if(x == y) return ;
    else
        par[x] = y; //x连到y上
}

void solve(int a, int b)
{
    int x = find(a);
    int y = find(b);
    if(x == y)
        ans = min(ans, d[a] + d[b] + 1); //环的长度为a到根节点的长度加b到根节点的长度加ab之间的1
    else
    {
        unite(x, y);
        d[a] = d[b] + 1;
    }
}

int main()
{
    scanf("%d", &n);
    init();
    for(int i = 1; i <= n; ++i)
    {
        int t;
        scanf("%d", &t);
        solve(i, t);
    }
    printf("%d\n", ans);
    return 0;
}

洛谷P1111（并查集求连通块数量）

简单题， 想到套模板即可

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
//连通块数量 = n - 1
#include<cstdio>
#include<algorithm>
using namespace std;

const int MAX_N = 1e5 + 1;

struct Node
{
    int a;
    int b;
    int n;
};

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

int par[MAX_N];
int rank1[MAX_N];

void init(int n)
{
    for(int i = 0; i < n; ++i)
    {
        par[i] = i;
        rank1[i] = 0;
    }
}

int find(int x)
{
    if(par[x] == x)
        return x;
    else
        return par[x] = find(par[x]);
}

void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    if(x == y) return ;

    if(rank1[x] < rank1[y])
        par[x] = y;
    else
    {
        par[y] = x;
        if(rank1[x] == rank1[y])
            rank1[x]++;
    }
}

bool same(int x, int y)
{
    return (find(x) == find(y));
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    Node a[MAX_N];
    for(int i = 0; i < m; ++i)
    {
        scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].n);
    }
    sort(a, a+m, cmp);
    int t = n;
    init(n);
    for(int i = 0; i < m; ++i)
    {
        if(!same(a[i].a, a[i].b))
        {
            unite(a[i].a, a[i].b);
            t--;
        }
        if(t == 1)
        {
            printf("%d\n", a[i].n);
            return 0;
        }
    }
    printf("-1\n");
    return 0;
}

洛谷P1197（并查集+逆向思考+邻接表+栈）

中等题，搞了我好久

  • 并查集只加边不减边，所以从所有星球被毁开始计算联通数
  • 由于数据太大，邻接矩阵开不下，只能邻接表（这是我第一次用邻接表）
  • 为了输出简单，我用了栈存储答案
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
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<cstring>
using namespace std;

const int MAX_N = 4e5 + 1;

int par[MAX_N]; // 父亲
int rankk[MAX_N]; //树的高度

void init(int n)
{
    for(int i = 0; i < n; ++i)
    {
        par[i] = i;
        rankk[i] = 0;
    }
}

int find(int x) //查询根
{
    if(par[x] == x)
        return x;
    else
        return par[x] = find(par[x]);
}

void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    if(x == y) return ;
    if(rankk[x] < rankk[y])
        par[x] = y;
    else
    {
        par[y] = x;
        if(rankk[x] == rankk[y])
            rankk[x]++;
    }
}

bool same(int x, int y)
{
    return find(x) == find(y);
}

struct Node
{
    int data;
    Node *next;
};

Node v[MAX_N]; //存起点编号

void initl(int n)
{
    for(int i = 0; i < n; ++i)
    {
        v[i].data = i;
        v[i].next = NULL;
    }
}

void InsertNode(int a, int b)
{
    Node *NewNode = (Node *)malloc(sizeof(Node));
    NewNode->data = b;
    NewNode->next = v[a].next;
    v[a].next = NewNode;
    return ;
}

int n, m, ans;
int book[MAX_N];
stack<int> s;

int main()
{
    scanf("%d%d", &n, &m);
    initl(n);
    for(int i = 0; i < m; ++i) //插入边
    {
        int a, b;
        scanf("%d%d", &a, &b);
        InsertNode(a, b);
        InsertNode(b, a);
    }

    int k;
    scanf("%d", &k);
    int deletek[k+1];
    memset(deletek, 0, sizeof(deletek));
    for(int i = 0; i < k; ++i)
    {
        scanf("%d", &deletek[i]);
        book[deletek[i]] = 1;
    }

    // for(int i = 0; i < n; ++i)
    // {
    //     Node *p = v[i].next;
    //     printf("%d: ", i);
    //     while(p)
    //     {
    //         printf("%d ", p->data);
    //         p = p->next;
    //     }
    //     printf("\n");
    // }

    init(n); //初始化并查集
    int ans = n - k;
    for(int i = 0; i < n; ++i)
    {
        Node *p = v[i].next;
        if(!book[i]) //没有删去的结点
        {
            while(p)
            {
                if(!book[p->data] && !same(i, p->data))
                {
                    unite(i, p->data);
                    ans--;
                }
                p = p->next;
            }
        }
    }

    s.push(ans);

    for(int i = k - 1; i >= 0; --i) //开始加边
    {
        int a = deletek[i];
        Node *p = &v[a];
        book[a] = 0;
        ans++;
        while(p)
        {
            if(!book[p->data])
            {
                if(!same(a, p->data))
                {
                    ans--;
                    unite(a, p->data);
                }
            }
            p = p->next;
        }
        s.push(ans);
    }
    while(!s.empty())
    {
        printf("%d\n", s.top());
        s.pop();
    }
    return 0;
}

洛谷P2024（并查集+思维）

想到其实还好做

  • 不知道每种动物属于哪种，于是开三倍长度的并查集，存储a，a 的天敌，a的天敌的天敌
  • 每次输入a及其天敌及其天敌的天敌都要更新
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<cstdio>

const int MAX_N = 1e4 * 5;

int par[MAX_N * 4]; // 父亲
int rank[MAX_N * 4]; //树的高度

void init(int N)
{
    for(int i = 0; i < N; ++i)
    {
        par[i] = i;
        rank[i] = 0;
    }
}

int find(int x) //查询根
{
    if(par[x] == x)
        return x;
    else
        return par[x] = find(par[x]);
}

void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    if(x == y) return ;
    if(rank[x] < rank[y])
        par[x] = y;
    else
    {
        par[y] = x;
        if(rank[x] == rank[y])
            rank[x]++;
    }
}

bool same(int x, int y)
{
    return find(x) == find(y);
}

int ans = 0;
int N, k;

void solve(int T, int X, int Y)
{
    if(X > N || Y > N)
    {
        ans++;
        return ;
    }
    if(T == 1)
    {
        if(same(X, Y+N) || same(X, Y+2*N))
        {
            ans++;
            return ;
        }
        else
        {
            unite(X, Y);
            unite(X+N, Y+N);
            unite(X+2*N, Y+2*N);
        }
    }
    else
    {
        if(same(X, Y) || same(X, Y+2*N))
        {
            ans++;
            return ;
        }
        else
        {
            unite(X, Y+N);
            unite(X+N, Y+N*2);
            unite(X+N*2, Y);
        }
    }
}

int main()
{
    scanf("%d%d", &N, &k);
    int T, X, Y;
    init(3 * N + 3);
    for(int i = 0; i < k; ++i)
    {
        scanf("%d%d%d", &T, &X, &Y);
        solve(T, X, Y);
    }
    printf("%d\n", ans);
    return 0;
}

洛谷P1197（带权并查集）

tle了2个点，只有61分，待更

结语

没什么好说的，做得要死要活的，才这么几道简单题，菜是原罪，继续加油吧~