2023.3.19 模拟赛题解()

银行取款

题意

  • 在现代文明社会中，大家在诸如银行办理业务、车站买票等活动时都很文明，没有插队的现象，本着”先来先服务”的规矩。
  • 初赛已经结束了，凡凡的爸爸打算上银行去取点钱，带着初赛考得很好的凡凡上街购物，凡凡的爸爸到银行时发现很多人在办理业务，凡凡的爸爸就自觉地在排队机上去了一个业务号码，并焦急的等待着银行柜台叫自己的号码……
  • 输入有若干行，每一行包含 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\)，依然不想写字符串哈希，用 得了。

map
#include <map>
#include <stack>
#include <string>
#include <iostream>
std::map<std::string,bool>q;
std::stack<std::string>st;
std::string inp;
int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int n;
	std::cin>>n;
	while(n--)
	{
		std::cin>>inp;
		st.push(inp);
	}
	while(!st.empty())
	{
		if(!q.count(st.top()))
		{
			q[st.top()]=true;
			std::cout<<st.top()<<'\n';
		}
		st.pop();
	}
	return 0;
}
————————

银行取款

题意

  • 在现代文明社会中，大家在诸如银行办理业务、车站买票等活动时都很文明，没有插队的现象，本着”先来先服务”的规矩。
  • 初赛已经结束了，凡凡的爸爸打算上银行去取点钱，带着初赛考得很好的凡凡上街购物，凡凡的爸爸到银行时发现很多人在办理业务，凡凡的爸爸就自觉地在排队机上去了一个业务号码，并焦急的等待着银行柜台叫自己的号码……
  • 输入有若干行，每一行包含 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\)，依然不想写字符串哈希，用 得了。

map
#include <map>
#include <stack>
#include <string>
#include <iostream>
std::map<std::string,bool>q;
std::stack<std::string>st;
std::string inp;
int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int n;
	std::cin>>n;
	while(n--)
	{
		std::cin>>inp;
		st.push(inp);
	}
	while(!st.empty())
	{
		if(!q.count(st.top()))
		{
			q[st.top()]=true;
			std::cout<<st.top()<<'\n';
		}
		st.pop();
	}
	return 0;
}