洛谷线性表题单题解

王逗比666

时隔好长时间更新，依然使用了TWilight6大佬的转换器，当然题目中的KaTeX公式无法转换，如果有想看题目的同学可以点开连接看一下原题

题单来自洛谷【数据结构1-1】线性表这次用的是默认的题目顺序  

P3156 【深基15.例1】询问学号
【深基15.例1】询问学号

题目描述

有 $n(n \le 2 \times 10^6)$ 名同学陆陆续续进入教室。我们知道每名同学的学号（在 $1$ 到 $10^9$ 之间），按进教室的顺序给出。上课了，老师想知道第 $i$ 个进入教室的同学的学号是什么（最先进入教室的同学 $i=1$），询问次数不超过 $10^5$ 次。

输入格式

第一行 $2$ 个整数 $n$ 和 $m$，表示学生个数和询问次数。

第二行 $n$ 个整数，表示按顺序进入教室的学号。

第三行 $m$ 个整数，表示询问第几个进入教室的同学。

输出格式

输出 $m$ 个整数表示答案，用换行隔开。

样例 #1

样例输入 #1

1. 
   
2. 10 3
   
3. 1 9 2 60 8 17 11 4 5 14
   
4. 1 5 9
   

复制代码

样例输出 #1

1. 
   
2. 1
   
3. 8
   
4. 5
   

复制代码

这道题没有什么好说的，将n个学生进入教室的顺序存在一个数组里，然后按照下标查早就好了，唯一需要注意的一点是$ n \leq 2 \times 10^6 $，所以定义数组范围的时候不要定义为100001这种，另外题解区说用cin和cout会TLE，实际上并不会

1. 
   
2. cpp
   
3. #include <iostream>
   
4. 
   
5. using namespace std;
   
6. 
   
7. const int N = 2000001;
   
8. 
   
9. int a[N];
   
10. 
    
11. int main(void) {
    
12.         int n, m;
    
13.         cin >> n >> m;
    
14. 
    
15.         for(int i = 1; i <= n; i++)
    
16.                 cin >> a[i];
    
17.         for(int i = 1; i <= m; i++) {
    
18.                 int x;
    
19.                 cin >> x;
    
20.                 cout << a[x] << endl;
    
21.         }
    
22. }
    

复制代码

P3613 【深基15.例2】寄包柜
【深基15.例2】寄包柜

题目描述

超市里有 $n(1\le n\le10^5)$ 个寄包柜。每个寄包柜格子数量不一，第 $i$ 个寄包柜有 $a_i(1\le a_i\le10^5)$ 个格子，不过我们并不知道各个 $a_i$ 的值。对于每个寄包柜，格子编号从 1 开始，一直到 $a_i$。现在有 $q(1 \le q\le10^5)$ 次操作：

- 1 i j k：在第 $i$ 个柜子的第 $j$ 个格子存入物品 $k(0\le k\le 10^9)$。当 $k=0$ 时说明清空该格子。
- 2 i j：查询第 $i$ 个柜子的第 $j$ 个格子中的物品是什么，保证查询的柜子有存过东西。

已知超市里共计不会超过 $10^7$ 个寄包格子，$a_i$ 是确定然而未知的，但是保证一定不小于该柜子存物品请求的格子编号的最大值。当然也有可能某些寄包柜中一个格子都没有。

输入格式

第一行 2 个整数 $n$ 和 $q$，寄包柜个数和询问次数。

接下来 $q$ 个整数，表示一次操作。

输出格式

对于查询操作时，输出答案，以换行隔开。

样例 #1

样例输入 #1

1. 
   
2. 5 4
   
3. 1 3 10000 118014
   
4. 1 1 1 1
   
5. 2 3 10000
   
6. 2 1 1
   

复制代码

样例输出 #1

1. 
   
2. 118014
   
3. 1
   

复制代码

提示

$\text{upd 2022.7.26}$：新增加一组 Hack 数据。

我一直觉得这道题的描述有问题，因为输入了n又好像什么用都没有，并且题目上下好像又有点矛盾，先是说“第 $i$ 个寄包柜有 $a_i(1\le a_i\le10^5)$ 个格子”，下面又说“当然也有可能某些寄包柜中一个格子都没有”，然后这些格子到底有多少我们也用不到。

超市里有 $n(1\le n\le10^5)$ 个寄包柜，我们要是开二维数组的话会TLE，虽然题单介绍上说这道题用到的是二维可变数组还有迭代器，但是题解区的大佬们选择用map直接解决问题，通过map<int, map<int, int>>的方式可以将map嵌套，然后直接当作二维数组使用，并且由于map内部使用红黑树实现的，所以时间复杂度较低

1. 
   
2. cpp
   
3. #include <iostream>
   
4. #include <map>
   
5. 
   
6. using namespace std;
   
7. 
   
8. int i, j, k;
   
9. int n, q;
   
10. map<int, map<int, int>> p;
    
11. 
    
12. int main(void) {
    
13.         cin >> n >> q;
    
14.         while(q--) {
    
15.                 int t;
    
16.                 cin >> t >> i >> j;
    
17.                 if(t == 1) {
    
18.                         cin >> k;
    
19.                         p[i][j] = k;
    
20.                 }
    
21.                 else  {
    
22.                         cout << p[i][j] << endl;
    
23.                 }
    
24.         }
    
25.         return 0;
    
26. }
    

复制代码

P1449 后缀表达式
后缀表达式

题目描述

所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。

如：$\texttt{3(5-2)+7}$ 对应的后缀表达式为：$\texttt{3.5.2.-7.+@}$。在该式中，@ 为表达式的结束符号。. 为操作数的结束符号。

输入格式

输入一行一个字符串 $s$，表示后缀表达式。

输出格式

输出一个整数，表示表达式的值。

样例 #1

样例输入 #1

1. 
   
2. 3.5.2.-*7.+@
   

复制代码

样例输出 #1

1. 
   
2. 16
   

复制代码

提示

数据保证，$1 \leq |s| \leq 50$，答案和计算过程中的每一个值的绝对值不超过 $10^9$。

后缀表达式是一个经典的用栈解决的问题（甚至《The C Programming Language》也有这道题），解决的思路很简单，输入字符，如果是数字则入栈，如果是运算符则将栈最顶部的两个元素出栈进行运算，再将运算结果入栈。其中有几个陷阱，首先栈是一个后进先出的线性表，所以我们一次性入栈a,b，则出栈顺序为b, a，所以如果我们将b, a出栈进行除法运算，则最后入栈的结果应该是b / a而不是a / b，减法同理；第二个问题是我们将表达式作为字符串读入，如果是数字则将其转化为int类型后再入栈，转化的方式是将当前字符减去'0'，即t = s - '0'，但是这样的缺陷是如果数字多位数的话会变成多个个位数分别入栈，解决方式是如果当前字符是数字则继续判断，如果输入内容依然是数字，则将之前的内容乘10再加上这个数字，即将这些个位数合并成一个多位数再将其整个入栈 （我就是因为这个错误卡了一下午）

1. 
   
2. cpp
   
3. #include <iostream>
   
4. #include <stack>
   
5. 
   
6. using namespace std;
   
7. 
   
8. char s;
   
9. stack<int> st;
   
10. 
    
11. int main(void) {
    
12.     while(cin >> s && s != '@') {
    
13.         if(s >= '0' && s <= '9') {
    
14.             int t = s - '0';
    
15.             while(cin >> s && s >= '0' && s <= '9') {
    
16.                 t = t * 10 + s - '0';
    
17.             }
    
18.             st.push(t);
    
19.         }
    
20.         if(s == '+') {
    
21.             int a = st.top();
    
22.             st.pop();
    
23.             int b = st.top();
    
24.             st.pop();
    
25.             st.push(b + a);
    
26.         }
    
27.         if(s == '-') {
    
28.             int a = st.top();
    
29.             st.pop();
    
30.             int b = st.top();
    
31.             st.pop();
    
32.             st.push(b - a);
    
33.         }
    
34.         if(s == '*') {
    
35.             int a = st.top();
    
36.             st.pop();
    
37.             int b = st.top();
    
38.             st.pop();
    
39.             st.push(b * a);
    
40.         }
    
41.         if(s == '/') {
    
42.             int a = st.top();
    
43.             st.pop();
    
44.             int b = st.top();
    
45.             st.pop();
    
46.             st.push(b / a);
    
47.         }
    
48.     }
    
49. 
    
50.     cout << st.top() << endl;
    
51. 
    
52.     return 0;
    
53. }
    

复制代码

P1996 约瑟夫问题
约瑟夫问题

题目描述

$n$ 个人围成一圈，从第一个人开始报数,数到 $m$ 的人出列，再由下一个人重新从 $1$ 开始报数，数到 $m$ 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

注意：本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 $n-1$ 名小朋友，而该题是全部出圈。

输入格式

输入两个整数 $n,m$。

输出格式

输出一行 $n$ 个整数，按顺序输出每个出圈人的编号。

样例 #1

样例输入 #1

1. 
   
2. 10 3
   

复制代码

样例输出 #1

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

复制代码

提示

$1 \le m, n \le 100$

对于这道题我们可以有队列来解决，首先我们要知道是这些人围城了一个圈，;那么我们用队列模拟的话可以在队列读完之后将队头放到队尾，这样就实现了一个循环，如果队列没有空我们就继续执行这个循环，当第m个人在队头时我们将其出队

1. 
   
2. cpp
   
3. #include <iostream>
   
4. #include <queue>
   
5. 
   
6. using namespace std;
   
7. 
   
8. queue<int> q;
   
9. int n, m;
   
10. 
    
11. int main(void) {
    
12.     cin >> n >> m;
    
13. 
    
14.     int cnt = 1;
    
15.     for(int i = 1; i <= n; i++) {
    
16.         q.push(i);
    
17.     }
    
18. 
    
19.     while(!q.empty()) {
    
20.         if(cnt == m) {
    
21.             cout << q.front() << " ";
    
22.             q.pop();
    
23.             cnt = 1;
    
24.         }
    
25.         else {
    
26.             cnt++;
    
27.             q.push(q.front());
    
28.             q.pop();
    
29.         }
    
30.     }
    
31.     cout << endl;
    
32. 
    
33.     return 0;
    
34. }
    

复制代码

P1160 队列安排
队列安排

题目描述

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

1. 先将 $1$ 号同学安排进队列，这时队列中只有他一个人；

2. $2\sim N$ 号同学依次入列，编号为 $i$ 的同学入列方式为：老师指定编号为 $i$ 的同学站在编号为 $1\sim(i-1)$ 中某位同学（即之前已经入列的同学）的左边或右边；

3. 从队列中去掉 $M$ 个同学，其他同学位置顺序不变。

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

输入格式

第一行一个整数 $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$ 号同学已经不在队列中则忽略这一条指令。

输出格式

一行，包含最多 $N$ 个空格隔开的整数，表示了队列从左到右所有同学的编号。

样例 #1

样例输入 #1

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

复制代码

样例输出 #1

1. 
   
2. 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<M\leq N\leq 10^5$。

虽然题目叫做队列安排，但是这道题要用到链表，好巧不巧的是stl中并没有写好的链表库，所以这道题最大的难点是手写链表，下面的内容抄了Mickey_snow大佬的代码，并且对大佬在题解中写的模糊的地方进行了重新解释（这个大佬还喜欢重复使用变量，所以新手可能会看着有点乱），另外由于代码是抄来的，我就不更改变量名和函数名了

具体的解决方式是用用双向链表，由于本题最大的数据不超过$10^5$，并且人数正好是整数，所以避开了用链表难以随机访问的缺点，我们还可以直接用一个结构体数组将所有元素存起来（所以说是在用数组模拟双链表？）

首先我们需要定义节点queueDat，每个节点由三个内容构成，当前节点在整个队列（这里的队列指的是题目中学生们排序的队列）中的次序ID，以及分别指向当前节点前面节点和后面节点的指针front和back，并且定义一个结构体数组用来保存所有的节点：

1. 
   
2. cpp
   
3. struct queueDat
   
4. {
   
5.     int ID;
   
6.     queueDat *front = NULL, *back = NULL;
   
7. }que[100001];
   

复制代码

再定义一个指向队头（也就是链表中第一个元素）的指针head，默认指向数组的第一个元素

1. 
   
2. cpp
   
3. queueDat *head = &que[1];
   

复制代码

在定义好链表节点和数组之后，我们就可以进行数据的存放了，此时我们注意到题目中同学们出队时出队的学生可能时重复的，如果是重复的我们直接将其忽略，所以我们需要判断一个元素是否已经入队，这里我们选择建议一个长度和que相同的bool数组inQueue进行判断，并且用memset()为其统一赋值

1. 
   
2. cpp
   
3. bool inQueue[100001];
   
4. memset(inQueue, false, sizeof(inQueue));
   

复制代码

此时一号同学已经入队，所以我们要将一号同学标记为true

1. 
   
2. cpp
   
3. inQueue[1] = true;
   

复制代码

我们再将每个节点的下标和ID一一对应

1. 
   
2. cpp
   
3. for(int i = 1; i < 100001; i++)
   
4.     que[i].ID = i;
   

复制代码

由于是双向链表，所以对于链表中此时唯一的元素1号同学来说，它的front指针和back指针都指向的是他自己

1. 
   
2. cpp
   
3. que[1].front = &que[1];
   
4. que[1].back = &que[1];
   

复制代码

到此，我们链表的初始化就完成了，现在需要实现链表的插入和删除操作，我们定义两个函数_add()和_cut()分别实现插入和删除  
对于插入操作，题目上要求同时可以向左边或者右边操作，所以我们需要一个bool参数back来判断往哪个方向插入，另外需要两个整形参数num和ID，即要插入的元素要要插入的位置

1. 
   
2. cpp
   
3. void _add(int num, int ID, bool back)
   
4. {
   
5.     queueDat *find = &que[ID], *add = &que[num];
   
6.     if(back)    //向后插入
   
7.     {
   
8.         add->front = find;
   
9.         add->back = find->back;
   
10.         find->back = add;
    
11.         find = find->back->back;
    
12.         find->front = add;
    
13.         return;
    
14.     }
    
15.     else    //向前插入
    
16.     {
    
17.         add->back = find;
    
18.         add->front = find->front;
    
19.         find = find->front;
    
20.         find->back = add;
    
21.         find = find->back->back;
    
22.         find->front = add;
    
23.         if(ID == head->ID) head = add;
    
24.     }
    
25. }
    

复制代码

在_add函数中，我们定义了两个指针add和find，find指向要插入的位置，add指向要插入的元素（大佬的题解里面把这里写反了，让我迷茫了好长时间）  
以向后插入为例，首先我们将要插入元素的前面指向要插入的位置，将后面指向要插入的元素后面，再将要插入的位置的后面指向要插入的元素，将插入的位置指向原本它后面的后面，最后将此时的find（位置已经更改成最开始的find后面的后面，也就是add的后面）的前面指向add，即将add后面的那个元素的前面指向add，此时add已经成功插入到了预期位置的后面  
向前插入同理，将add的后面指向find，再将add的前面指向find的前面，将find指向find的前面，此时将find的后面指向add，也就是将find前面那个元素的后面指向add，这样add就和前面这个元素“对接”，再将find移动到此时它后面的后面，也就是add的后面，将它的前面指向add，也就是将add后面的元素的前面指向add，此时add已经成功插入到了预期位置的前面。由于是向前面插入元素，所以有可能插入后这个元素成为了队头，因此需要进行判断，如果要插入的位置正好是队头处于的位置，就将队头也指向这个元素  
用语言描述很乱，但是可以画幅图就非常直观了  
在了解了插入操作后，删除操作可以很容易的首先出来，在_cut函数中，我们由一个整形参数ID，说明要删除哪个位置的元素

1. 
   
2. cpp
   
3. void _cut(int ID)
   
4. {
   
5.     queueDat *cut = &que[ID];
   
6.     if(cut->ID == head->ID) head = cut->back;
   
7.     cut = cut->front;
   
8.     cut->back = cut->back->back;
   
9.     cut = cut->back;
   
10.     cut->front = cut->front->front;
    
11. }
    

复制代码

由于我们可能删除的是队头，所以要进行判断，如果删除了队头就将队头指向原本队头后面的元素，对于元素本身的删除，我们要做的是将它前后两个元素“跳过”它进行互相指向，这样这个元素本身的存在就没有了意义，也就被删除了  
在实现这两个功能之后，我们就可以着手完成题目了，首先按照要求将同学们入队

1. 
   
2. cpp
   
3. int totStudents, a, b;
   
4.         cin >> totStudents;
   
5.         for(int i = 2; i <= totStudents; i++) {
   
6.                 inQueue[i] = true;
   
7.                 cin >> a >> b;
   
8.                 _add(i, a, ((b == 0) ? false : true));
   
9.         }
   

复制代码

这里用了一个三目运算符，翻译一下就是如果b是0，第三个参数就是false，否则是true  
之后再输入m个同学将他们出队，注意这里和上面两个输入大佬都用了同一个变量totStudents，实际上它们是两个变量n和m，代表入队的同学数量和出队的同学数量

1. 
   
2. cpp
   
3.         cin >> totStudents;
   
4.         for(int i = 0; i < totStudents; i++) {
   
5.                 cin >> a;
   
6.                 if(inQueue[a] == true) {
   
7.                         inQueue[a] = false;
   
8.                         _cut(a);
   
9.                 }
   
10.         }
    

复制代码

最后我们从队头开始，输出在队中的同学，这里大佬将之前的变量b重新利用了一下，让它等于队头的ID，在输出当前队头后，将队头指向它后面的元素，由于是双向链表，所以最后全部输出后队头又会回到一开始的位置，也就是b存放的位置，所以当它们相等时退出循环

1. 
   
2. cpp
   
3. b = head->ID;
   
4.         do {
   
5.                 cout << head->ID << " ";
   
6.                 head = head->back;
   
7.         } while(b != head->ID);
   
8.         cout << endl;
   

复制代码

至此这道题就完成了，下面是整体代码：

1. 
   
2. cpp
   
3. #include <iostream>
   
4. #include <cstring>
   
5. 
   
6. using namespace std;
   
7. 
   
8. struct queueDat
   
9. {
   
10.     int ID;
    
11.     queueDat *front = NULL, *back = NULL;
    
12. }que[100001];
    
13. 
    
14. queueDat *head = &que[1];
    
15. 
    
16. void _add(int num, int ID, bool back)
    
17. {
    
18.     queueDat *find = &que[ID], *add = &que[num];
    
19.     if(back)    //向后插入
    
20.     {
    
21.         add->front = find;
    
22.         add->back = find->back;
    
23.         find->back = add;
    
24.         find = find->back->back;
    
25.         find->front = add;
    
26.         return;
    
27.     }
    
28.     else    //向前插入
    
29.     {
    
30.         add->back = find;
    
31.         add->front = find->front;
    
32.         find = find->front;
    
33.         find->back = add;
    
34.         find = find->back->back;
    
35.         find->front = add;
    
36.         if(ID == head->ID) head = add;
    
37.     }
    
38. }
    
39. 
    
40. void _cut(int ID)
    
41. {
    
42.     queueDat *cut = &que[ID];
    
43.     if(cut->ID == head->ID) head = cut->back;
    
44.     cut = cut->front;
    
45.     cut->back = cut->back->back;
    
46.     cut = cut->back;
    
47.     cut->front = cut->front->front;
    
48. }
    
49. 
    
50. int main(void) {
    
51.     bool inQueue[100001];
    
52.     memset(inQueue, false, sizeof(inQueue));
    
53.     inQueue[1] = true;
    
54. 
    
55.     for(int i = 1; i < 100001; i++)
    
56.         que[i].ID = i;
    
57.    
    
58.     que[1].front = &que[1];
    
59.     que[1].back = &que[1];
    
60. 
    
61.     int totStudents, a, b;
    
62.     cin >> totStudents;
    
63.     for(int i = 2; i <= totStudents; i++) {
    
64.             inQueue[i] = true;
    
65.             cin >> a >> b;
    
66.             _add(i, a, ((b == 0) ? false : true));
    
67.     }
    
68.     cin >> totStudents;
    
69.     for(int i = 0; i < totStudents; i++) {
    
70.             cin >> a;
    
71.             if(inQueue[a] == true) {
    
72.                     inQueue[a] = false;
    
73.                     _cut(a);
    
74.             }
    
75.     }
    
76.     b = head->ID;
    
77.     do {
    
78.             cout << head->ID << " ";
    
79.             head = head->back;
    
80.     } while(b != head->ID);
    
81.     cout << endl;
    
82. 
    
83.     return 0;
    
84. }
    

复制代码

P1540 [NOIP2010 提高组] 机器翻译
[NOIP2010 提高组] 机器翻译

题目背景

小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。

题目描述

这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。

假设内存中有 $M$ 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过 $M-1$，软件会将新单词存入一个未使用的内存单元；若内存中已存入 $M$ 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。

假设一篇英语文章的长度为 $N$ 个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。

输入格式

共 $2$ 行。每行中两个数之间用一个空格隔开。

第一行为两个正整数 $M,N$，代表内存容量和文章的长度。

第二行为 $N$ 个非负整数，按照文章的顺序，每个数（大小不超过 $1000$）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。

输出格式

一个整数，为软件需要查词典的次数。

样例 #1

样例输入 #1

1. 
   
2. 3 7
   
3. 1 2 1 5 4 4 1
   

复制代码

样例输出 #1

1. 
   
2. 5
   

复制代码

提示

样例解释

整个查字典过程如下：每行表示一个单词的翻译，冒号前为本次翻译后的内存状况：

1. 1：查找单词 1 并调入内存。
2. 1 2：查找单词 2 并调入内存。
3. 1 2：在内存中找到单词 1。
4. 1 2 5：查找单词 5 并调入内存。
5. 2 5 4：查找单词 4 并调入内存替代单词 1。
6. 2 5 4：在内存中找到单词 4。
7. 5 4 1：查找单词 1 并调入内存替代单词 2。

共计查了 $5$ 次词典。

数据范围

- 对于 $10\%$ 的数据有 $M=1$，$N \leq 5$；
- 对于 $100\%$ 的数据有 $1 \leq M \leq 100$，$1 \leq N \leq 1000$。

这道题可以直接用数组模拟得出结果，但是由于这是线性表题单，所以我们用队列来实现

可以发现如果内存满后，遇到新的单词会清除最开始的单词再存入新的单词，有着先进先出特性的队列可以满足我们的需求，并且这里的“单词”都是非负整数，我们可以一个bool数组来判断单词是否已经存入内存中

1. 
   
2. cpp
   
3. #include <iostream>
   
4. #include <queue>
   
5. 
   
6. using namespace std;
   
7. 
   
8. queue<int> q;
   
9. 
   
10. int m, n, cnt;
    
11. bool st[1001];
    
12. 
    
13. int main(void)
    
14. {
    
15.     cin >> m >> n;
    
16. 
    
17.     for(int i = 1; i <= n; i++) {
    
18.         int a;
    
19.         cin >> a;
    
20.         if(!st[a]) {
    
21.             if(q.size() == m) {
    
22.                 st[q.front()] = false;
    
23.                 q.pop();
    
24.             }
    
25.             st[a] = true;
    
26.             cnt++;
    
27.             q.push(a);
    
28.         }
    
29.     }
    
30. 
    
31.     cout << cnt << endl;
    
32. 
    
33.     return 0;
    
34. }
    

复制代码

P2058 [NOIP2016 普及组] 海港
[NOIP2016 普及组] 海港

题目背景

NOIP2016 普及组 T3

题目描述

小 K 是一个海港的海关工作人员，每天都有许多船只到达海港，船上通常有很多来自不同国家的乘客。

小 K 对这些到达海港的船只非常感兴趣，他按照时间记录下了到达海港的每一艘船只情况；对于第 $i$ 艘到达的船，他记录了这艘船到达的时间 $t_i$ (单位：秒)，船上的乘客数 $k_i$，以及每名乘客的国籍 $x_{i,1}, x_{i,2},\dots,x_{i,k}$。

小K统计了 $n$ 艘船的信息，希望你帮忙计算出以每一艘船到达时间为止的 $24$ 小时（$24$ 小时 $=86400$ 秒）内所有乘船到达的乘客来自多少个不同的国家。

形式化地讲，你需要计算 $n$ 条信息。对于输出的第 $i$ 条信息，你需要统计满足 $t_i-86400<t_p \le t_i$ 的船只 $p$，在所有的 $x_{p,j}$ 中，总共有多少个不同的数。

输入格式

第一行输入一个正整数 $n$，表示小 K 统计了 $n$ 艘船的信息。

接下来 $n$ 行，每行描述一艘船的信息：前两个整数 $t_i$ 和 $k_i$ 分别表示这艘船到达海港的时间和船上的乘客数量，接下来 $k_i$ 个整数 $x_{i,j}$ 表示船上乘客的国籍。

保证输入的 $t_i$ 是递增的，单位是秒；表示从小K第一次上班开始计时，这艘船在第 $t_i$ 秒到达海港。

保证 $1 \le n \le 10^5$，$\sum{k_i} \le 3\times 10^5 $ ，$1\le x_{i,j} \le 10^5$， $1 \le t_{i-1}\le  t_i    \le  10^9$。


其中 $\sum{k_i}$ 表示所有的 $k_i$ 的和。

输出格式

输出 $n$ 行，第 $i$ 行输出一个整数表示第 $i$ 艘船到达后的统计信息。

样例 #1

样例输入 #1

1. 
   
2. 3
   
3. 1 4 4 1 2 2
   
4. 2 2 2 3
   
5. 10 1 3
   

复制代码

样例输出 #1

1. 
   
2. 3
   
3. 4
   
4. 4
   

复制代码

样例 #2

样例输入 #2

1. 
   
2. 4
   
3. 1 4 1 2 2 3
   
4. 3 2 2 3
   
5. 86401 2 3 4
   
6. 86402 1 5
   

复制代码

样例输出 #2

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

复制代码

提示

【样例解释 1】

第一艘船在第 $1$ 秒到达海港，最近 $24$ 小时到达的船是第一艘船，共有 $4$ 个乘客，分别是来自国家 $4,1,2,2$，共来自 $3$ 个不同的国家；

第二艘船在第 $2$ 秒到达海港，最近 $24$ 小时到达的船是第一艘船和第二艘船，共有 $4 + 2 = 6$ 个乘客，分别是来自国家 $4,1,2,2,2,3$，共来自 $4$ 个不同的国家；

第三艘船在第 $10$ 秒到达海港，最近 $24$ 小时到达的船是第一艘船、第二艘船和第三艘船，共有 $4+2+1=7$ 个乘客，分别是来自国家 $4,1,2,2,2,3,3$，共来自 $4$ 个不同的国家。

【样例解释 2】

第一艘船在第 $1$ 秒到达海港，最近 $24$ 小时到达的船是第一艘船，共有 $4$ 个乘客，分别是来自国家 $1,2,2,3$，共来自 $3$ 个不同的国家。

第二艘船在第 $3$ 秒到达海港，最近 $24$ 小时到达的船是第一艘船和第二艘船，共有 $4+2=6$ 个乘客，分别是来自国家 $1,2,2,3,2,3$，共来自 $3$ 个不同的国家。

第三艘船在第 $86401$ 秒到达海港，最近 $24$ 小时到达的船是第二艘船和第三艘船，共有 $2+2=4$ 个乘客，分别是来自国家 $2,3,3,4$，共来自 $3$ 个不同的国家。

第四艘船在第 $86402$ 秒到达海港，最近 $24$ 小时到达的船是第二艘船、第三艘船和第四艘船，共有 $2+2+1=5$ 个乘客，分别是来自国家 $2,3,3,4,5$，共来自 $4$个 不同的国家。

【数据范围】

- 对于 $10\%$ 的测试点，$n=1,\sum k_i \leq 10,1 \leq x_{i,j} \leq 10, 1 \leq t_i \leq 10$。
- 对于 $20\%$ 的测试点，$1 \leq n \leq 10, \sum k_i \leq 100,1 \leq x_{i,j} \leq 100,1 \leq t_i \leq 32767$。
- 对于 $40\%$ 的测试点，$1 \leq n \leq 100, \sum k_i \leq 100,1 \leq x_{i,j} \leq 100,1 \leq t_i \leq 86400$。
- 对于 $70\%$ 的测试点，$1 \leq n \leq 1000, \sum k_i \leq 3000,1 \leq x_{i,j} \leq 1000,1 \leq t_i \leq 10^9$。
- 对于 $100\%$ 的测试点，$1 \leq n \leq 10^5,\sum k_i \leq 3\times 10^5, 1 \leq x_{i,j} \leq 10^5,1\leq t_i \leq 10^9$。

这道题和上面的题有点像，都要用队列，但是一个小时内会进入多个相同国籍的人，所以直接用整数和数组存会很麻烦（我第一次只得了40分） 虽然题解区很多大佬直接二十行代码出结果 ，所以我们需要用到结构体，一个结构体包含乘客的国籍和进入的时间，再创建一个数组存储不同国籍有多少乘客，最后还需要一个变量计数有多少个国籍，创建一个结构体队列，将每个结构体入队，如果最开始进入的乘客和现在进入的乘客（即队首和队尾）进入时间相差超过了86400秒，则将第一个进入的乘客（即队首）对应国籍的乘客数量减一再将队首出队，如果减一之后这个国籍的乘客数量变成了0就将计数变量也减一，最后更新队首

1. 
   
2. cpp
   
3. #include <iostream>
   
4. #include <queue>
   
5. 
   
6. using namespace std;
   
7. 
   
8. struct node{
   
9.     int time;
   
10.     int nationality;
    
11. };
    
12. 
    
13. queue<node> q;
    
14. 
    
15. int n, t, k, cnt;
    
16. int arr[100001];
    
17. 
    
18. int main(void) {
    
19.     cin >> n;
    
20.     while(n--) {
    
21.         cin >> t >> k;
    
22.         for(int i = 1; i <= k; i++) {
    
23.             node a;
    
24.             cin >> a.nationality;
    
25.             a.time = t;
    
26.             arr[a.nationality]++;
    
27.             if(arr[a.nationality] == 1) cnt++;
    
28.             q.push(a);
    
29.         }
    
30.         node b = q.back();
    
31.         node f = q.front();
    
32. 
    
33.         while(b.time - f.time >= 86400) {
    
34.             arr[f.nationality]--;
    
35.             if(arr[f.nationality] == 0) cnt--;
    
36.             q.pop();
    
37.             f = q.front();
    
38.         }
    
39. 
    
40.         cout << cnt << endl;
    
41.     }
    
42.     return 0;
    
43. }
    

复制代码

P1241 括号序列
括号序列

题目描述

定义如下规则：

1. 空串是「平衡括号序列」
2. 若字符串 $S$ 是「平衡括号序列」，那么 $\texttt{[}S\texttt]$ 和 $\texttt{(}S\texttt)$ 也都是「平衡括号序列」
3. 若字符串 $A$ 和 $B$ 都是「平衡括号序列」，那么 $AB$（两字符串拼接起来）也是「平衡括号序列」。


例如，下面的字符串都是平衡括号序列：


()，[]，(())，([])，()[]，()[()]


而以下几个则不是：


(，[，]，)(，())，([()


现在，给定一个仅由 (，)，[，]构成的字符串 $s$，请你按照如下的方式给字符串中每个字符配对：
1. 从左到右扫描整个字符串。
2. 对于当前的字符，如果它是一个右括号，考察它与它左侧离它最近的未匹配的的左括号。如果该括号与之对应（即小括号匹配小括号，中括号匹配中括号），则将二者配对。如果左侧未匹配的左括号不存在或与之不对应，则其配对失败。

配对结束后，对于 $s$ 中全部未配对的括号，请你在其旁边添加一个字符，使得该括号和新加的括号匹配。

输入格式

输入只有一行一个字符串，表示 $s$。

输出格式

输出一行一个字符串表示你的答案。

样例 #1

样例输入 #1

1. 
   
2. ([()
   

复制代码

样例输出 #1

1. 
   
2. ()[]()
   

复制代码

样例 #2

样例输入 #2

1. 
   
2. ([)
   

复制代码

样例输出 #2

1. 
   
2. ()[]()
   

复制代码

提示

数据规模与约定

对于全部的测试点，保证 $s$ 的长度不超过 100，且只含  (，)，[，] 四个字符。

括号匹配也是一个典型的用栈解决的问题，本体相较于单纯的括号匹配而言只有小括号和中括号，并且需要将没有匹配成功的括号补全

另外本题还有个谜之匹配规则，据说原来这是一道毒瘤题，还是一道曾经的绿题，虽然现在它成了橙题，好在题解区解释了它的匹配规则，这里给出题解区大佬YuJieSong的解释:

1. 
   
2. markdown
   
3. 原题目：扫描一遍原序列，对每一个右括号，找到在它左边最靠近它的左括号匹配，如果没有就放弃。
   
4. 
   
5. 翻译：扫描一遍原序列，当找到一个右括号（即找到一个 ' ) ' 或者 ' ] ' 时），以它为起点向左找，找到一个没被标记成功匹配的左括号（即找到一个 ' ( ' 或者 ' [ ' ），如果两者匹配的话，标记它们成功 牵手 匹配，如果不匹配，或者找不到左括号的话，不做任何标记。
   
6. 
   
7. 原题目：在以这种方式把原序列匹配完成后，把剩下的未匹配的括号补全。
   
8. 
   
9. 翻译：上面扫描一遍标记完成功匹配的括号之后，扫描一遍序列，对于标记过的括号，则直接输出；对于没有标记的括号，则补全成对输出
   
10. 
    
11. 举例：如果有个 ' [ ' 或 ' ] ' 没被标记匹配，则输出 [ ]
    
12. 
    
13. 如果还不理解的话，给个测试样例：
    
14. 
    
15. 输入：( [ ) ] )
    
16. 
    
17. 输出：( [ ( ) ] )
    

复制代码

在明白题意后，我们可以遍历这个字符串，如果是左括号就将它在字符串中的位置入栈，由于匹配规则是遍历到右括号后从左开始找，所以我们在遇到右括号后将它与栈顶，即离它最近的左括号配对，如果配对成功就出栈，并且我们还需要一个bool数组用来判断是否配对，如果配对就将这两个括号的位置标记为true

在字符串遍历结束后我们就得到了一个标记了哪些括号成功配对的bool数组，现在我们从第一个字符开始再次遍历，如果这个字符被标记成功配对，我们就直接输出它，否则就按照它的左右以及大小给它补上另一半括号

1. 
   
2. cpp
   
3. #include <iostream>
   
4. #include <string>
   
5. #include <stack>
   
6. 
   
7. using namespace std;
   
8. 
   
9. bool x[101];
   
10. string s;
    
11. stack<int> st;
    
12. 
    
13. int main(void) {
    
14.     cin >> s;
    
15. 
    
16.     for(int i = 0; i < s.length(); i++) {
    
17.         if(s[i] == ')' && !st.empty()) {
    
18.             if(s[st.top()] == '(') {
    
19.                 x[i] = x[st.top()] = true;
    
20.                 st.pop();
    
21.             }
    
22.         } else if(s[i] == ']' && !st.empty()){
    
23.             if(s[st.top()] == '[') {
    
24.                 x[i] = x[st.top()] = true;
    
25.                 st.pop();
    
26.             }
    
27.         } else
    
28.             st.push(i);
    
29.     }
    
30. 
    
31.     for(int i = 0; i < s.length(); i++) {
    
32.         if(x[i]) cout << s[i];
    
33.         else if(s[i] == '(' || s[i] == ')') cout << "()";
    
34.         else cout << "[]";
    
35.     }
    
36.     cout << endl;
    
37.    
    
38.     return 0;
    
39. }
    

复制代码

P4387 【深基15.习9】验证栈序列
【深基15.习9】验证栈序列

题目描述

给出两个序列 pushed 和 poped 两个序列，其取值从 1 到 $n(n\le100000)$。已知入栈序列是 pushed，如果出栈序列有可能是 poped，则输出 Yes，否则输出 No。为了防止骗分，每个测试点有多组数据。

输入格式

第一行一个整数 $q$，询问次数。

接下来 $q$ 个询问，对于每个询问：

第一行一个整数 $n$ 表示序列长度；

第二行 $n$ 个整数表示入栈序列；

第三行 $n$ 个整数表示出栈序列；

输出格式

对于每个询问输出答案。

样例 #1

样例输入 #1

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

复制代码

样例输出 #1

1. 
   
2. Yes
   
3. No
   

复制代码

这道题其实挺简单的，虽然它是黄题，但是很抽象的是我一开始为了省劲少定义了一个数组，wa了以后交了改改了交，好几次才过.....

回归正题，我们只需要定义两个数组，将第一个数组入栈，然后和第二个数组比对，如果栈顶的数能和第二个数组的数对应上就将这个数出栈然后继续比对，到最后如果栈空了则比对成功输出Yes，反正输出No  
需要注意的是给出的“入栈序列”并不是说这个序列会一次性全部入栈，而是有各种入栈的可能 所以这道题就是每年csp第一轮选择题里面的将元素a, b, c依次进栈），则下列选项中出栈序列不可能是（）的代码版  
还有一点就是由于有q组数据，所以每次判断前我们都要先将栈清空

1. 
   
2. cpp
   
3. #include <iostream>
   
4. #include <stack>
   
5. 
   
6. using namespace std;
   
7. 
   
8. const int N = 100001;
   
9. 
   
10. int a[N], b[N];
    
11. int p, q, cnt;
    
12. stack<int> st;
    
13. 
    
14. void init(void) {
    
15.     while(!st.empty()) {
    
16.         st.pop();
    
17.     }
    
18.     cnt = 1;
    
19. }
    
20. 
    
21. int main(void) {
    
22.     cin >> q;
    
23.     while(q--) {
    
24.         init();
    
25.         cin >> p;
    
26.         for(int i = 1; i <= p; i++) {
    
27.             cin >> a[i];
    
28.         }
    
29.         for(int i = 1; i <= p; i++) {
    
30.             cin >> b[i];
    
31.         }
    
32.         for(int i = 1; i <= p; i++) {
    
33.             st.push(a[i]);
    
34.             while(st.top() == b[cnt]) {
    
35.                 cnt++;
    
36.                 st.pop();
    
37.                 if(st.empty()) {
    
38.                     break;
    
39.                 }
    
40.             }
    
41.         }
    
42.         printf("%s
    
43. ", st.empty() ? "Yes" : "No");
    
44.     }
    
45. 
    
46.     return 0;
    
47. }
    

复制代码

P2234 [HNOI2002] 营业额统计
[HNOI2002] 营业额统计

题目描述

Tiger 最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。

Tiger 拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：当最小波动值越大时，就说明营业情况越不稳定。

而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助 Tiger 来计算这一个值。

我们定义，一天的最小波动值 = $\min\{|\text{该天以前某一天的营业额}-\text{该天营业额}|\}$。

特别地，第一天的最小波动值为第一天的营业额。

输入格式

第一行为正整数 $n$（$n \leq 32767$） ，表示该公司从成立一直到现在的天数，接下来的 $n$ 行每行有一个整数 $a_i$（$|a_i| \leq 10^6$) ，表示第 $i$ 天公司的营业额，可能存在负数。

输出格式

输出一个正整数，即每一天最小波动值的和，保证结果小于 $2^{31}$。

样例 #1

样例输入 #1

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

复制代码

样例输出 #1

1. 
   
2. 12
   

复制代码

提示

结果说明：$5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12$

这道题思路其实很简单，最暴力的写法就是从第三个数开始每读一个数就排下序，再取$min(abs(a_i - a_i - 1), abs(a_i - a_i + 1))$，然而这样做即使再快的排序来了也要超时（除非你能找到一个时间复杂度是O(1)的排序算法 除了猴子算法)，介绍上说这道题应该用平衡树（平衡树是什么），幸好万能的题解区给出了用set容器做的方法（set是什么），于是赶紧去百度了一下，终于弄明白题解区的代码了

这道题依然是题解区的代码，代码来自于大佬Okarin
set容器内封装了一些树形结构，所以我们可以直接把它当成树来用，但是仅用set是不够的，我们还需要遍历和访问set内存放的元素，这个时候就用到了iterator迭代器

1. 
   
2. cpp
   
3. set<int> s;
   
4. set<int>::iterator k, a
   

复制代码

另外我们需要知道对于每天营业额的最小波动值的$min(abs(a_i - a_n))$，即要知道对于每个元素来说跟它大小最相近的元素，除了排序外我们可以使用二分来找到数组中第一个大于等于当前元素的元素，放在set中我们也不需要手写二分，可以直接用lower_bound()，当然对于二分来说我们需要一个边界值，所以我们可以再容器中插入两个边界值(这里我用的是$\pm0x7fffff$)

1. 
   
2. cpp
   
3. s.insert(0x7ffffff);
   
4. s.insert(-0x7ffffff);
   

复制代码

接下来我们要做的就是根据迭代器和lower_bound()查找对于当前元素第一个大于等于它的元素，另外还需要一个迭代器指向这个元素的前一个元素，也就是第一个小与等于当前元素的元素，它们差的绝对值的最小值就是当天的最小波动值，累加起来就是答案  
要注意的是对于第一天，它的营业额就是最小的波动值，所以要进行特判  
另外iterator的作用类似于指针，所以如果我们将k = lower_bound(x)，k并不是被赋值为了第一个大于等于x的元素的值，而是指向了这个元素，因此我们要获得这个元素的值就需要像指针一样解引用*k  
现在我们的准备工作就完成了，下面是全部代码：

1. 
   
2. cpp
   
3. #include <iostream>
   
4. #include <set>
   
5. #include <algorithm>
   
6. 
   
7. using namespace std;
   
8. 
   
9. set<int> s;
   
10. set<int>::iterator k, a;
    
11. 
    
12. int x, ans, n;
    
13. 
    
14. int main(void) {
    
15.     s.insert(0x7ffffff);
    
16.     s.insert(-0x7ffffff);
    
17. 
    
18.     cin >> n;
    
19.     for(int i = 1; i <= n; i++) {
    
20.         cin >> x;
    
21.         if(s.size() == 2) {
    
22.             ans += x;
    
23.             s.insert(x);
    
24.         } else {
    
25.             k = s.lower_bound(x);
    
26.             if(*k != x) {
    
27.                 a = k;
    
28.                 a--;
    
29.                 ans += min(abs(*k - x), abs(*a - x));
    
30.                 insert(x);
    
31.             }
    
32.         }
    
33.     }
    
34. 
    
35.     cout << ans << endl;
    
36.    
    
37.     return 0;
    
38. }
    

复制代码

另外题解区还要大佬直接用的排序暴力过的，但是我看不懂他是怎么写的。。。

Ewan-Ahiouy

大佬！快来膜拜！

                               
登录/注册后可看大图