M 海运公司最近要对旗下仓库的货物进出情况进行统计。目前他们所拥有的唯一记录就是一个记录集装箱进出情况的日志。该日志记录了两类操作：第一类操作为集装箱入库操作，以及该次入库的集装箱重量；第二类操作为集装箱的出库操作。这些记录都严格按时间顺序排列。集装箱入库和出库的规则为先进后出，即每次出库操作出库的集装箱为当前在仓库里所有集装箱中最晚入库的集装箱。

出于分析目的，分析人员在日志中随机插入了若干第三类操作――查询操作。分析日志时，每遇到一次查询操作，都要报告出当前仓库中最大集装箱的重量。

输入：第一行一个整数n表示操作次数，接下来n行每行一个操作，如果是”0 x”则表示入库一个重量为x的货物，如果是”1”表示出库，如果是”2”表示查询。

输出：若干行，对每个操作”2”，输出一行一个整数表示对应的结果。

一眼栈，不过要求栈内元素最大值。 这个也好做，直接再开个栈记录最大值就可以了。

设a是原栈，b是最大值栈，那么a加入元素x时，b加入max(b.top(),x)，a删除时b跟着删除，每次查询的答案就是b的栈顶。

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

本题的运算只有四则运算，所有运算的法则跟C++中的一致。

给定一个后缀表达式，请求出它的结果。

输入：一个字符串表示这个后缀表达式。其中@为表达式的结束符号，.为操作数的结束符号。如3*(5-2)+7的后缀表达式为3.5.2.-*7.+@。

输出：一个整数表示答案。

直接用栈来模拟就可以。

先读入字符串，遇到数字就用类似快读的方法求值，遇到小数点的时候就把现在这个数字放进栈里面。如果遇到运算符号，就把栈里的头两个数取出，第一个作为右端运算数字，第二个作为左端运算数字得到结果，再把结果放进栈里面。最后得到的结果就是答案。

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

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

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

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

输入：共 2 行。每行中两个数之间用一个空格隔开。第一行为两个正整数 M,N，代表内存容量和文章的长度。第二行为 N 个非负整数，按照文章的顺序，每个数（大小不超过 1000）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。

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

直接用队列模拟，只要有入队操作就让查字典的计数器cnt++即可。

开一个vis数组记录当前数字是否在队列中。 读入整数x时，如果vis[x]为假，说明它原本不在队列中，我们将其入队，并将vis[x]设置为真，且cnt++。如果入队后队列元素个数超过了m，那么我们让队首front出队，并令vis[front]为假。

否则，直接跳过本次操作。

爱与愁大神买完东西后，打算坐车离开中山路。现在爱与愁大神在 (x1,y1)处，车站在 (x2,y2) 处。现在给出一个 n×n(n≤1000) 的地图，0 表示马路，1 表示店铺（不能从店铺穿过），爱与愁大神只能垂直或水平着在马路上行进。爱与愁大神为了节省时间，他要求最短到达目的地距离（每两个相邻坐标间距离为 1）。你能帮他解决吗？

输入：第一行一个正整数n，接下来n行每行一个长为n的，只包含0和1的字符串，最后一行四个整数x1,y1,x2,y2。

输出：一个整数表示答案。

BFS板子题。

实现BFS的基础就是队列，因此直接用队列做就行。

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

输入：

输出：

本题有两个做法：一是模拟，二是链表。 先讲模拟做法。

模拟做法就是直接不断让下标从1跑到n，每跑到还没标记的m个就将这个数输出并标记，这样就直接做完了。

而链表做法可以用一个循环链表来解决，每在链表里遍历到第m个就输出并删除。链表的删除操作比较方便，总的遍历次数会比直接模拟小。

输入：

输出：

首先每个格子可能会重复染色，那么我们考虑一个操作序列，使得我们可以将所有操作转化为t=0的操作。这样的话统计会方便很多，因为每次涂完整行整列之后我们可以更新剩下的行列数量来直接算出这次涂了多少格。

那么我们先倒序执行所有t=1的操作，再顺序执行所有t=0的操作即可。 现在问题是统计，我们不仅要统计数量，还要记录那些已经涂过色的行列。

模拟做法就是直接不断让下标从1跑到n，每跑到还没标记的m个就将这个数输出并标记，这样就直接做完了。

而链表做法可以用一个循环链表来解决，每在链表里遍历到第m个就输出并删除。链表的删除操作比较方便，总的遍历次数会比直接模拟小。

真正的做法是对行列各开一个链表nxtr,nxtc，分别记录这个行列之后第一个没有被完全染色的行列。那么我们可以在每次更新的时候将区间内所有点标记为已染色，且更新nxtr和nxtc，这样链表每次跳的时候都会自动跳过那些已经完全染色的行列，时间复杂度均摊至线性。

# include<iostream>
using namespace std;

const int N=1e5+5,inf=1e5+1;
int n,m,x,k;
bool f[N],p;
int pre[N],nxt[N],head=1;

int main(){
	cin>>n;
	pre[1]=nxt[1]=inf;
	for(int i=2;i<=n;++i){
		cin>>k>>p;
		if(p){
			pre[nxt[k]]=i;
			nxt[i]=nxt[k];
			nxt[k]=i;
			pre[i]=k;
		}
		else{
			nxt[pre[k]]=i;
			pre[i]=pre[k];
			pre[k]=i;
			nxt[i]=k;
			if(k==head) head=i;
		}
	}
	cin>>m;
	for(int i=1;i<=m;++i){
		cin>>x;
		f[x]=1;
	}
	for(int i=head;i!=inf;i=nxt[i])
		if(!f[i]) cout<<i<<" ";
	return 0;
}

# include<iostream>
using namespace std;

const int N=103;
int n,m,nxt[N],cnt=1,k=1;

int main(){
	cin>>n>>m;
	if(m==1){
		for(int i=1;i<=n;++i)
			cout<<i<<" ";
		return 0;
	}
	for(int i=1;i<=n;++i)
		nxt[i]=(i==n?1:i+1);
	while(nxt[k]!=k){
		if(cnt==m-1){
			cout<<nxt[k]<<" ";
			nxt[k]=nxt[nxt[k]];
			cnt=0;
		}
		k=nxt[k];
		cnt++;
	}
	cout<<k;
	return 0;
}