题单二总结DAY04

---

学习内容

1.B3616
2.P5266
3.P4305

---

一、题目

B3616 【模板】队列

题目描述

请你实现一个队列（queue），支持如下操作：

• push(x)：向队列中加入一个数 $x$。
• pop()：将队首弹出。如果此时队列为空，则不进行弹出操作，并输出 ERR_CANNOT_POP。
• query()：输出队首元素。如果此时队列为空，则输出 ERR_CANNOT_QUERY。
• size()：输出此时队列内元素个数。

输入格式

第一行，一个整数 $n$，表示操作的次数。

接下来 $n$ 行，每行表示一个操作。格式如下：

• 1 x，表示将元素 x 加入队列。
• 2，表示将队首弹出队列。
• 3，表示查询队首。
• 4，表示查询队列内元素个数。

输出格式

输出若干行，对于每个操作，按「题目描述」输出结果。

每条输出之间应当用空行隔开。

输入输出样例 #1

输入 #1

13
1 2
3
4
1 233
3
2
3
2
4
3
2
1 144
3

输出 #1

2
1
2
233
0
ERR_CANNOT_QUERY
ERR_CANNOT_POP
144

说明/提示

样例解释

首先插入 2，队首为 2、队列内元素个数为 1。
插入 233，此时队首为 2。
弹出队首，此时队首为 233。
弹出队首，此时队首为空。
再次尝试弹出队首，由于队列已经为空，此时无法弹出。
插入 144，此时队首为 144。

数据规模与约定

对于 $100\%$ 的测试数据，满足 $n\le 10000$，且被插入队列的所有元素值是 $[1,1000000]$ 以内的正整数。

Tips

queue 是 push 和 pop 以及 front

完整代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	int n;
	cin>>n;
	int s;
	queue<int>b;
	while(n--){
		cin>>s;
		if(s==1){
			int k=0;
			cin>>k;
			b.push(k);	
		}else if(s==2){
			if(b.empty()){
				cout<<"ERR_CANNOT_POP"<<endl;
			}else{
				b.pop();	
			}
		}else if(s == 3){
			if(b.empty()){
				cout<<"ERR_CANNOT_QUERY"<<endl;
			}else{
				cout<<b.front()<<endl;	
			}
		}else if(s == 4){
			cout<<b.size()<<endl;
		}
		
	}
	return 0;
} 

P5266 【深基17.例6】学籍管理

题目描述

您要设计一个学籍管理系统，最开始学籍数据是空的，然后该系统能够支持下面的操作（不超过 $10^5$ 条）：

• 插入与修改，格式 1 NAME SCORE：在系统中插入姓名为 $\text{NAME}$(由字母和数字组成不超过 $20$ 个字符的字符串，区分大小写)，分数为 $\text{SCORE}$（$0<\text{SCORE}<2^{31}$） 的学生。如果已经有同名的学生则更新这名学生的成绩为 $\text{SCORE}$。如果成功插入或者修改则输出 OK。
• 查询，格式 2 NAME：在系统中查询姓名为 $\text{NAME}$ 的学生的成绩。如果没能找到这名学生则输出 Not found，否则输出该生成绩。
• 删除，格式 3 NAME：在系统中删除姓名为 $\text{NAME}$ 的学生信息。如果没能找到这名学生则输出 Not found，否则输出 Deleted successfully。
• 汇总，格式 4：输出系统中学生数量。

输入格式

第一行，输入一个正整数 $Q$（$1\le Q\le 10^5$），表示操作数量。

接下来 $Q$ 行，每行先输入一个正整数 $op$（$op\in [1,4]$），表示操作种类。接着：

• 如果 $op=1$，则再输入一个字符串 $\text{NAME}$ 以及一个正整数 $\text{SCORE}$，含义见题目描述。
• 如果 $op=2$，则再输入一个字符串 $\text{NAME}$，含义见题目描述。
• 如果 $op=3$，则再输入一个字符串 $\text{NAME}$，含义见题目描述。
• 如果 $op=4$，则无需再输入其他内容。

输出格式

共输出 $Q$ 行，每行输出一个字符串或正整数，为对应操作的处理结果，具体含义见题目描述。

输入输出样例 #1

输入 #1

5
1 lxl 10
2 lxl
3 lxl
2 lxl
4

输出 #1

OK
10
Deleted successfully
Not found
0

Tips

这题 map unordered_map 都行
auto it = a.find(name);查找

完整代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
//	unordered_map<string,int>a;
	map<string,int>a;
	int Q=0 , t =0 ;
	string name ="";
	cin>>Q;
	while(Q--){
		int x =0  ;
		cin>>x;
		if(x==1){
			cin>>name;
			cin>>t;
			a[name] = t;
			cout<<"OK"<<endl;		
		}
		if(x ==2){
			cin>>name;
			auto it = a.find(name);
			if(it == a.end()){
				cout<<"Not found"<<endl;		
			}else{
				cout<<a[name]<<endl;
			}
		}
		if(x == 3){
			cin>>name;
			auto it = a.find(name);
			if(it == a.end()){
				cout<<"Not found"<<endl;
			}else{
				a.erase(name);
				cout<<"Deleted successfully"<<endl;	
			}
					
		}
		if(x == 4){
			
			cout<<a.size()<<endl;
		}
	}
	return 0;
}

P4305 [JLOI2011] 不重复数字

题目描述

给定 $n$ 个数，要求把其中重复的去掉，只保留第一次出现的数。

输入格式

本题有多组数据。

第一行一个整数 $T$，表示数据组数。

对于每组数据：

第一行一个整数 $n$。

第二行 $n$ 个数，表示给定的数。

输出格式

对于每组数据，输出一行，为去重后剩下的数，两个数之间用一个空格隔开。

输入输出样例 #1

输入 #1

2
11
1 2 18 3 3 19 2 3 6 5 4
6
1 2 3 4 5 6

输出 #1

1 2 18 3 19 6 5 4
1 2 3 4 5 6

说明/提示

对于 $30\%$ 的数据，$n\le 100$，给出的数 $\in [0,100]$。

对于 $60\%$ 的数据，$n\le 10^4$，给出的数 $\in [0,10^4]$。

对于 $100\%$ 的数据，$1\le T\le 50$，$1\le n\le 5\times 10^4$，给出的数在 $32$ 位有符号整数范围内。

Tips

只能用unordered_set<int>a;因为set会给值排序 不符合要求

完整代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
unordered_set<int>a;
signed main(){
	int n=0;
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	
	while(n--){
		int flag =1;
		int x;
		cin>>x;
		for(int i =0;i<x;i++){
			int k =0;
			cin>>k;
			if(a.find(k)==a.end()){
				if(flag){
					cout<<k;
					flag =0;
				}else{
					cout<<" "<<k;
				}
				a.insert(k);	
			}
			
		}
		cout<<endl;
		a.clear();
	}
	return 0;
}