线性表

洛谷刷题7

【深基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

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

样例输出 #1

1
8
5

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
int main()	
{
	int n, m ,temp;
	cin >> n >> m;
	vector<int>stu;
	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		stu.push_back(temp);

	}
	for (int i = 0; i < m; i++)
	{
		int x;
		cin >> x;
		cout << stu[x - 1]<<"\n";

	}


}

vector知识点

(1) vector<int> a(10); //定义了10个整型元素的向量（尖括号中为元素类型名，它可以是任何合法的数据类型），但没有给出初值，其值是不确定的。
   （2）vector<int> a(10,1); //定义了10个整型元素的向量,且给出每个元素的初值为1
   （3）vector<int> a(b); //用b向量来创建a向量，整体复制性赋值
   （4）vector<int> a(b.begin(),b.begin+3); //定义了a值为b中第0个到第2个（共3个）元素
   （5）int b[7]={1,2,3,4,5,9,8};
        vector<int> a(b,b+7); //从数组中获得初值
（1）a.assign(b.begin(), b.begin()+3); //b为向量，将b的0~2个元素构成的向量赋给a
    （2）a.assign(4,2); //是a只含4个元素，且每个元素为2
    （3）a.back(); //返回a的最后一个元素
    （4）a.front(); //返回a的第一个元素
    （5）a[i]; //返回a的第i个元素，当且仅当a[i]存在2013-12-07
    （6）a.clear(); //清空a中的元素
    （7）a.empty(); //判断a是否为空，空则返回ture,不空则返回false
    （8）a.pop_back(); //删除a向量的最后一个元素
    （9）a.erase(a.begin()+1,a.begin()+3); //删除a中第1个（从第0个算起）到第2个元素，也就是说删除的元素从a.begin()+1算起（包括它）一直到a.begin()+         3（不包括它）
    （10）a.push_back(5); //在a的最后一个向量后插入一个元素，其值为5
    （11）a.insert(a.begin()+1,5); //在a的第1个元素（从第0个算起）的位置插入数值5，如a为1,2,3,4，插入元素后为1,5,2,3,4
    （12）a.insert(a.begin()+1,3,5); //在a的第1个元素（从第0个算起）的位置插入3个数，其值都为5
    （13）a.insert(a.begin()+1,b+3,b+6); //b为数组，在a的第1个元素（从第0个算起）的位置插入b的第3个元素到第5个元素（不包括b+6），如b为1,2,3,4,5,9,8         ，插入元素后为1,4,5,9,2,3,4,5,9,8
    （14）a.size(); //返回a中元素的个数；
    （15）a.capacity(); //返回a在内存中总共可以容纳的元素个数
    （16）a.resize(10); //将a的现有元素个数调至10个，多则删，少则补，其值随机
    （17）a.resize(10,2); //将a的现有元素个数调至10个，多则删，少则补，其值为2
    （18）a.reserve(100); //将a的容量（capacity）扩充至100，也就是说现在测试a.capacity();的时候返回值是100.这种操作只有在需要给a添加大量数据的时候才         显得有意义，因为这将避免内存多次容量扩充操作（当a的容量不足时电脑会自动扩容，当然这必然降低性能） 
    （19）a.swap(b); //b为向量，将a中的元素和b中的元素进行整体性交换
    （20）a==b; //b为向量，向量的比较操作还有!=,>=,<=,>,<
（1）sort(a.begin(),a.end()); //对a中的从a.begin()（包括它）到a.end()（不包括它）的元素进行从小到大排列
（2）reverse(a.begin(),a.end()); //对a中的从a.begin()（包括它）到a.end()（不包括它）的元素倒置，但不排列，如a中元素为1,3,2,4,倒置后为4,2,3,1
（3）copy(a.begin(),a.end(),b.begin()+1); //把a中的从a.begin()（包括它）到a.end()（不包括它）的元素复制到b中，从b.begin()+1的位置（包括它）开        始复制，覆盖掉原有元素
（4）find(a.begin(),a.end(),10); //在a中的从a.begin()（包括它）到a.end()（不包括它）的元素中查找10，若存在返回其在向量中的位置
//链接：
https://blog.csdn.net/wkq0825/article/details/82255984

错误地方

vector<int> a;
for(int i=0;i<10;i++)
    a[i]=i;

【深基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

5 4
1 3 10000 118014
1 1 1 1
2 3 10000
2 1 1

样例输出 #1

118014
1

提示

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

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
	vector<vector<int> >a;
	int opt;
	int i, j, k, n, q;
	cin >> n >> q;
	a.resize(n + 1);
	

	for (int x = 0; x < q; x++)
	{
		cin >> opt;
		if (opt==1)
		{
			cin >> i >> j >> k;
			if (a[i].size()<j+1)
			{
				a[i].resize(j + 1);
			}
			a[i][j] = k;
		}
		else
		{
			cin >> i >> j;
			cout << a[i][j] << endl;
		}
	}

}

后缀表达式

题目描述

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

本题中运算符仅包含 \(\texttt{+-*/}\)。保证对于 \(\texttt{/}\) 运算除数不为 0。特别地，其中 \(\texttt{/}\) 运算的结果需要向 0 取整（即与 C++ / 运算的规则一致）。

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

3.5.2.-*7.+@

样例输出 #1

16

样例 #2

样例输入 #2

10.28.30./*7.-@

样例输出 #2

-7

提示

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

#include<string>
#include<algorithm>
#include<string>
#include<stack>
#include<iostream>

using namespace std;
stack < int > n;
int s = 0;
int x, y;
int main()
{
	char ch;
	do
	{
		ch = getchar();
		if (ch>='0'&&ch<='9')
		{
			s = s * 10 + ch - '0';

		}
		else if (ch=='.')
		{
			n.push(s);
			s = 0;
		}
		else if(ch!='@')
		{
			x = n.top();
			n.pop();
			y = n.top();
			n.pop();
			switch (ch)
			{
			case '+':n.push(x + y); break;
			case '-':n.push(y - x); break;
			case '*':n.push(x * y); break;
			case '/':n.push(y/x); break;	
			}
		}

	} while (ch!='@');
    cout<< n.top();

}

栈知识点

栈是一个先入后出的有序列表 栈中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top),另一端为固定的一端，称为栈底(Bottom) 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除

#include <bits/stdc++.h>
#include <stack>
using namespace std;
int main(){
	stack<int> st;
	for(int i = 0; i < 5; i++){
		st.push(i);
	}
	cout<<st.top()<<endl;
	return 0;
} 
3. stack常用函数实例解析
(1). push(x) 将x入栈
(2). top() 获得栈顶元素
(3). pop() 用以弹出栈顶元素
(4). empty() 可以检测stack内是否为空，返回true为空，返回false为非空
(5). size() 返回stack内元素的个数

约瑟夫问题

题目描述

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

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

输入格式

输入两个整数 \(n,m\)。

输出格式

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

样例 #1

样例输入 #1

10 3

样例输出 #1

3 6 9 2 7 1 8 5 10 4

提示

\(1 \le m, n \le 100\)

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
queue < int>q;
int n, k;
int main()
{
	cin >> n >> k;
	for (int i =1; i <=n ; i++)
	{
		q.push(i);
	}
	while (q.size()!=0)
	{
		for (int i = 1; i < k; i++)
		{
			q.push(q.front());
			q.pop();

		}
		cout << q.front()<<" ";
		q.pop();
	}
}

queue队列详解

C++队列Queue类成员函数如下:

back()返回最后一个元素

empty()如果队列空则返回真

front()返回第一个元素

pop()删除第一个元素

push()在末尾加入一个元素

size()返回队列中元素的个数

队列安排

题目描述

一个学校里老师要将班上 \(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

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<M\leq N\leq 10^5\)。

//题解第一篇大佬的，
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int mx=1e5+10;
int n,m;
struct T{
    int l,r;        //每个同学的“左右手” 
	int d;          //表示同学是否输出 
}t[mx]={0};
void add(int i,int k,int f)       //新增同学 
{
    if(f==1)         //左 
    {
        t[k].r=t[i].r;
        t[k].l=i; 
        t[i].r=k;
        t[t[k].r].l=k;
        //一个双向链表的移动过程
    }
    else             //右 
    {
        t[k].r=i;
        t[k].l=t[i].l;
        t[i].l=k;
        t[t[k].l].r=k;
    }
}
int main()
{
    int x,k,f;
    cin>>n;
    t[0].r=0,t[0].l=0;
    add(0,1,1);
    for (int i=2;i<=n;i++)
    {
        cin>>x>>f;
        add(x,i,f);
    }
    cin>>m;
    while(m--)
    {
        cin>>x;
        t[x].d=1;         //将该同学标记为不输出 
    }
    for (int i=t[0].r;i;i=t[i].r)
    {
        if (t[i].d==0)    //输出未标记的 
          cout<<i<<" ";
    }
    return 0;
}

[NOIP2010 提高组] 机器翻译

题目背景

NOIP2010 提高组 T1

题目描述

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

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

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

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

输入格式

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

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

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

输出格式

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

样例 #1

样例输入 #1

3 7
1 2 1 5 4 4 1

样例输出 #1

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\)。

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int n, m, ans;
int mark[1005];
int t;
queue <int>q;

int main()
{
	cin >> m >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> t;
		if (mark[t]==1)
		{
			continue;
		}
		if (q.size()<m)
		{
			q.push(t);
			mark[t] = 1;
			ans++;
		}
		else
		{
			mark[q.front()] = 0;
			q.pop();
			q.push(t);
			mark[t] = 1;
			ans ++;
		}


	}

	cout << ans;
}
//哈希存储，队列弹出

[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\)，$ ^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

3
1 4 4 1 2 2
2 2 2 3
10 1 3

样例输出 #1

3
4
4

样例 #2

样例输入 #2

4
1 4 1 2 2 3
3 2 2 3
86401 2 3 4
86402 1 5

样例输出 #2

3
3
3
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\)。

  #include<iostream>
  #include<algorithm>
  #include<queue>
  using namespace std;  
  struct people
  {
  	int t, x;
  };
  //放入时间和国家
  int ct[1000000];
  int ans;
  int n, t, k, tep;
  queue<people>q;
  int main()
  {
  	people p;
  
  	cin >> n;
  	for (int i = 0; i < n; i++)
  	{
  		cin >> t >> k;
  		for (int j = 0; j < k; j++)
  		{
  			cin >> tep;
  			if (ct[tep]==0)
  			{
  				ans++;
  				
  			}
  			ct[tep]++;
  			q.push({ t,tep });
  		}
  		p = q.front();
  		while (t-p.t>=86400)
              //表示过了一天，人要走了
  		{
  			ct[p.x]--;
  			if (ct[p.x]==0)
  			{
  				ans--;
  			}
  			q.pop();
  			p = q.front();
  		}
  		cout << ans << "\n";
  	}
  
  
  
  	return 0;
  }

# 括号序列

题目描述

定义如下规则：

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

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

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

而以下几个则不是：

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

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

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

输入格式

输入只有一行一个字符串，表示 \(s\)。

输出格式

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

样例 #1

样例输入 #1

([()

样例输出 #1

()[]()

样例 #2

样例输入 #2

([)

样例输出 #2

()[]()

提示

数据规模与约定

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

#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<string>
using namespace std;
struct point
{
	char c;
	int pos;
};
bool mark[105];
int main()
{
	string s;
	stack<point>p_s;
		cin >>s;
		for (int i = 0; i < s.size(); i++)
		{
			if (s[i] == '(' || s[i] == '[')
			{
				p_s.push({ s[i], i });
				continue;
			}
			if (p_s.empty())
			{
				continue;
			}
			point p = p_s.top();
			if (s[i] == ')' && p.c == '(' || s[i] == ']' && p.c == '[')
			{
				mark[i] = 1;
                //标记自己
				mark[p.pos] = 1;
                //标记离自己最近的那个点
				p_s.pop();
			}
			else
			{
				continue;
			}
	}
		for (int i = 0; i < s.size(); i++)
		{
			if (mark[i]==1)
			{
				cout << s[i];
			}
			else if (s[i]=='('||s[i]==')')
				{
					cout << "()";
				}
			else
			{
				cout << "[]";
			}
		}
}

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

题目描述

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

输入格式

第一行一个整数 \(q\)，询问次数。

接下来 \(q\) 个询问，对于每个询问：

第一行一个整数 \(n\) 表示序列长度；

第二行 \(n\) 个整数表示入栈序列；

第三行 \(n\) 个整数表示出栈序列；

输出格式

对于每个询问输出答案。

样例 #1

样例输入 #1

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

样例输出 #1

Yes
No

#include<iostream>
#include<stack>
using namespace std;
int a[1000000];
int b[1000000];

void solve()
{
	stack<int>s;
	int n;
	int now=0;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	for (int i = 0; i < n; i++)
	{
		cin >> b[i];
	}
	for (int i = 0; i < n; i++)
	{
		if (s.empty())
		{
			s.push(a[now++ ]);
		}
		while (b[i]!=s.top()&&now<n)
		{
			s.push(a[now++]);

			//缩减代码量
		}
        //不等于你就加，等于你就不加
        //因为符合栈的规律，你肯定有一个节点相同的，然后不断这样
		if (b[i]==s.top())
		{
			s.pop();
		}
		else
		{
			cout << "No"<<'\n';
			return;
		}

	}
	cout << "Yes"<<"\n";

}
int main()
{
	int q;
	cin >> q;
	while (q--)
	{
		solve();


	}


	return 0;
}

[HNOI2002] 营业额统计

题目描述

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

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

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

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

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

6
5
1
2
5
4
6

样例输出 #1

12

提示

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

#include<iostream>
#include<set>
#include<algorithm>
#include<string>
using namespace std;
int main()
{
	int ans = 0, x, n, l, r;

	set<int>q;
	set<int>::iterator lit, rit;
	cin >> n >> ans;
	q.insert(ans);
	for (int i = 2; i <=n ; i++)
	{
		cin >> x;
		rit = q.lower_bound(x);
		lit = --q.lower_bound(x);
		l = *lit;
		r = *rit;
		if (rit==q.begin())
		{
			ans+=abs(r - x);
		}
		else if (rit==q.end())
		{
			ans += abs(l - x);
		}
		else
        {
			ans+=min(abs(l - x), abs(r - x));
		}
		q.insert(x);
	}
	cout << ans;
}