题单二总结DAY06

---

学习内容

1.P1540
2.P2058
3.P1923

---

一、题目

P1540 [NOIP 2010 提高组] 机器翻译

题目背景

NOIP2010 提高组 T1

题目描述

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

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

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

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

输入格式

共 $2$ 行。每行中两个数之间用一个空格隔开。

第一行为两个正整数 $M,N$，代表内存容量和文章的长度。

第二行为 $N$ 个非负整数，按照文章的顺序，每个数（大小不超过 $1000$）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。

输出格式

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

输入输出样例 #1

输入 #1

3 7
1 2 1 5 4 4 1

输出 #1

5

说明/提示

样例解释

整个查字典过程如下：每行表示一个单词的翻译，冒号前为本次翻译后的内存状况：

1. 1：查找单词 1 并调入内存。
2. 1 2：查找单词 2 并调入内存。
3. 1 2：在内存中找到单词 1。
4. 1 2 5：查找单词 5 并调入内存。
5. 2 5 4：查找单词 4 并调入内存替代单词 1。
6. 2 5 4：在内存中找到单词 4。
7. 5 4 1：查找单词 1 并调入内存替代单词 2。

共计查了 $5$ 次词典。

数据范围

• 对于 $10\%$ 的数据有 $M=1$，$N\le 5$；
• 对于 $100\%$ 的数据有 $1\le M\le 100$，$1\le N\le 1000$。

Tips

queue 没有查询功能
q.push(x); q.pop(); q.front(); q.size(); q.empty();

完整代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	int m=0,n=0;
	scanf("%d%d",&m,&n);
	list<int>a;
	int k=0;
	while(n--){
		int x=0;
		scanf("%d",&x);
		if(find(a.begin(),a.end(),x)==a.end()){
			if(a.size()!=m){
				a.push_back(x);
				k++;
			}else{
				a.pop_front();
				a.push_back(x);
				k++;	
			}
		}
				
	} 
	printf("%d\n",k);
	return 0;
}

P2058 [NOIP 2016 普及组] 海港

题目背景

NOIP2016 普及组 T3

题目描述

小 K 是一个海港的海关工作人员，每天都有许多船只到达海港，船上通常有很多来自不同国家的乘客。

小 K 对这些到达海港的船只非常感兴趣，他按照时间记录下了到达海港的每一艘船只情况；对于第 $i$ 艘到达的船，他记录了这艘船到达的时间 $t_i$ (单位：秒)，船上的乘客数 $k_i$，以及每名乘客的国籍 $x_{i,1},x_{i,2},\dots ,x_{i,k}$。

小K统计了 $n$ 艘船的信息，希望你帮忙计算出以每一艘船到达时间为止的 $24$ 小时（$24$ 小时 $=86400$ 秒）内所有乘船到达的乘客来自多少个不同的国家。

形式化地讲，你需要计算 $n$ 条信息。对于输出的第 $i$ 条信息，你需要统计满足 $t_i-86400<t_p\le t_i$ 的船只 $p$，在所有的 $x_{p,j}$ 中，总共有多少个不同的数。

输入格式

第一行输入一个正整数 $n$，表示小 K 统计了 $n$ 艘船的信息。

接下来 $n$ 行，每行描述一艘船的信息：前两个整数 $t_i$ 和 $k_i$ 分别表示这艘船到达海港的时间和船上的乘客数量，接下来 $k_i$ 个整数 $x_{i,j}$ 表示船上乘客的国籍。

保证输入的 $t_i$ 是递增的，单位是秒；表示从小K第一次上班开始计时，这艘船在第 $t_i$ 秒到达海港。

保证 $1\le n\le 10^5$，$\sum{k_i} \le 3\times 10^5 $ ，$1\le x_{i,j}\le 10^5$， $1\le t_{i-1}\le t_i\le 10^9$。

其中 $\sum k_i$ 表示所有的 $k_i$ 的和。

输出格式

输出 $n$ 行，第 $i$ 行输出一个整数表示第 $i$ 艘船到达后的统计信息。

输入输出样例 #1

输入 #1

3
1 4 4 1 2 2
2 2 2 3
10 1 3

输出 #1

3
4
4

输入输出样例 #2

输入 #2

4
1 4 1 2 2 3
3 2 2 3
86401 2 3 4
86402 1 5

输出 #2

3
3
3
4

说明/提示

【样例解释 1】

第一艘船在第 $1$ 秒到达海港，最近 $24$ 小时到达的船是第一艘船，共有 $4$ 个乘客，分别是来自国家 $4,1,2,2$，共来自 $3$ 个不同的国家；

第二艘船在第 $2$ 秒到达海港，最近 $24$ 小时到达的船是第一艘船和第二艘船，共有 $4+2=6$ 个乘客，分别是来自国家 $4,1,2,2,2,3$，共来自 $4$ 个不同的国家；

第三艘船在第 $10$ 秒到达海港，最近 $24$ 小时到达的船是第一艘船、第二艘船和第三艘船，共有 $4+2+1=7$ 个乘客，分别是来自国家 $4,1,2,2,2,3,3$，共来自 $4$ 个不同的国家。

【样例解释 2】

第一艘船在第 $1$ 秒到达海港，最近 $24$ 小时到达的船是第一艘船，共有 $4$ 个乘客，分别是来自国家 $1,2,2,3$，共来自 $3$ 个不同的国家。

第二艘船在第 $3$ 秒到达海港，最近 $24$ 小时到达的船是第一艘船和第二艘船，共有 $4+2=6$ 个乘客，分别是来自国家 $1,2,2,3,2,3$，共来自 $3$ 个不同的国家。

第三艘船在第 $86401$ 秒到达海港，最近 $24$ 小时到达的船是第二艘船和第三艘船，共有 $2+2=4$ 个乘客，分别是来自国家 $2,3,3,4$，共来自 $3$ 个不同的国家。

第四艘船在第 $86402$ 秒到达海港，最近 $24$ 小时到达的船是第二艘船、第三艘船和第四艘船，共有 $2+2+1=5$ 个乘客，分别是来自国家 $2,3,3,4,5$，共来自 $4$个 不同的国家。

【数据范围】

• 对于 $10\%$ 的测试点，$n=1,\sum k_i\le 10,1\le x_{i,j}\le 10,1\le t_i\le 10$。
• 对于 $20\%$ 的测试点，$1\le n\le 10,\sum k_i\le 100,1\le x_{i,j}\le 100,1\le t_i\le 32767$。
• 对于 $40\%$ 的测试点，$1\le n\le 100,\sum k_i\le 100,1\le x_{i,j}\le 100,1\le t_i\le 86400$。
• 对于 $70\%$ 的测试点，$1\le n\le 1000,\sum k_i\le 3000,1\le x_{i,j}\le 1000,1\le t_i\le 10^9$。
• 对于 $100\%$ 的测试点，$1\le n\le 10^5,\sum k_i\le 3\times 10^5,1\le x_{i,j}\le 10^5,1\le t_i\le 10^9$。

Tips

窗口问题 找到那个移动的地方就解决了

完整代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5+7;
int w[N];
int from[N];
int arrivaltime[N];
signed main(){
	int n;
	int r=0,s=0,i=1;
	scanf("%lld",&n);
	while(n--){
		int t,k;
		scanf("%lld%lld",&t,&k);
		while(k--){
			arrivaltime[++r]=t;
			scanf("%lld",&from[r]);
			if(!w[from[r]])s++; 
			w[from[r]]++;
		
		}
		while(t-arrivaltime[i]>=86400)if(--w[from[i++]]==0)s--;
		printf("%lld\n",s);
	} 
	
	return 0;
}

P1923 【深基9.例4】求第 k 小的数

题目描述

输入 $n$ 个数字 $a_i$，输出这些数字中第 $k$ 小的数。最小的数是第 $0$ 小。

请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。

输入格式

第一行有两个整数，分别表示 $n$ 和 $k$。

第二行有 $n$ 个整数，第 $i$ 个数表示 $a_i$。

输出格式

一个整数，表示第 $k$ 小的数。

输入输出样例 #1

输入 #1

5 1
4 3 2 1 5

输出 #1

2

说明/提示

对于 $100\%$ 的数据，$1\le a_i<{10}^9$，$1\le n<5\times 10^6$，且 $n$ 为奇数。

Tips

这里是引用

完整代码

在这里插入代码片