Note:

vector的学习

vectorSTL(Standard Template Library)中的动态数组,功能非常的强大,在不存东西的时候几乎不占空间。

他可以做到:

  1. 尾部插入
  2. 获取长度
  3. 随机访问
  4. 清空
  5. 排序

vector 初始只占用很小的空间。随着内部元素增多,空间将会随之扩增。 OI 中,需要动态数组的场合,我们一般倾向于使用 vector,因为 vector 大小可变、提供了充足的 API。

eg:洛谷P1177

#include <bits/stdc++.h>
using namespace std;

int n;
vector <int> v;

void input() {
    cin >> n;

    for(int i=0; i<n; i++) {
        int x;
        cin >> x;
        v.push_back(x);     // x 追加到 vector 尾部
    }

    // v 最开始是空的
    // 第一次 push_back,会放进 v[0]
}

void work() {
    sort(v.begin(), v.end());

    for(int i=0; i<v.size(); i++)
        cout << v[i] << ' ';
}

int main() {
    input();
    work();

    return 0;
}

可以看到,vector是可以直接当数组访问的,非常的方便,在不知道数据数量时非常方便。

(stack)

举个例子:

我们洗盘子的时候,先来的盘子放在下面,后来的放在上面,而你洗盘子是从上面取盘子,且时不时还有盘子加入,这就是一个标准的栈。

我们永远是在顶端进行操作。在顶端加入,在顶端弹出。

所以栈的特性:后进先出。

所以满足“先进后出”的题目可以考虑使用栈来做。

来看一下define实现的简单栈:

int a[MAXN],tot;
#define top (a[tot])
#define pop tot--
#define push(x) (a[++tot]=(x))

是不是非常简单呢?简单而不失优雅

这样的栈有很多局限性,我们可以使用STL提供的栈:

#include<stack>
void work(){
    stack <int> s;
    s.push(x);//压入x
    printf("%d",s.top());查询栈顶
    while(!s.empty()){//栈是否为空
        s.pop();//弹出栈
    }
}

stl的栈还支持结构体,虽然不开O2比手写略慢,但是现在coiO2啊!

所以还是推荐使用stl的栈。

特别注意!如果在栈为空的情况下pop()你会得到RE(run time error)为奖励。

队列

今天有一群人排队,每次都是队尾加入,队首离开,这就是队列,他的规律是:先进后出

一个队列需要可以做到:

  1. 查询队首
  2. 弹出队首
  3. 压入队尾

STL也有队列,存在queue库中

q.push(x);//将x加入队尾
printf("%d",q.front());//查询队首
s.pop();//弹出队首

队列的弹出,查询,加入的时间复杂度都是$$O(1)$$的,非常方便,不建议手写队列,因为会浪费空间,如果空间不预估好可能会爆空间。

链表

重点来了~~

今天最难的部分就是链表,每个元素记住自己的左(右)。

链表是一种崭新的数据结构。它不以下标来寻址,而是通过相邻元素之间的联系。 通俗地讲,每个人记住自己紧邻的人。

eg1:月黑风高

n 名同学排队,每个人都只记得自己后面是谁,且编号为 1 的人站在最前面。 能否根据这些信息,还原出整支队伍

#include <cstdio>
const int MAXN = 100000 + 5;
int nxt[MAXN], n, cur = 1;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &nxt[i]);//记录他们后面都是谁
    }
    while (nxt[cur] != 0)
    {
        printf("%d ", cur);//遍历链表
        cur = nxt[cur];
    }
    printf("%d", cur);
    return 0;
}

这样就用简单的实现了链表。

eg2:队列安排

洛谷P1160

队列安排

题目描述

一个学校里老师要将班上 $N$ 个同学排成一列,同学被编号为 $1\sim N$,他采取如下的方法:

  1. 先将 $1$ 号同学安排进队列,这时队列中只有他一个人;
  2. $2-N$ 号同学依次入列,编号为 $i$ 的同学入列方式为:老师指定编号为 $i$ 的同学站在编号为 $1\sim(i-1)$ 中某位同学(即之前已经入列的同学)的左边或右边;
  3. 从队列中去掉 $M(M<N)$ 个同学,其他同学位置顺序不变。

在所有同学按照上述方法队列排列完毕后,老师想知道从左到右所有同学的编号。

输入格式

第 $1$ 行为一个正整数 $N$,表示了有 $N$ 个同学。

第 $2\sim N$行,第 $i$ 行包含两个整数 $k,p$,其中 $k$ 为小于 $i$ 的正整数,$p$ 为 $0$ 或者 $1$。若 $p$ 为$ 0$,则表示将 $i$ 号同学插入到 $k$ 号同学的左边,$p$ 为 $1$ 则表示插入到右边。

第 $N+1$ 行为一个正整数 $M$,表示去掉的同学数目。

接下来 $M$ 行,每行一个正整数 $x$,表示将 $x$ 号同学从队列中移去,如果 $x$ 号同学已经不在队列中则忽略这一条指令。

输出格式

$1$ 行,包含最多 $N$ 个空格隔开的正整数,表示了队列从左到右所有同学的编号,行末换行且无空格。

样例 #1

样例输入 #1

4
1 0
2 1
1 0
2
3
3

样例输出 #1

2 4 1

提示

样例解释:

将同学 $2$ 插入至同学 $1$ 左边,此时队列为:

2 1

将同学 $3$ 插入至同学 $2$ 右边,此时队列为:

2 3 1

将同学 $4$ 插入至同学 $1$ 左边,此时队列为:

2 3 4 1

将同学 $3$ 从队列中移出,此时队列为:

2 4 1

同学 $3$ 已经不在队列中,忽略最后一条指令

最终队列:

2 4 1

数据范围

对于 $20\%$ 的数据,有 $1\leq N\leq 10$;

对于 $40\%$ 的数据,有 $1\leq N\leq 1000$;

对于 $100\%$ 的数据,有 $1\leq N,M\leq100000$。

我们可以用静态双向链表维护队伍。 由于插入是指定相邻元素的插入,故可以 O(1) 寻址,从而插入是 O(1) 的。
删除同理 O(1)。

主要是实现插入和删除,插入也是很简单的:只需要将x左边的元素指向需要插入的元素,需要插入的元素指向x左边的元素,需要插入的元素指向x,x指向需要插入的元素。

void ins(int x, int target, int flag) {
    if(flag == 0) {
        // 把 x 插入到 target 的左边
        // 现在 x 是不在链表里面的
        int pre = le[target];
        // 把 x 插入到 pre, target 之间,形成 pre <=> x <=> target
        // 建立 pre 与 x 之间的联系
        rt[pre] = x;
        le[x] = pre;
        // 建立 x 与 target 之间的联系
        rt[x] = target;
        le[target] = x;
    } else {
        // 把 x 插入到 target 右边,形成 target <=> x <=> nxt
        int nxt = rt[target];
        rt[target] = x;
        le[x] = target;
        rt[x] = nxt;
        le[nxt] = x;
    }
}

删除就更简单了(现在需要删除x):将x左边的元素指向x右边的元素,x右边的元素指向x左边的元素,这样x就被“架空”了。有句话说得好:

怎样杀了一个人?如果没有人记得他了,即使他的身体活着,但他已经死了
void del(int x) {
    // 把 x 从 pre <=> x <=> nxt 里面删去
    // 只需要让 pre 直接连接 nxt 即可

    int pre = le[x], nxt = rt[x];

    // 如果 pre 的下一个元素不是 x,则显然 x 不在链表里面
    // 忽略掉本次操作
    if(rt[pre] != x)
        return;

    rt[pre] = nxt;
    le[nxt] = pre;
}
This article was written on July 25, 2022 at 18:16.