银行取款
题意
- 在现代文明社会中，大家在诸如银行办理业务、车站买票等活动时都很文明，没有插队的现象，本着"先来先服务"的规矩。
- 初赛已经结束了，凡凡的爸爸打算上银行去取点钱，带着初赛考得很好的凡凡上街购物，凡凡的爸爸到银行时发现很多人在办理业务，凡凡的爸爸就自觉地在排队机上去了一个业务号码，并焦急的等待着银行柜台叫自己的号码......
- 输入有若干行，每一行包含
I（表示等待办理业务）和顾客的序号；或者 是O（表示办理完业务的人离开）。 - 输出银行排队中出队顾客序列，若队列为空（没人等待），则输出 "None"。
- 输入不超过 \(10^3\) 行。
题解
显然是队列板子题。
维护一个队列 q，这里偷懒用容器 std::queue。
I 操作相当于 q.push(...)，O 操作相当于输出 q.front()，然后 q.pop()。注意队列特判为空。
#include <queue>
#include <stdio.h>
class reque// 瞎封装一个吧，好看一点。
{
private:
std::queue<int> q;
public:
void insert(int val)
{
q.push(val);
return ;
}
void erase()
{
if(q.empty())
puts("None");
else
{
printf("%d\n",q.front());
q.pop();
}
return ;
}
}q;
char opt[3];
int main()
{
int id;
while(~scanf("%s",opt))//单个字符转化成字符串，避免不可见字符问题。
{
if(opt[0]=='O')
{
q.erase();
}else
{
scanf("%d",&id);
q.insert(id);
}
}
return 0;
}
聊天列表
题意
- Smart 热衷于在社交网络上消磨时间。他在他最喜欢的网络中创建一个带有聊天列表的页面，这样当他向某个朋友发送消息时，他朋友的聊天内容就会上升到聊天列表的顶部。
- 其他聊天的相对顺序没有改变。如果之前没有与这个朋友的聊天记录，那么一个新的聊天记录就会被插入到列表的顶部。
- 假设聊天列表最初为空，给定 Smart 发消息的顺序，在处理完他的所有消息后，输出生成的聊天列表。
- \(n\le 2\times 10^5\)。
题解
首先将给定的聊天序列压入一个栈。
从栈顶开始扫，如果一个名字是第一次出现，则输出；反之忽略。
手模发现大概是正确的。
怎么实现呢，虽然给定 \(\forall str,|str| \le 10\)，依然不想写字符串哈希，用 umap 得了。