栈与队列解题报告

刚考完试。重返oi！
这次挂掉80pts 20pts挂在T1,未考虑读的时候数字占多个字符， 60pts挂在多测未清空上。

T1

https://www.luogu.com.cn/problem/P1981
经典表达式求值。我这里采用了一种比较奇特的方法。我以每个加号为分界线。当我遍历到其中一个加号时，保证加号之前只有一个数。然后在遍历到下一个加号时，式子就是x + x * x + ,于是就可以倒着算了。
当然也可以先算乘法，最后把加法加起来。

代码

 #include <iostream>
 #include <cstdio>
 #include <algorithm>
 #include <cstring>
 
//表达式求值
//时间 40min
using namespace std;
 
const int N = 1000010;
 

char str[N];
int num[N], tt_num = -1;
int op[N], tt_op = -1;
int n;

void eval(int opretion, int a, int b)
{
	//cout << a << endl << b << opretion << endl;
	if (opretion == 1) num[ ++ tt_num] = ((a % 10000) + (b % 10000)) % 10000;
	else num[ ++ tt_num] = ((a % 10000) * (b % 10000)) % 10000;
} 

int main()
{
	cin >> str + 1;
	
	n = strlen(str + 1);
	
	int x = 0;
	for (int i = 1; i <= n; i ++ )
	{
		if ('0' <= str[i] && str[i] <= '9')
			x = x * 10 + str[i] - '0';
		else if (str[i] == '+')
		{
			num[ ++ tt_num] = x % 10000;
			x = 0; //清0 
			//只要是加法 前面必须算尽 
			while (tt_op >= 0) 
			{
				if (tt_num <= 0) break; //前面没有或者只有一个数 没必要取出算 
				int num1 = num[tt_num -- ];
				int num2 = num[tt_num -- ]; 
				eval(op[tt_op], num1, num2); 
				tt_op -- ;
			}
			op[ ++ tt_op] = 1;
		}
		else
		{
		 	op[ ++ tt_op] = 2; //乘法直接算
		 	num[ ++ tt_num] = x % 10000;
		 	x = 0; 
		}
		//这样保证了两个加直接只有乘 第一个加前面只有一个数 
	}
	num[ ++ tt_num] = x % 10000; //最后一个数哦
	
	//一定是x + x * x 的形式了
	while (tt_op >= 0) 
	{
		if (tt_num <= 0) break; //前面没有或者只有一个数 没必要取出算 
		int num1 = num[tt_num -- ];
		int num2 = num[tt_num -- ]; 
		eval(op[tt_op], num1, num2);
		tt_op -- ;
	}
	//无脑从后往前算就行 
	
	printf("%d\n", num[tt_num]);
	
	return 0;
} 

T2

https://www.luogu.com.cn/problem/P1540
这题可以直接模拟的。模拟查单词的过程，每到一个新单词，维护他的状态，如果内存有，那我们大可直接拿来用。如果内存没有。我们要先看看内存满了没，如果满了，我们要弹出，然后在加入。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

//10min

const int N = 1010;

int q[N], hh, tt = -1;
int res, m, n;
bool st[N];

int main()
{
	scanf("%d%d", &m, &n);
	
	for (int i = 1; i <= n; i ++ )
	{
		int num;
		scanf("%d", &num);
		if (st[num]) continue; //有了 
		
		if (tt - hh + 1 == m) //满了 
		{
			st[q[hh]] = false;
			hh ++ ; 
		}
		q[ ++ tt] = num;
		st[num] = true;
		res ++ ;
	}
	
	printf("%d\n", res);
	
	return 0;
}

T3

https://www.luogu.com.cn/problem/P4387

这题多测。记得清空。
我们直接一个数一个数进，我们发现。出栈当且仅当 出栈队列中的数==栈顶。并且与后面数无关，于是我们考虑不断满足出栈序列，直接模拟进栈过程，那么该出就出，最后统计答案。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

//验证栈序列 25min 

using namespace std;

const int N = 100010, INF = 0x3f3f3f3f;

int stk[N], tt = 0;
int n, m;
int in[N], out[N];

int main()
{
	scanf("%d", &m);
	while (m -- )
	{ 
	    tt = 0;
		scanf("%d", &n);
		
		for (int i = 1; i <= n; i ++ ) scanf("%d", &in[i]);
		for (int i = 1; i <= n; i ++ ) scanf("%d", &out[i]);
		//out[n + 1] = INF; //当做边界 
		int b = 0; //目前满足到出栈哪个位置了 
		for (int i = 1; i <= n; i ++ )
		{
			stk[ ++ tt] = in[i];//入栈 
			while (tt > 0 && stk[tt] == out[b + 1]) b ++ , tt -- ; //能出就出 
		}
		
		if (b >= n) puts("Yes"); //能够全部满足 
		else puts("No"); 
	}
	
	return 0; 
}

T4

单调队列板子。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

//滑动窗口 20min 
const int N = 1000010;

int q[N], hh, tt = -1;
int n, k, a[N];
 
int main()
{
	scanf("%d%d", &n, &k);
	
	//求min 
	for (int i = 1; i <= n; i ++ )
	{
		scanf("%d", &a[i]);
		while (hh <= tt && q[hh] <= i - k) hh ++ ;
		while (hh <= tt && a[q[tt]] >= a[i]) tt -- ;
		q[ ++ tt] = i;
		if (i >= k) printf("%d ", a[q[hh]]);
	}
	puts("");
	
	//求max
	hh = 0, tt = -1; 
	for (int i = 1; i <= n; i ++ )
	{
		while (hh <= tt && q[hh] <= i - k) hh ++ ;
		while (hh <= tt && a[q[tt]] <= a[i]) tt -- ;
		q[ ++ tt] = i;
		if (i >= k) printf("%d ", a[q[hh]]);
	}
	
	return 0;
}