C++ STL

简介

向量vector / 队列queue / 栈stack / 双端队列deque

这些数据结构都是简单的数组，即使不用STL，也可以很方便的实现

向量 和 栈 只能后进后出
队列只能后进前出
双端对了 可以前后进 前后出

向量和双端队列 可以随机访问，栈和队列不可以

Error: ENOENT: no such file or directory, open '/Users/wwwwodddd/Dropbox/Informatics/problems/priority_queue.md'

priority_queue 优先队列/堆

加入任意值
询问最大值
删除最大值

优先队列是唯一一个默认大的在前的内置函数
priority_queue is the only exception, which largest is the first

其他的比如
set
map
sort
lower_bound
都是小的在前
the first is the smallest

每个位置都 -= M 可以删去一段，和 < 0 说明 ans < M R = M
每个位置都 -= M 删去任意一段，和 >= 0 说明 ans >= M L = M

include

std::priority_queue

3个操作
加入一个数字 push
取出最大值 top
删去最大值 pop
（不能删去任意值）
如何支持删除

1. 直接用set
2. 每次取top之后，检查一下是不是最新版本
3. 用一个堆，记录删去了哪些元素，如果2个堆的堆顶相同，同时删去。

可以删除 相当于可以修改

priority_queue q;

priority_queue
可以是结构体
结构体需要重载 <
或者传比较函数

priority_queue 默认 大的数字在前 top 是最大的
这个和 其他STL都不相同

map set sort lower_bound ...
都是小的在前

priority_queue 支持的操作和 set/multiset 很相似
priority_queue 快一点，但是不支持删除任意元素
set/multiset 可以删除任意元素，set支持lower_bound，前驱，后继

lower_bound 查询set中 >=x 最小元素是什么？
upper_bound 查询set中 >x 最小元素是什么？

std::priority_queue<int, std::vector<int>, std::less<int> > q2;
等价于
std::priority_queue<int> q2;
大 的在前

std::priority_queue<int, std::vector<int>, std::greater<int> > q2;
小 的在前

堆是如何实现的
https://github.com/wwwwodddd/Zukunft/blob/master/luogu/P3378.cpp
如何用数组存储二叉树
根节点是0，x的左孩子是2x+1，右孩子是2x+2，父亲节点是(x-1)/2
根节点是1，x的左孩子是2x，右孩子是2x+1，父亲节点是x/2

堆的性质（以大根堆为例）
每个节点>=自己的两个孩子
最大值一定在根节点（堆顶）
https://github.com/wwwwodddd/Zukunft/blob/master/luogu/P3378.cpp

调整操作
up 向上调整
每次和自己的父亲节点比

down 向下调整
和自己较大的孩子比
（自己可能0个孩子，1个孩子，2个孩子）

1. 取最大值
   直接返回堆顶

2. 如何加入一个数字
   加在末尾，向上调整

3. 删除
   堆顶和最后一个交换，堆顶向下调整

4. 初始化
   输入一个数组，如何初始化成堆的样子。

显而易见的做法，一个一个加入
for (int i = 1; i <= n; i++)
{
up(i);
}
时间复杂度O(n log n)

另一个做法
for (int i = n; i >= 1; i--)
{
down(i);
}
O(n)

对于自己实现的堆，可以支持删除任意值
需要记录每个值的位置（所以在所有swap的时候，需要同时交换位置）

swap(a[需要删除的位置], a[n]);
n--;
up(需要删除的位置)
down(需要删除的位置)

P1090 合并果子
Huffman Code

k叉？（每次合并<=k堆）
合并一次减少k-1堆
如果(n-1)%(k-1)==0 和之前一样，贪心即可。
如果(n-1)%(k-1)>0 第一次合并最小的(n-1)%(k-1)+1堆，其他和之前一样。

P1334 瑞瑞的木板
和 合并果子 一样
需要long long

STL函数
make_heap
pop_heap
push_heap

P6033 合并果子 加强版
合并果子的 计数排序 队列优化

P1177 【模板】快速排序

https://www.luogu.com.cn/problem/P1177

题目描述

利用快速排序算法将读入的 $N$ 个数从小到大排序后输出。

快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（C++ 选手请不要试图使用 STL，虽然你可以使用 sort 一遍过，但是你并没有掌握快速排序算法的精髓。）

输入格式

第 $1$ 行为一个正整数 $N$，第 $2$ 行包含 $N$ 个空格隔开的正整数 $a_i$，为你需要进行排序的数，数据保证了 $A_i$ 不超过 $10^9$。

输出格式

将给定的 $N$ 个数从小到大输出，数之间空格隔开，行末换行且无空格。

样例 #1

样例输入 #1

5
4 2 4 5 1

样例输出 #1

1 2 4 4 5

提示

对于 $20\%$ 的数据，有 $N\leq 10^3$；

对于 $100\%$ 的数据，有 $N\leq 10^5$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, a[100020];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	sort(a, a + n);
	for (int i = 0; i < n; i++) {
		printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');
	}
	return 0;
}

题解

P1168 中位数

https://www.luogu.com.cn/problem/P1168

题目描述

给出一个长度为$N$的非负整数序列$A_i$，对于所有$1 ≤ k ≤ (N + 1) / 2$，输出$A_1, A_1 \sim A_3, …,A_1 \sim A_{2k - 1}$的中位数。即前$1,3,5,…$个数的中位数。

输入格式

第$1$行为一个正整数$N$，表示了序列长度。

第$2$行包含$N$个非负整数$A_i (A_i ≤ 10^9)$。

输出格式

共$(N + 1) / 2$行，第$i$行为$A_1, A_3, …, A_{2k - 1}$的中位数。

样例 #1

样例输入 #1

7
1 3 5 7 9 11 6

样例输出 #1

1
3
5
6

提示

对于$20\%$的数据，$N ≤ 100$；

对于$40\%$的数据，$N ≤ 3000$；

对于$100\%$的数据，$N ≤ 100000$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, x;
priority_queue<int, vector<int>, greater<int> > q1;
priority_queue<int, vector<int>, less<int> > q2;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> x;
		if (i == 1 || x > q1.top()) {
			q1.push(x);
		} else {
			q2.push(x);
		}
		if (q1.size() < q2.size()) {
			q1.push(q2.top());
			q2.pop();
		}
		if (q1.size() > q2.size() + 1) {
			q2.push(q1.top());
			q1.pop();
		}
		if (i % 2 == 1) {
			printf("%d\n", q1.top());
		}
	}
	return 0;
}

题解

#include <bits/stdc++.h>
using namespace std;
int n, x;
priority_queue<int, vector<int>, greater<int> > q1; 小根堆
priority_queue<int, vector<int>, less<int> > q2; 大根堆
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> x;
		if (i == 1 || x > q1.top()) {
			q1.push(x);
		} else {
			q2.push(x);
		}
		if (q1.size() < q2.size()) {
			q1.push(q2.top());
			q2.pop();
		}
		if (q1.size() > q2.size() + 1) {
			q2.push(q1.top());
			q1.pop();
		}
		// 时刻保证 q1.size() == q2.size() || q1.size() == q2.size() + 1
		// 时刻保证 q1.top() >= q2.top();
		if (i % 2 == 1) {
			printf("%d\n", q1.top());
		}
	}
	return 0;
}

P1801 黑匣子

https://www.luogu.com.cn/problem/P1801

题目描述

Black Box 是一种原始的数据库。它可以储存一个整数数组，还有一个特别的变量 $i$。最开始的时候 Black Box 是空的．而 $i=0$。这个 Black Box 要处理一串命令。

命令只有两种：

• ADD(x)：把 $x$ 元素放进 Black Box;

• GET：$i$ 加 $1$，然后输出 Black Box 中第 $i$ 小的数。

记住：第 $i$ 小的数，就是 Black Box 里的数的按从小到大的顺序排序后的第 $i$ 个元素。

我们来演示一下一个有11个命令的命令串。（如下表所示）

序号	操作	$i$	数据库	输出
1	ADD(3)	$0$	$3$	/
2	GET	$1$	$3$	$3$
3	ADD(1)	$1$	$1,3$	/
4	GET	$2$	$1,3$	$3$
5	ADD(-4)	$2$	$-4,1,3$	/
6	ADD(2)	$2$	$-4,1,2,3$	/
7	ADD(8)	$2$	$-4,1,2,3,8$	/
8	ADD(-1000)	$2$	$-1000,-4,1,2,3,8$	/
9	GET	$3$	$-1000,-4,1,2,3,8$	$1$
10	GET	$4$	$-1000,-4,1,2,3,8$	$2$
11	ADD(2)	$4$	$-1000,-4,1,2,2,3,8$	/

现在要求找出对于给定的命令串的最好的处理方法。ADD 命令共有 $m$ 个，GET 命令共有 $n$ 个。现在用两个整数数组来表示命令串：

1. $a_1,a_2,\cdots,a_m$：一串将要被放进 Black Box 的元素。例如上面的例子中 $a=[3,1,-4,2,8,-1000,2]$。

2. $u_1,u_2,\cdots,u_n$：表示第 $u_i$ 个元素被放进了 Black Box 里后就出现一个 GET 命令。例如上面的例子中 $u=[1,2,6,6]$ 。输入数据不用判错。

输入格式

第一行两个整数 $m$ 和 $n$，表示元素的个数和 GET 命令的个数。

第二行共 $m$ 个整数，从左至右第 $i$ 个整数为 $a_i$，用空格隔开。

第三行共 $n$ 个整数，从左至右第 $i$ 个整数为 $u_i$，用空格隔开。

输出格式

输出 Black Box 根据命令串所得出的输出串，一个数字一行。

样例 #1

样例输入 #1

7 4
3 1 -4 2 8 -1000 2
1 2 6 6

样例输出 #1

3
3
1
2

提示

数据规模与约定

• 对于 $30\%$ 的数据，$1 \leq n,m \leq 10^{4}$。
• 对于 $50\%$ 的数据，$1 \leq n,m \leq 10^{5}$。
• 对于 $100\%$ 的数据，$1 \leq n,m \leq 2 \times 10^{5},|a_i| \leq 2 \times 10^{9}$，保证 $u$ 序列单调不降。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, a[200020];
priority_queue<int, vector<int>, greater<int> > q1;
priority_queue<int, vector<int>, less<int> > q2;
int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	for (int i = 0, j = 0; i < m; i++)
	{
		cin >> x;
		for (; j < x; j++)
		{
			q2.push(a[j]);
			if (q2.size() > i)
			{
				q1.push(q2.top());
				q2.pop();
			}
		}
		cout << q1.top() << endl;
		q2.push(q1.top());
		q1.pop();
	}
	return 0;
}

题解

和中位数类似的思路，2个堆

P1631 序列合并

https://www.luogu.com.cn/problem/P1631

题目描述

有两个长度都是N的序列A和B，在A和B中各取一个数相加可以得到$N^2$个和，求这$N^2$个和中最小的N个。

输入格式

第一行一个正整数N；

第二行N个整数$A_i$, 满足$A_i\le A_{i+1}$且$A_i\le 10^9$;

第三行N个整数$B_i$, 满足$B_i\le B_{i+1}$且$B_i\le 10^9$.

【数据规模】

对于50%的数据中，满足1<=N<=1000；

对于100%的数据中，满足1<=N<=100000。

输出格式

输出仅一行，包含N个整数，从小到大输出这N个最小的和，相邻数字之间用空格隔开。

样例 #1

样例输入 #1

3
2 6 6
1 4 8

样例输出 #1

3 6 7

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
int a[100020];
int b[100020];
int p[100020];
priority_queue<pair<int, int> > q;
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	for (int i = 0; i < n; i++) {
		scanf("%d", &b[i]);
		q.push(make_pair(-a[p[i]] - b[i], i));
	}
	for (int i = 0; i < n; i++) {
		pair<int, int> u = q.top();
		q.pop();
		printf("%d", -u.first);
		if (i == n - 1) {
			printf("\n");
			break;
		} else {
			printf(" ");
		}
		p[u.second]++;
		q.push(make_pair(-a[p[u.second]] - b[u.second], u.second));
	}
	return 0;
}

题解

注意到a[i] + b[j] 如果ij>n 一定不会被选择
考虑有多少个位置满足 ij <= n
n / 1 + n / 2 + .. + n / n 约等于 n log n
在n log n个数字中求最小的n个

for (int i = 1; i <= n && i <= a.size(); i++)
{
	for (int j = 1; j * i <= n && j <= b.size(); j++)
	{
		re.push_back(a[i-1] + b[j-1]);
	}
}
sort(re.begin(), re.end());
re.resize(n);
return re;

P2085 最小函数值

https://www.luogu.com.cn/problem/P2085

题目描述

有 $n$ 个函数，分别为 $F_1,F_2,\dots,F_n$。定义 $F_i(x)=A_ix^2+B_ix+C_i(x\in\mathbb N*)$。给定这些 $A_i$、$B_i$ 和 $C_i$，请求出所有函数的所有函数值中最小的 $m$ 个（如有重复的要输出多个）。

输入格式

第一行输入两个正整数 $n$ 和 $m$。

以下 $n$ 行每行三个正整数，其中第 $i$ 行的三个数分别为 $A_i$、$B_i$ 和 $C_i$。

输出格式

输出将这 $n$ 个函数所有可以生成的函数值排序后的前 $m$ 个元素。这 $m$ 个数应该输出到一行，用空格隔开。

样例 #1

样例输入 #1

3 10
4 5 3
3 4 5
1 7 1

样例输出 #1

9 12 12 19 25 29 31 44 45 54

提示

数据规模与约定

对于全部的测试点，保证 $1 \leq n,m\le10000$，$1 \leq A_i\le10,B_i\le100,C_i\le10^4$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[10020];
int b[10020];
int c[10020];
int p[10020];
priority_queue<pair<int, int> > q;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d%d%d", &a[i], &b[i], &c[i]);
		int j = i;
		p[j]++;
		q.push(make_pair(-a[j] * p[j] * p[j] - b[j] * p[j] - c[j], j));
	}
	for (int i = 0; i < m; i++) {
		pair<int, int> u = q.top();
		q.pop();
		printf("%d%c", -u.first, i == m - 1 ? '\n' : ' ');
		int j = u.second;
		p[j]++;
		q.push(make_pair(-a[j] * p[j] * p[j] - b[j] * p[j] - c[j], j));
	}
	return 0;
}

题解

Fi(x) < Fi(x+1)
一定先取x再取x+1

P3620 [APIO/CTSC 2007] 数据备份

https://www.luogu.com.cn/problem/P3620

题目描述

你在一家 IT 公司为大型写字楼或办公楼(offices)的计算机数据做备份。然而数据备份的工作是枯燥乏味的，因此你想设计一个系统让不同的办公楼彼此之间互相备份，而你则坐在家中尽享计算机游戏的乐趣。

已知办公楼都位于同一条街上。你决定给这些办公楼配对(两个一组)。每一对办公楼可以通过在这两个建筑物之间铺设网络电缆使得它们可以互相备份。

然而，网络电缆的费用很高。当地电信公司仅能为你提供 K 条网络电缆，这意味着你仅能为 K 对办公楼(或总计 2K 个办公楼)安排备份。任一个办公楼都属于唯一的配对组(换句话说，这 2K 个办公楼一定是相异的)。

此外，电信公司需按网络电缆的长度(公里数)收费。因而，你需要选择这 K对办公楼使得电缆的总长度尽可能短。换句话说，你需要选择这 K 对办公楼，使得每一对办公楼之间的距离之和(总距离)尽可能小。

下面给出一个示例，假定你有 5 个客户，其办公楼都在一条街上，如下图所示。这 5 个办公楼分别位于距离大街起点 1km, 3km, 4km, 6km 和 12km 处。电信公司仅为你提供 K=2 条电缆。

上例中最好的配对方案是将第 1 个和第 2 个办公楼相连，第 3 个和第 4 个办公楼相连。这样可按要求使用 K=2 条电缆。第 1 条电缆的长度是 3km―1km = 2km，第 2 条电缆的长度是 6km―4km = 2 km。这种配对方案需要总长 4km 的网络电缆，满足距离之和最小的要求。

输入格式

输入文件的第一行包含整数 n 和 k，其中 n(1≤n≤100 000)表示办公楼的数目，k(1≤k≤n/2)表示可利用的网络电缆的数目。

接下来的 n 行每行仅包含一个整数(0≤s≤1000 000 000), 表示每个办公楼到大街起点处的距离。这些整数将按照从小到大的顺序依次出现。

输出格式

输出文件应当由一个正整数组成，给出将 2K 个相异的办公楼连成 K 对所需的网络电缆的最小总长度。

样例 #1

样例输入 #1

5 2 
1 
3 
4 
6 
12 

样例输出 #1

4

提示

30%的输入数据满足 n≤20。

60%的输入数据满足 n≤10 000

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[100020];
int nxt[100020];
int pre[100020];
set<pair<int, int> > s;
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		pre[i + 1] = i;
		nxt[i] = i + 1;
	}
	for (int i = n - 1; i > 0; i--) {
		a[i] -= a[i - 1];
		s.insert(make_pair(a[i], i));
	}
	a[0] = 1e9;
	a[n] = 1e9;
	int z = 0;
	for (int i = 0; i < k; i++) {
		int x = s.begin()->second;
		s.erase(s.begin());
		z += a[x];
		s.erase(make_pair(a[pre[x]], pre[x]));
		s.erase(make_pair(a[nxt[x]], nxt[x]));
		a[x] = a[pre[x]] + a[nxt[x]] - a[x];
		s.insert(make_pair(a[x], x));
		pre[x] = pre[pre[x]];
		nxt[x] = nxt[nxt[x]];
		nxt[pre[x]] = x;
		pre[nxt[x]] = x;
	}
	printf("%lld\n", z);
	return 0;
}

题解

2 1 2 6

1000000000 1 2 3 4

a b c 选择中间的b
变成1个数字
a+c-b

51nod 1380 夹克老爷的逢三抽一

P1878 舞蹈课

https://www.luogu.com.cn/problem/P1878

题目描述

有 $n$ 个人参加一个舞蹈课。每个人的舞蹈技术由整数来决定。在舞蹈课的开始，他们从左到右站成一排。当这一排中至少有一对相邻的异性时，舞蹈技术相差最小的那一对会出列并开始跳舞。如果不止一对，那么最左边的那一对出列。一对异性出列之后，队伍中的空白按原顺序补上（即：若队伍为 ABCD，那么 BC 出列之后队伍变为 AD）。舞蹈技术相差最小即是 $a_i$ 的绝对值最小。

任务是模拟以上过程，确定跳舞的配对及顺序。

输入格式

第一行一个正整数 $n$ 表示队伍中的人数。

第二行包含 $n$ 个字符 B 或者 G，B 代表男，G 代表女。

第三行为 $n$ 个整数 $a_i$。所有信息按照从左到右的顺序给出。

输出格式

第一行一个整数表示出列的总对数 $k$。

接下来 $k$ 行，每行是两个整数。按跳舞顺序输出，两个整数代表这一对舞伴的编号（按输入顺序从左往右 $1$ 至 $n$ 编号）。请先输出较小的整数，再输出较大的整数。

样例 #1

样例输入 #1

4
BGBG
4 2 4 3

样例输出 #1

2
3 4
1 2

提示

对于 $50\%$ 的数据，$1\leq n\leq 200$。

对于 $100\%$ 的数据，$1\leq n\leq 2\times 10^5$，$1\le a_i\le 10^7$。

参考代码

题解

P5120 [USACO18DEC]Convention II S

https://www.luogu.com.cn/problem/P5120

题目描述

虽然在接机上耽误了挺长时间，Farmer John 为吃草爱好牛们举行的大会至今为止都非常顺利。大会吸引了世界各地的奶牛。

然而大会的重头戏看起来却给 Farmer John 带来了一些新的安排上的困扰。他的农场上的一块非常小的牧草地出产一种据某些识货的奶牛说是世界上最美味的品种的草。因此，所有参会的 $N$ 头奶牛（$1\le N\le 10^5$）都想要品尝一下这种草。由于这块牧草地小到仅能容纳一头奶牛，这很有可能会导致排起长龙。

Farmer John 知道每头奶牛i计划到达这块特殊的牧草地的时间 $a_i$，以及当轮到她时，她计划品尝这种草花费的时间 $t_i$。当奶牛 $i$ 开始吃草时，她会在离开前花费全部 $t_i$ 的时间，此时其他到达的奶牛需要排队等候。如果这块牧草地空出来的时候多头奶牛同时在等候，那么资历最深的奶牛将会是下一头品尝鲜草的奶牛。在这里，恰好在另一头奶牛吃完草离开时到达的奶牛被认为是“在等待的”。类似地，如果当没有奶牛在吃草的时候有多头奶牛同时到达，那么资历最深的奶牛是下一头吃草的奶牛。

请帮助 FJ 计算所有奶牛中在队伍里等待的时间（$a_i$ 到这头奶牛开始吃草之间的时间）的最大值。

输入格式

输入的第一行包含 $N$。以下 $N$ 行按资历顺序给出了 $N$ 头奶牛的信息（资历最深的奶牛排在最前面）。每行包含一头奶牛的 $a_i$ 和 $t_i$。所有的 $t_i$ 为不超过 $10^4$ 的正整数，所有 $a_i$ 为不超过 $10^9$ 的正整数。

输出格式

输出所有奶牛中的最长等待时间。

样例 #1

样例输入 #1

5
25 3
105 30
20 50
10 17
100 10

样例输出 #1

10

提示

在这个例子中，我们有 $5$ 头奶牛（按输入中的顺序编号为 $1\dots 5$）。奶牛 $4$ 最先到达（时间 $10$），在她吃完之前（时间 $27$）奶牛 $1$ 和奶牛 $3$ 都到达了。由于奶牛 $1$ 拥有较深的资历，所以她先吃，从她到达开始共计等待了 $2$ 个单位时间。她在时间 $30$ 结束吃草，随后奶牛 $3$ 开始吃草，从她到达开始共计等待了 $10$ 单位时间。在一段没有奶牛吃草的时间过后，奶牛 $5$ 到达，在她正在吃草的时间里奶牛 $2$ 也到达了，在 $5$ 个单位时间之后能够吃到草。相比到达时间等待最久的奶牛是奶牛 $3$。

参考代码

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
int n;
pair<pair<int, int>, int> a[100020];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &a[i].X.X, &a[i].Y);
		a[i].X.Y = i;
	}
	sort(a, a + n);
	int z = 0, i = 0, t = 0;
	set<pair<pair<int, int>, int> > s;
	while (i < n || s.size()) {
		while (i < n && a[i].X.X <= t) {
			swap(a[i].X.X, a[i].X.Y);
			s.insert(a[i++]);
		}
		if (s.size() == 0) {
			t = a[i].X.X;
			continue;
		}
		z = max(z, t - s.begin()->X.Y);
		t += s.begin()->Y;
		s.erase(s.begin());
	}
	printf("%d\n", z);
	return 0;
}

题解

P1382 楼房

https://www.luogu.com.cn/problem/P1382

题目描述

地平线（$x$ 轴）上有 $n$ 个楼房，每个楼房可以表示为一个矩形。

用三个整数 $h_i,l_i,r_i$ 来表示第 $i$ 个矩形：矩形左下角为 $(l_i,0)$，右上角为 $(r_i,h_i)$。

地平线高度为 $0$。在轮廓线长度最小的前提下，从左到右输出轮廓线。

输入格式

第一行一个整数 $n$，表示矩形个数。

以下 $n$ 行，每行 $3$ 个整数 $h_i,l_i,r_i$ 表示第 $i$ 个矩形。

输出格式

第一行一个整数 $m$，表示节点个数。

以下 $m$ 行，每行一个坐标表示轮廓线上的节点。

要求从左到右遍历轮廓线并顺序输出节点。

注：第一个和最后一个节点的 $y$ 坐标必然为 $0$。

样例 #1

样例输入 #1

2
3 0 2
4 1 3

样例输出 #1

6
0 0
0 3
1 3
1 4
3 4
3 0

样例 #2

样例输入 #2

5
3 -3 0
2 -1 1
4 2 4
2 3 7
3 6 8

样例输出 #2

14
-3 0
-3 3
0 3
0 2
1 2
1 0
2 0
2 4
4 4
4 2
6 2
6 3
8 3
8 0

提示

样例二如图：

数据范围:

对于 $30\%$ 的数据，$n\le100$。

对于另外 $30\%$ 的数据，$1\le h_i,l_i,r_i\le 1000$。

对于 $100\%$ 的数据，$1\le n\le10^5$，$1\le h_i\le 10^9$，$-10^9\le l_i<r_i\le10^9$。

参考代码

题解

扫描线 set

P2707 Facer帮父亲

https://www.luogu.com.cn/problem/P2707

题目背景

Facer可是一个孝顺的孩纸呦

题目描述

Facer的父亲是一名经理，现在总是垂头丧气的。

Facer问父亲，怎么啦？父亲说，公司出了点问题啊。

公司管理着N个风景点，每个风景点都有不少人来参观。

可是现在！人民投诉票价太高了，他不得不调整票价

具体来说，第i个景点如果票价是x，来的人数就是max( (ai - bi * x),0 )[收益自己算好伐]

你需要分配每个景点的门票，使得每个景点门票总和不超过k，且最大化收益

求最大的收益

输入格式

第一行N , k

接下来N行，每行ai,bi

输出格式

一行，最大的收益

样例 #1

样例输入 #1

2 4
50 2
40 1

样例输出 #1

171

提示

样例解释：

景点1票价3，景点2票价1

景点1人数：50 - 3*2 = 44 票价 :3 收益:132

景点2人数 : 40 - 1*1 = 39 票价 : 1 收益:39

总收益171 最大

10%  n <= 5 , k <= 5
30%  n <= 100,k <= 100
60%  n <= 2000,k <= 2000
100%n <= 100000,k <= 100000
1 <= ai , bi <= 100000
鸣谢 zhouyonglong 提供解法

参考代码

题解

P2085 最小函数值

https://www.luogu.com.cn/problem/P2085

题目描述

有 $n$ 个函数，分别为 $F_1,F_2,\dots,F_n$。定义 $F_i(x)=A_ix^2+B_ix+C_i(x\in\mathbb N*)$。给定这些 $A_i$、$B_i$ 和 $C_i$，请求出所有函数的所有函数值中最小的 $m$ 个（如有重复的要输出多个）。

输入格式

第一行输入两个正整数 $n$ 和 $m$。

以下 $n$ 行每行三个正整数，其中第 $i$ 行的三个数分别为 $A_i$、$B_i$ 和 $C_i$。

输出格式

输出将这 $n$ 个函数所有可以生成的函数值排序后的前 $m$ 个元素。这 $m$ 个数应该输出到一行，用空格隔开。

样例 #1

样例输入 #1

3 10
4 5 3
3 4 5
1 7 1

样例输出 #1

9 12 12 19 25 29 31 44 45 54

提示

数据规模与约定

对于全部的测试点，保证 $1 \leq n,m\le10000$，$1 \leq A_i\le10,B_i\le100,C_i\le10^4$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[10020];
int b[10020];
int c[10020];
int p[10020];
priority_queue<pair<int, int> > q;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d%d%d", &a[i], &b[i], &c[i]);
		int j = i;
		p[j]++;
		q.push(make_pair(-a[j] * p[j] * p[j] - b[j] * p[j] - c[j], j));
	}
	for (int i = 0; i < m; i++) {
		pair<int, int> u = q.top();
		q.pop();
		printf("%d%c", -u.first, i == m - 1 ? '\n' : ' ');
		int j = u.second;
		p[j]++;
		q.push(make_pair(-a[j] * p[j] * p[j] - b[j] * p[j] - c[j], j));
	}
	return 0;
}

题解

Fi(x) < Fi(x+1)
一定先取x再取x+1

P3045 [USACO12FEB]Cow Coupons G

https://www.luogu.com.cn/problem/P3045

题目描述

Farmer John needs new cows! There are N cows for sale (1 <= N <= 50,000), and FJ has to spend no more than his budget of M units of money (1 <= M <= 10^14). Cow i costs P_i money (1 <= P_i <= 10^9), but FJ has K coupons (1 <= K <= N), and when he uses a coupon on cow i, the cow costs C_i instead (1 <= C_i <= P_i). FJ can only use one coupon per cow, of course.

What is the maximum number of cows FJ can afford?

FJ准备买一些新奶牛，市场上有N头奶牛(1<=N<=50000)，第i头奶牛价格为Pi(1<=Pi<=10^{9)。FJ有K张优惠券，使用优惠券购买第i头奶牛时价格会降为Ci(1<=Ci<=Pi)，每头奶牛只能使用一次优惠券。FJ想知道花不超过M(1<=M<=10}14)的钱最多可以买多少奶牛？

输入格式

* Line 1: Three space-separated integers: N, K, and M.

* Lines 2..N+1: Line i+1 contains two integers: P_i and C_i.

输出格式

* Line 1: A single integer, the maximum number of cows FJ can afford.

样例 #1

样例输入 #1

4 1 7 
3 2 
2 2 
8 1 
4 3 

样例输出 #1

3 

提示

FJ has 4 cows, 1 coupon, and a budget of 7.

FJ uses the coupon on cow 3 and buys cows 1, 2, and 3, for a total cost of 3 + 2 + 1 = 6.

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, k;
long long m, s;
int c[100020];
int p[100020];
pair<int, int> a[100020];
pair<int, int> b[100020];
bool v[100020];
int main() {
	cin >> n >> k >> m;
	for (int i = 0; i < n; i++) {
		cin >> p[i] >> c[i];
		a[i].first = c[i];
		b[i].first = p[i];
		a[i].second = b[i].second = i;
	}
	sort(a, a + n);
	sort(b, b + n);
	priority_queue<int, vector<int>, greater<int> > q;
	q.push(1000000000);
	for (int i = 0; i < k; i++) {
		q.push(0);
	}
	int pa = 0;
	int pb = 0;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		while (v[a[pa].second]) {
			pa++;
		}
		while (v[b[pb].second]) {
			pb++;
		}
		if (a[pa].first + q.top() < b[pb].first) {
			v[a[pa].second] = true;
			s += a[pa].first + q.top();
			q.pop();
			q.push(p[a[pa].second] - a[pa].first);
			assert(c[a[pa].second] == a[pa].first);
		} else {
			v[b[pb].second] = true;
			s += b[pb].first;
		}
		if (s <= m) {
			ans = max(ans, i + 1);
		}
	}
	cout << ans << endl;
}

题解

优先队列 可以优化 dijkstra

Java PriorityQueue

P2107 小Z的AK计划

https://www.luogu.com.cn/problem/P2107

题目描述

在小Z的家乡，有机房一条街，街上有很多机房。每个机房里都有一万个人在切题。小Z刚刷完CodeChef，准备出来逛逛。

机房一条街有 n 个机房，第 i 个机房的坐标为 xi ，小Z的家坐标为 0。小Z在街上移动的速度为1，即从 x1 到 x2 所耗费的时间为 |x1 - x2|。
每个机房的学生数量不同，ACM 题目水平也良莠不齐。小Z到达第 i 个机房后，可以花 ti 的时间想题，然后瞬间 AK；当然，也可以过机房而不入。

小Z现在只有 m 个单位时间，之后他就该赶着去打 Codeforces 了。现在他想知道自己最多能在多少个机房 AK，希望你帮帮他。

输入格式

第一行包含两个整数 n，m。

接下来 n 行，每行包含两个整数 xi，ti 。

输出格式

第一行包含一个整数，表示小Z最多能 AK 的机房数量。

样例 #1

样例输入 #1

2 10
1 100
5 5

样例输出 #1

1

提示

【数据规模】

对于 30% 的数据，n ≤ 20。

对于 60% 的数据，n ≤ 1000。

对于 100% 的数据，1 ≤ n ≤ 10^5，0 ≤ m，xi ≤ 10^18，0 ≤ ti ≤ 10^9。

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, z;
ll m, s;
pair<ll, ll> a[100020];
priority_queue<ll> q;
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i].first >> a[i].second;
	}
	sort(a, a + n);
	for (int i = 0; i < n; i++) {
		if (a[i].first > m) {
			break;
		}
		q.push(a[i].second);
		s += a[i].second;
		while (s + a[i].first > m) {
			s -= q.top();
			q.pop();
		}
		z = max(z, (int)q.size());
	}
	cout << z << endl;
}

题解

带反悔的贪心
一定是从原点向右走到某个位置，在路过的任务中选最小的若干个来做。

P2949 [USACO09OPEN]Work Scheduling G

https://www.luogu.com.cn/problem/P2949

题目描述

Farmer John has so very many jobs to do! In order to run the farm efficiently, he must make money on the jobs he does, each one of which takes just one time unit.

His work day starts at time 0 and has 1,000,000,000 time units (!). He currently can choose from any of N (1 <= N <= 100,000) jobs

conveniently numbered 1..N for work to do. It is possible but

extremely unlikely that he has time for all N jobs since he can only work on one job during any time unit and the deadlines tend to fall so that he can not perform all the tasks.

Job i has deadline D_i (1 <= D_i <= 1,000,000,000). If he finishes job i by then, he makes a profit of P_i (1 <= P_i <= 1,000,000,000).

What is the maximum total profit that FJ can earn from a given list of jobs and deadlines? The answer might not fit into a 32-bit integer.

输入格式

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains two space-separated integers: D_i and P_i

输出格式

* Line 1: A single number on a line by itself that is the maximum possible profit FJ can earn.

样例 #1

样例输入 #1

3 
2 10 
1 5 
1 7 

样例输出 #1

17 

提示

Complete job 3 (1,7) at time 1 and complete job 1 (2,10) at time 2 to maximize the earnings (7 + 10 -> 17).

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
priority_queue<int, vector<int>, greater<int> > q;
pair<int, int> a[100020];
long long z;
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d", &a[i].first, &a[i].second);
	}
	sort(a, a + n);
	for (int i = 0; i < n; i++)
	{
		z += a[i].second;
		q.push(a[i].second);
		if (q.size() > a[i].first)
		{
			z -= q.top();
			q.pop();
		}
	}
	printf("%lld\n", z);
	return 0;
}

题解

带反悔的贪心

假设决定了做哪些任务，一定是按照截止时间排序来做。
对于任意一个时间x，
截止时间<=x的任务 消耗的总时间 必须<=x
截止时间<=x的任务 个数 必须<=x

扫描所有任务，每次直接选择，如果当前选择的任务个数 > 截止时间，在所有已经选择的任务中，
扔掉获利最小的（扔掉获利最小的任务时，不考虑截止时间）

假设每个任务消耗的时间不相同
可以用背包解决
先排序
每个任务更新时，只更新到自己的截止时间

背包时，不同物品的放置顺序是有关系的
先考虑假设要选择一个集合
按哪种顺序一定可以放置成功
先把这些物品按照这个顺序排序

CF101623I

https://codeforces.com/gym/101623/attachments
https://codeforces.com/gym/101623/problem/I

set 集合

set 集合 有序的
multiset 多重集合 有序的

支持的操作：

• 加入任意值 s.insert
  • 有返回值，返回 pair<iterator, bool>
  • iterator 表示插入位置的指针
  • bool 表示插入是否成功
• 删除任意值 s.erase
  • 参数可以是 值 或者 iterator
  • 如果 erase 一个值，会把所有这个值都删掉
  • multiset 时，有的时候只想删去一个值，要用 s.erase(s.find(x))
• 询问 lower_bound 和 upper_bound
  • lower_bound >= x 的最小值
  • upper_bound > x 的最小值
• 询问最小值 s.begin()
• 询问最大值 --s.end() 或 s.rbegin()
  • 如果想删去最大值，只能用 s.erase(--s.end())
  • 如果想删去最大值，不能用 s.erase(s.rbegin())
  • 因为 s.rbegin() 是 reverse_iterator 不是 iteratior
• 从小到大遍历所有元素
  • for (auto i : s)
  • for (set<int>::iterator it = s.begin() it != s.end(); it++)
• 从大到小遍历所有元素
  • for (auto it = s.rbegin() it != s.rend(); it++)

不支持的操作

询问第k大值
询问一个值是第几大

priority_queue 能做的，set 都能做，但是 set 慢一些

C++ set = Java TreeSet (sorted set)
C++ unordered_set = Java HashSet
Python 用 SortedList 实现 C++ set 的功能

s.find(x)
如果 x 在 set 中，返回 iterator
如果不在 返回 s.end()

s.lower_bound(x) set 中 >= x 最小的
s.upper_bound(x) set 中 > x 最小的
如果存在，返回 iterator
如果不存在，那么返回 s.end()

如果 x 不在 s 中，那么 lower_bound 和 upper_bound 结果相同（不存在 == x 的位置）

--s.lower_bound(x) set 中 < x 最大的
--s.upper_bound(x) set 中 <= x 最大的
需要注意如果x已经是最小的数字，那么可能出错。

枚举

for (auto i: s)
{

}

加入

可以利用 insert 的返回值判断是否删除成功

删除

multiset 删除一个 要先 find 再 erase

map

map 映射

同时存储一对 key 和 value
可以根据 key 找到 value

支持操作：
加入任意值
删除任意值
询问 lower_bound 和 upper_bound
询问最大值最小值

不支持：
询问第k大值
询问一个值是第几大

Java

C++ map = Java TreeMap (sorted map)
C++ unordered_map = Java HashMap

参考题目

abc253_c Max - Min Query

https://atcoder.jp/contests/abc253/tasks/abc253_c
维护 multiset
支持加入一个值
删去一个值x至多c次
输出最大值减去最小值的差

参考代码

#include <bits/stdc++.h>
using namespace std;
map<int, int> g;
int q, o, x, c;
int main()
{
	scanf("%d", &q);
	for (int i = 0; i < q; i++)
	{
		scanf("%d", &o);
		if (o == 1)
		{
			scanf("%d", &x);
			g[x]++;
		}
		else if (o == 2)
		{
			scanf("%d%d", &x, &c);
			g[x] -= c;
			if (g[x] <= 0)
			{
				g.erase(x);
			}
		}
		else
		{
			printf("%d\n", g.rbegin()->first - g.begin()->first);
		}
	}
	return 0;
}

题解

题目

P1503 鬼子进村

https://www.luogu.com.cn/problem/P1503

题目背景

小卡正在新家的客厅中看电视。电视里正在播放放了千八百次依旧重播的《亮剑》，剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队，于是独立团与鬼子展开游击战。

题目描述

县城里有 $n$ 个用地道相连的房子，第 $i$ 个只与第 $i-1$ 和第 $i+1$ 个相连。这时有 $m$ 个消息依次传来：

1. 若消息为 D x：鬼子将 $x$ 号房子摧毁了，地道被堵上。

2. 若消息为 R ：村民们将鬼子上一个摧毁的房子修复了。

3. 若消息为 Q x：有一名士兵被围堵在 $x$ 号房子中。

李云龙收到信息很紧张，他想知道每一个被围堵的士兵能够到达的房子有几个。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，有如题目所说的三种信息共 $m$ 条。

输出格式

对于每一个被围堵的士兵，输出该士兵能够到达的房子数。

样例 #1

样例输入 #1

7 9
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4

样例输出 #1

1
0
2
4

提示

$1\leq n,m\leq 5\times 10^4$。

若士兵被围堵在摧毁了的房子中，那只能等死了。。。。。。

参考代码

#include <bits/stdc++.h>
using namespace std;
stack<int> a;
char o[2];
set<int> s;
int n, m, x;
int main() {
	scanf("%d%d", &n, &m);
	s.insert(0);
	s.insert(n+1);
	for (int i = 0; i < m; i++) {
		scanf("%s", o);
		if (o[0] == 'D') {
			scanf("%d", &x);
			s.insert(x);
			a.push(x);
		} else if (o[0] == 'R') {
			s.erase(a.top());
			a.pop();
		} else if (o[0] == 'Q') {
			scanf("%d", &x);
			if (s.find(x) != s.end()) {
				printf("0\n");
			} else {
				set<int>::iterator it;
				it = s.lower_bound(x);
//				it = s.upper_bound(x);
				set<int>::iterator ti=it;
				ti--;
				printf("%d\n", *it - *ti - 1);
			}
		}
	}
	return 0;
}

题解

P2073 送花

https://www.luogu.com.cn/problem/P2073

题目背景

小明准备给小红送一束花，以表达他对小红的爱意。他在花店看中了一些花，准备用它们包成花束。

题目描述

这些花都很漂亮，每朵花有一个美丽值W，价格为C。

小明一开始有一个空的花束，他不断地向里面添加花。他有以下几种操作：

操作 含义

1 W C 添加一朵美丽值为W，价格为C的花。

3 小明觉得当前花束中最便宜的一朵花太廉价，不适合送给小红，所以删除最便宜的一朵花。

2 小明觉得当前花束中最贵的一朵花太贵，他心疼自己的钱，所以删除最贵的一朵花。

-1 完成添加与删除，开始包装花束

若删除操作时没有花，则跳过删除操作。

如果加入的花朵价格已经与花束中已有花朵价格重复，则这一朵花不能加入花束。

请你帮小明写一个程序，计算出开始包装花束时，花束中所有花的美丽值的总和，以及小明需要为花束付出的总价格。

输入格式

若干行，每行一个操作，以-1结束。

输出格式

一行，两个空格隔开的正整数表示开始包装花束时，花束中所有花的美丽值的总和。以及小明需要为花束付出的总价格。

样例 #1

样例输入 #1

1 1 1
1 2 5
2
1 3 3
3
1 5 2
-1

样例输出 #1

8 5

提示

对于20%数据，操作数<=100，1<=W,C<=1000。

对于全部数据，操作数<=100000,1<=W,C<=1000000。

参考代码

#include <bits/stdc++.h>
using namespace std;
map<int, int> g;
int main() {
	while (true) {
		int o, x, y;
		scanf("%d", &o);
		if (o == 1) {
			scanf("%d%d", &x, &y);
			if (g.find(y) == g.end()) {
				g[y] = x;
			}
		} else if (o == 2) {
			if (g.size() > 0) {
				g.erase(--g.end());
			}
		} else if (o == 3) {
			if (g.size() > 0) {
				g.erase(g.begin());
			}
		} else {
			break;
		}
	}
	long long s1 = 0;
	long long s2 = 0;
	for (map<int, int>::iterator it = g.begin(); it != g.end(); it++) {
		s1 += it->first;
		s2 += it->second;
	}
	cout << s2 << ' ' << s1 << endl;
	return 0;
}

题解

P2234 [HNOI2002]营业额统计

https://www.luogu.com.cn/problem/P2234

题目描述

Tiger 最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。

Tiger 拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：当最小波动值越大时，就说明营业情况越不稳定。

而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助 Tiger 来计算这一个值。

我们定义，一天的最小波动值 = $\min\{|\text{该天以前某一天的营业额}-\text{该天营业额}|\}$。

特别地，第一天的最小波动值为第一天的营业额。

输入格式

第一行为正整数 $n$（$n \leq 32767$） ，表示该公司从成立一直到现在的天数，接下来的 $n$ 行每行有一个整数 $a_i$（$|a_i| \leq 10^6$) ，表示第 $i$ 天公司的营业额，可能存在负数。

输出格式

输出一个正整数，即每一天最小波动值的和，保证结果小于 $2^{31}$。

样例 #1

样例输入 #1

6
5
1
2
5
4
6

样例输出 #1

12

提示

结果说明：$5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12$

参考代码

#include <bits/stdc++.h>
using namespace std;
set<int> s;
int n, x, z;
int main() {
	s.insert(-1000000000);
	s.insert(1000000000);
	cin >> n;
	cin >> x;
	z = x;
	s.insert(x);
	for (int i = 1; i < n; i++) {
		cin >> x;
		set<int>::iterator it;
		it = s.lower_bound(x);
		set<int>::iterator ti=it;
		ti--;
		z += min(*it - x, x - *ti);
		s.insert(x);
	}
	cout << z << endl;
	return 0;
}

题解

P4404 [JSOI2010]缓存交换

https://www.luogu.com.cn/problem/P4404

题目背景

感谢@ACdreamer 贡献数据

题目描述

在计算机中，CPU只能和高速缓存Cache直接交换数据。当所需的内存单元不在Cache中时，则需要从主存里把数据调入Cache。此时，如果Cache容量已满，则必须先从中删除一个。

例如，当前Cache容量为3，且已经有编号为10和20的主存单元。
此时，CPU访问编号为10的主存单元，Cache命中。

接着，CPU访问编号为21的主存单元，那么只需将该主存单元移入Cache中，造成一次缺失（Cache Miss）。

接着，CPU访问编号为31的主存单元，则必须从Cache中换出一块，才能将编号为31的主存单元移入Cache，假设我们移出了编号为10的主存单元。

接着，CPU再次访问编号为10的主存单元，则又引起了一次缺失。我们看到，如果在上一次删除时，删除其他的单元，则可以避免本次访问的缺失。

在现代计算机中，往往采用LRU(最近最少使用)的算法来进行Cache调度——可是，从上一个例子就能看出，这并不是最优的算法。
对于一个固定容量的空Cache和连续的若干主存访问请求，聪聪想知道如何在每次Cache缺失时换出正确的主存单元，以达到最少的Cache缺失次数。

输入格式

输入文件第一行包含两个整数N和M(1<=M<=N<=100,000)，分别代表了主存访问的次数和Cache的容量。

第二行包含了N个空格分开的正整数，按访问请求先后顺序给出了每个主存块的编号(不超过1,000,000,000)。

输出格式

输出一行，为Cache缺失次数的最小值。

样例 #1

样例输入 #1

6 2
1 2 3 1 2 3

样例输出 #1

4

提示

在第4次缺失时将3号单元换出Cache。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, ans;
int a[100020];
int p[100020];
map<int, int> g;
set<int> s;
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = n - 1; i >= 0; i--) {
		if (g.find(a[i]) == g.end()) {
			p[i] = n;
		} else {
			p[i] = g[a[i]];
		}
		g[a[i]] = i;
	}
	for (int i = 0; i < n; i++) {
		if (s.find(i) == s.end()) {
			ans++;
			if (s.size() == m) {
				s.erase(--s.end());
			}
		} else {
			s.erase(i);
		}
		s.insert(p[i]);
	}
	cout << ans << endl;
	return 0;
}

题解

P2061 [USACO07OPEN]City Horizon S

https://www.luogu.com.cn/problem/P2061

题目描述

Farmer John has taken his cows on a trip to the city! As the sun sets, the cows gaze at the city horizon and observe the beautiful silhouettes formed by the rectangular buildings.

The entire horizon is represented by a number line with N (1 ≤ N ≤ 40,000) buildings. Building i's silhouette has a base that spans locations Ai through Bi along the horizon (1 ≤ Ai < Bi ≤ 1,000,000,000) and has height Hi (1 ≤ Hi ≤ 1,000,000,000). Determine the area, in square units, of the aggregate silhouette formed by all N buildings.

有一个数列，初始值均为0，他进行N次操作，每次将数列[ai,bi)这个区间中所有比Hi小的数改为Hi，他想知道N次操作后数列中所有元素的和。

输入格式

第一行一个整数N，然后有N行，每行三个正整数ai、bi、Hi。

输出格式

一个数，数列中所有元素的和。

样例 #1

样例输入 #1

4
2 5 1
9 10 4
6 8 2
4 6 3

样例输出 #1

16

提示

N<=40000 , a、b、k<=10^9 。

参考代码

#include <bits/stdc++.h>
using namespace std;
pair<int, int> a[100020];
int n, x, y, z;
long long ans;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x >> y >> z;
		a[2 * i] = make_pair(x, z);
		a[2 * i + 1] = make_pair(y, -z);
	}
	sort(a, a + 2 * n);
	multiset<int> s;
	s.insert(0);
	for (int i = 0; i + 1 < 2 * n; i++) {
		if (a[i].second > 0) {
			s.insert(a[i].second);
		} else {
			s.erase(s.find(-a[i].second));
		}
		ans += (long long)(a[i + 1].first - a[i].first) * (*--s.end());
	}
	cout << ans << endl;
}

题解

P2161 [SHOI2009]会场预约

https://www.luogu.com.cn/problem/P2161

题目描述

PP大厦有一间空的礼堂，可以为企业或者单位提供会议场地。这些会议中的大多数都需要连续几天的时间（个别的可能只需要一天），不过场地只有一个，所以不同的会议的时间申请不能够冲突。也就是说，前一个会议的结束日期必须在后一个会议的开始日期之前。所以，如果要接受一个新的场地预约申请，就必须拒绝掉与这个申请相冲突的预约。 一般来说，如果PP大厦方面事先已经接受了一个会场预约，例如从10日到15日，就不会在接受与之相冲突的预约，例如从12日到17日。不过，有时出于经济利益，PP大厦方面有时会为了接受一个新的会场预约，而拒绝掉一个甚至几个之前预订的预约。 于是，礼堂管理员QQ的笔记本上笔记本上经常记录着这样的信息： 本题中为方便起见，所有的日期都用一个整数表示。例如，如果一个为期10天的会议从“90日”开始到“99日”，那么下一个会议最早只能在“100日”开始。 最近，这个业务的工作量与日俱增，礼堂的管理员QQ希望参加SHTSC的你替他设计一套计算机系统，方便他的工作。这个系统应当能执行下面两个操作： A操作：有一个新的预约是从“start日”到“end日”，并且拒绝掉所有与它相冲突的预约。执行这个操作的时候，你的系统应当返回为了这个新预约而拒绝掉的预约个数，以方便QQ与自己的记录相校对。 B操作：请你的系统返回当前的仍然有效的预约的总数。

---

形式化描述

你需要维护一个 在数轴上的线段 的集合 $S$，支持两种操作：

• A l r 表示将 $S$ 中所有与线段 $[l,r]$ 相交的线段删去，并将 $[l,r]$ 加入
  $S$ 中。
• B 查询 $S$ 中的元素数量。

对于 A 操作，每次还需输出删掉的元素个数。

输入格式

第一行一个正整数 $n$，表示操作个数。
接下来 $n$ 行，每行表示一个操作，都是上面两种中的一个。

输出格式

输出 $n$ 行，每行一个整数，表示对应操作的答案。

样例 #1

样例输入 #1

6
A 10 15
A 17 19
A 12 17
A 90 99
A 11 12
B

样例输出 #1

0
0
2
0
1
2

提示

【数据范围】
对于 $100\%$ 的数据，$1\le n \le 2\times 10^5$，$1\le l \le r \le 10^5$。

参考代码

#include <bits/stdc++.h>
using namespace std;
set<pair<int, int> > s;
int n, x, y;
char o;
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf(" %c", &o);
		if (o == 'A')
		{
			scanf("%d%d", &x, &y);
			set<pair<int, int> >::iterator it = s.lower_bound(make_pair(x, 0));
			int cnt = 0;
			while (it != s.end() && it->second <= y)
			{
				cnt++;
				s.erase(it++);
			}
			s.insert(make_pair(y, x));
			printf("%d\n", cnt);
		}
		else
		{
			printf("%d\n", int(s.size()));
		}
	}
}

题解

P1102 A-B 数对

https://www.luogu.com.cn/problem/P1102

题目描述

出题是一件痛苦的事情！

相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！

好吧，题目是这样的：给出一串数以及一个数字 $C$，要求计算出所有 $A - B = C$ 的数对的个数（不同位置的数字一样的数对算不同的数对）。

输入格式

输入共两行。

第一行，两个整数 $N, C$。

第二行，$N$ 个整数，作为要求处理的那串数。

输出格式

一行，表示该串数中包含的满足 $A - B = C$ 的数对的个数。

样例 #1

样例输入 #1

4 1
1 1 2 3

样例输出 #1

3

提示

对于 $75\%$ 的数据，$1 \leq N \leq 2000$。

对于 $100\%$ 的数据，$1 \leq N \leq 2 \times 10^5$。

保证所有输入数据绝对值小于 $2^{30}$，且 $C \ge 1$。

2017/4/29 新添数据两组

参考代码

#include <bits/stdc++.h>
using namespace std;
int a[200020];
int n, c;
long long z;
int main()
{
	scanf("%d%d", &n, &c);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}
	sort(a, a + n);
	for (int i = 0; i < n; i++)
	{
		z += upper_bound(a, a + n, a[i] + c) - lower_bound(a, a + n, a[i] + c);
	}
	printf("%lld\n", z);
	return 0;
}

题解

P5250 【深基17.例5】木材仓库

https://www.luogu.com.cn/problem/P5250

题目描述

博艾市有一个木材仓库，里面可以存储各种长度的木材，但是保证没有两个木材的长度是相同的。作为仓库负责人，你有时候会进货，有时候会出货，因此需要维护这个库存。有不超过 100000 条的操作：

• 进货，格式1 Length：在仓库中放入一根长度为 Length(不超过 $10^9$) 的木材。如果已经有相同长度的木材那么输出Already Exist。
• 出货，格式2 Length：从仓库中取出长度为 Length 的木材。如果没有刚好长度的木材，取出仓库中存在的和要求长度最接近的木材。如果有多根木材符合要求，取出比较短的一根。输出取出的木材长度。如果仓库是空的，输出Empty。

输入格式

输出格式

样例 #1

样例输入 #1

7
1 1
1 5
1 3
2 3
2 3
2 3
2 3

样例输出 #1

3
1
5
Empty

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
set<int> s;
int n, o, x;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> o >> x;
		if (o == 1) {
			if (!s.insert(x).second) {
				printf("Already Exist\n");
			}
		} else {
			if (s.size()) {
				set<int>::iterator it;
				it = s.lower_bound(x);
				set<int>::iterator ti=it;
				if (ti != s.begin()) {
					ti--;
				}
				if (it != s.end() && abs(*it - x) < abs(x - *ti)) {
					ti = it;
				}
				printf("%d\n", *ti);
				s.erase(ti);
			} else {
				printf("Empty\n");
			}
		}
	}
	return 0;
}

题解

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

https://www.luogu.com.cn/problem/P5266

题目描述

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

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

输入格式

输出格式

样例 #1

样例输入 #1

5
1 lxl 10
2 lxl
3 lxl
2 lxl
4

样例输出 #1

OK
10
Deleted successfully
Not found
0

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
map<string, int> g;
string s;
int n, o;
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> o;
		if (o == 4)
		{
			cout << g.size() << endl;
		}
		else
		{
			cin >> s;
			if (o == 1)
			{
				cin >> g[s];
				cout << "OK" << endl;
			}
			else
			{
				auto it = g.find(s);
				if (it != g.end())
				{
					if (o == 2)
					{
						cout << g[s] << endl;
					}
					else
					{
						g.erase(s);
						cout << "Deleted successfully" << endl;
					}
				}
				else
				{
					cout << "Not found" << endl;
				}
			}
		}
	}
	return 0;
}

题解

P4305 [JLOI2011]不重复数字

https://www.luogu.com.cn/problem/P4305

题目描述

给定 $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$ 位有符号整数范围内。

参考代码

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
	char c=getchar();int x=0,f=1;
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=x*10+c-48;
	return x*f;
}
int t, n, x;
int main()
{
	t = read();
	for (int tt = 0; tt < t; tt++)
	{
		unordered_set<int> s;
		n = read();
		for (int i = 0; i < n; i++)
		{
			x = read();
			if (s.insert(x).second)
			{
				printf("%d ", x);
			}
		}
		printf("\n");
	}
	return 0;
}

题解

set暴力，
unordered_set
unordered_map
没有有序的性质了（不能lower_bound upper_bound）
不需要指定
出题人能不能造一个数据，让unordered_set超时？
能

P1059 [NOIP2006 普及组] 明明的随机数

https://www.luogu.com.cn/problem/P1059

题目描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了$N$个$1$到$1000$之间的随机整数$(N≤100)$，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

输入格式

输入有两行，第$1$行为$1$个正整数，表示所生成的随机数的个数$N$

第$2$行有$N$个用空格隔开的正整数，为所产生的随机数。

输出格式

输出也是两行，第$1$行为$1$个正整数$M$，表示不相同的随机数的个数。

第$2$行为$M$个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

样例 #1

样例输入 #1

10
20 40 32 67 40 20 89 300 400 15

样例输出 #1

8
15 20 32 40 67 89 300 400

提示

NOIP 2006 普及组 第一题

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, a[1000];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	sort(a, a + n);
	n = unique(a, a + n) - a;
	printf("%d\n", n);
	for (int i = 0; i < n; i++) {
		printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');
	}
	return 0;
}

题解

1. set / TreeSet
2. sort unique
3. array

100 300 200 400 -> 1 3 2 4
sort unique lower_bound

P2141 [NOIP2014 普及组] 珠心算测验

https://www.luogu.com.cn/problem/P2141

题目描述

珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。

某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？

最近老师出了一些测验题，请你帮忙求出答案。

(本题目为2014NOIP普及T1)

输入格式

共两行，第一行包含一个整数$n$，表示测试题中给出的正整数个数。

第二行有$n$个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。

输出格式

一个整数，表示测验题答案。

样例 #1

样例输入 #1

4
1 2 3 4

样例输出 #1

2

提示

【样例说明】

由$1+2=3,1+3=4$，故满足测试要求的答案为$2$。

注意，加数和被加数必须是集合中的两个不同的数。

【数据说明】

对于$100\%$的数据，$3 ≤ n ≤ 100$，测验题给出的正整数大小不超过$10,000$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, a[1020];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	int z = 0;
	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if (a[i] + a[j] == a[k]) {
					z++;
					goto end;
				}
			}
		}
		end:;
	}
	printf("%d\n", z);
	return 0;
}

题解

P1125 [NOIP2008 提高组] 笨小猴

https://www.luogu.com.cn/problem/P1125

题目描述

笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！

这种方法的具体描述如下：假设maxn是单词中出现次数最多的字母的出现次数，minn是单词中出现次数最少的字母的出现次数，如果maxn-minn是一个质数，那么笨小猴就认为这是个Lucky Word，这样的单词很可能就是正确的答案。

输入格式

一个单词，其中只可能出现小写字母，并且长度小于$100$。

输出格式

共两行，第一行是一个字符串，假设输入的的单词是Lucky Word，那么输出“Lucky Word”，否则输出“No Answer”；

第二行是一个整数，如果输入单词是Lucky Word，输出maxn-minn的值，否则输出$0$。

样例 #1

样例输入 #1

error

样例输出 #1

Lucky Word
2

样例 #2

样例输入 #2

olympic

样例输出 #2

No Answer
0

提示

【输入输出样例1解释】

单词error中出现最多的字母$r$出现了$3$次，出现次数最少的字母出现了$1$次，$3-1=2$，$2$是质数。

【输入输出样例2解释】

单词olympic中出现最多的字母$i$出现了$1$次，出现次数最少的字母出现了$1$次，$1-1=0$，$0$不是质数。

（本处原题面错误已经修正）

noip2008提高第一题

参考代码

题解

P2814 家谱

https://www.luogu.com.cn/problem/P2814

题目背景

现代的人对于本家族血统越来越感兴趣。

题目描述

给出充足的父子关系，请你编写程序找到某个人的最早的祖先。

输入格式

输入由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系中父亲只有一行，儿子可能有若干行，用 #name 的形式描写一组父子关系中的父亲的名字，用 +name 的形式描写一组父子关系中的儿子的名字；接下来用 ?name 的形式表示要求该人的最早的祖先；最后用单独的一个 $ 表示文件结束。

输出格式

按照输入文件的要求顺序，求出每一个要找祖先的人的祖先，格式为：本人的名字 $+$ 一个空格 $+$ 祖先的名字 $+$ 回车。

样例 #1

样例输入 #1

#George
+Rodney
#Arthur
+Gareth
+Walter
#Gareth
+Edward
?Edward
?Walter
?Rodney
?Arthur
$

样例输出 #1

Edward Arthur
Walter Arthur
Rodney George
Arthur Arthur

提示

规定每个人的名字都有且只有 $6$ 个字符，而且首字母大写，且没有任意两个人的名字相同。最多可能有 $10^3$ 组父子关系，总人数最多可能达到 $5 \times 10^4$ 人，家谱中的记载不超过 $30$ 代。

参考代码

#include <bits/stdc++.h>
using namespace std;
map<string, string> f;
string a, b;
char c;
string F(string s)
{
	while (f.find(s) != f.end())
	{
		s = f[s];
	}
	return s;
}
int main()
{
	while (true)
	{
		cin >> c;
		if (c == '#')
		{
			cin >> a;
		}
		else if (c == '+')
		{
			cin >> b;
			f[b] = a;
		}
		else if (c == '?')
		{
			cin >> b;
			cout << b << ' ' << F(b) << endl;
		}
		else
		{
			break;
		}
	}
}

题解

P3370 【模板】字符串哈希

https://www.luogu.com.cn/problem/P3370

题目描述

如题，给定 $N$ 个字符串（第 $i$ 个字符串长度为 $M_i$，字符串内包含数字、大小写字母，大小写敏感），请求出 $N$ 个字符串中共有多少个不同的字符串。

友情提醒：如果真的想好好练习哈希的话，请自觉，否则请右转PJ试炼场:)

输入格式

第一行包含一个整数 $N$，为字符串的个数。

接下来 $N$ 行每行包含一个字符串，为所提供的字符串。

输出格式

输出包含一行，包含一个整数，为不同的字符串个数。

样例 #1

样例输入 #1

5
abc
aaaa
abc
abcc
12345

样例输出 #1

4

提示

对于 $30\%$ 的数据：$N\leq 10$，$M_i≈6$，$Mmax\leq 15$。

对于 $70\%$ 的数据：$N\leq 1000$，$M_i≈100$，$Mmax\leq 150$。

对于 $100\%$ 的数据：$N\leq 10000$，$M_i≈1000$，$Mmax\leq 1500$。

样例说明：

样例中第一个字符串(abc)和第三个字符串(abc)是一样的，所以所提供字符串的集合为{aaaa,abc,abcc,12345}，故共计4个不同的字符串。

Tip：
感兴趣的话，你们可以先看一看以下三题：

BZOJ3097：http://www.lydsy.com/JudgeOnline/problem.php?id=3097

BZOJ3098：http://www.lydsy.com/JudgeOnline/problem.php?id=3098

BZOJ3099：http://www.lydsy.com/JudgeOnline/problem.php?id=3099

如果你仔细研究过了（或者至少仔细看过AC人数的话），我想你一定会明白字符串哈希的正确姿势的^_

参考代码

#include <bits/stdc++.h>
using namespace std;
unsigned get() {
	string s;
	cin >> s;
	unsigned re = 0;
	for (int i = 0; i < s.size(); i++) {
		re = (re * 131) ^ s[i];
	}
	return re;
}
int main() {
	set<unsigned> s;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		s.insert(get());
	}
	cout << s.size() << endl;
	return 0;
}

题解

P3405 [USACO16DEC]Cities and States S

https://www.luogu.com.cn/problem/P3405

题目描述

To keep his cows intellectually stimulated, Farmer John has placed a large map of the USA on the wall of his barn. Since the cows spend many hours in the barn staring at this map, they start to notice several curious patterns. For example, the cities of Flint, MI and Miami, FL share a very special relationship: the first two letters of "Flint" give the state code ("FL") for Miami, and the first two letters of "Miami" give the state code ("MI") for Flint.

Let us say that two cities are a "special pair" if they satisfy this property and come from different states. The cows are wondering how many special pairs of cities exist. Please help them solve this amusing geographical puzzle!

为了让奶牛在智力上受到刺激，农夫约翰在谷仓的墙上放了一张美国地图。由于奶牛在谷仓里花了很多时间盯着这张地图，他们开始注意到一些奇怪的关系。例如，城市Flint，在MI省，或者Miami在FL省，他们有一种特殊的关系：“Flint”市前两个字母就是“FL”省，迈阿密前两个字母是“MI”省。

让我们说，两个城市是一个“特殊的一对”，如果他们满足这个属性，来自不同的省。奶牛想知道有多少特殊的城市存在。请帮助他们解决这个有趣的地理难题！

输入格式

The first line of input contains $N$ ($1 \leq N \leq 200,000$), the number ofcities on the map.

The next $N$ lines each contain two strings: the name of a city (a string of at least 2 and at most 10 uppercase letters), and its two-letter state code (a string of 2 uppercase letters). Note that the state code may be something like ZQ, which is not an actual USA state. Multiple cities with the same name can exist, but they will be in different states.

输入的第一行包含（），地图上的城市数量。

下一行包含两个字符串：一个城市的名称（字符串至少2个最多10个大写字母），和它的两个字母的州代码（一串2个大写字母）。注意状态代码可能像ZQ，这并不是一个真正的美国。同一名称的多个城市可以存在，但它们将处于不同的州。

输出格式

Please output the number of special pairs of cities.

请输出特殊城市对数。

样例 #1

样例输入 #1

6
MIAMI FL
DALLAS TX
FLINT MI
CLEMSON SC
BOSTON MA
ORLANDO FL

样例输出 #1

1

提示

感谢@何炜华8864 的翻译，并经过kkksc03的修改

参考代码

#include <bits/stdc++.h>
using namespace std;
char a[20], b[20];
int n, x, y, z;
int g[456976];
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%s%s", a, b);
		x = a[0] * 26 + a[1] - 1755;
		y = b[0] * 26 + b[1] - 1755;
		if (x != y)
		{
			z += g[y * 676 + x];
			g[x * 676 + y]++;
		}
	}
	printf("%d\n", z);
	return 0;
}

题解

P5250 【深基17.例5】木材仓库

https://www.luogu.com.cn/problem/P5250

题目描述

博艾市有一个木材仓库，里面可以存储各种长度的木材，但是保证没有两个木材的长度是相同的。作为仓库负责人，你有时候会进货，有时候会出货，因此需要维护这个库存。有不超过 100000 条的操作：

• 进货，格式1 Length：在仓库中放入一根长度为 Length(不超过 $10^9$) 的木材。如果已经有相同长度的木材那么输出Already Exist。
• 出货，格式2 Length：从仓库中取出长度为 Length 的木材。如果没有刚好长度的木材，取出仓库中存在的和要求长度最接近的木材。如果有多根木材符合要求，取出比较短的一根。输出取出的木材长度。如果仓库是空的，输出Empty。

输入格式

输出格式

样例 #1

样例输入 #1

7
1 1
1 5
1 3
2 3
2 3
2 3
2 3

样例输出 #1

3
1
5
Empty

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
set<int> s;
int n, o, x;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> o >> x;
		if (o == 1) {
			if (!s.insert(x).second) {
				printf("Already Exist\n");
			}
		} else {
			if (s.size()) {
				set<int>::iterator it;
				it = s.lower_bound(x);
				set<int>::iterator ti=it;
				if (ti != s.begin()) {
					ti--;
				}
				if (it != s.end() && abs(*it - x) < abs(x - *ti)) {
					ti = it;
				}
				printf("%d\n", *ti);
				s.erase(ti);
			} else {
				printf("Empty\n");
			}
		}
	}
	return 0;
}

题解

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

https://www.luogu.com.cn/problem/P5266

题目描述

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

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

输入格式

输出格式

样例 #1

样例输入 #1

5
1 lxl 10
2 lxl
3 lxl
2 lxl
4

样例输出 #1

OK
10
Deleted successfully
Not found
0

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
map<string, int> g;
string s;
int n, o;
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> o;
		if (o == 4)
		{
			cout << g.size() << endl;
		}
		else
		{
			cin >> s;
			if (o == 1)
			{
				cin >> g[s];
				cout << "OK" << endl;
			}
			else
			{
				auto it = g.find(s);
				if (it != g.end())
				{
					if (o == 2)
					{
						cout << g[s] << endl;
					}
					else
					{
						g.erase(s);
						cout << "Deleted successfully" << endl;
					}
				}
				else
				{
					cout << "Not found" << endl;
				}
			}
		}
	}
	return 0;
}

题解

P1918 保龄球

https://www.luogu.com.cn/problem/P1918

题目描述

DL 算缘分算得很烦闷，所以常常到体育馆去打保龄球解闷。因为他保龄球已经打了几十年了，所以技术上不成问题，于是他就想玩点新花招。

DL 的视力真的很不错，竟然能够数清楚在他前方十米左右每个位置的瓶子的数量。他突然发现这是一个炫耀自己好视力的借口——他看清远方瓶子的个数后从某个位置发球，这样就能打倒一定数量的瓶子。

1 OOO

2 OOOO

3 O

4 OO

如上图，每个“O”代表一个瓶子。如果 DL 想要打倒 3 个瓶子就在 1 位置发球，想要打倒 4 个瓶子就在 2 位置发球。

现在他想要打倒 m 个瓶子。他告诉你每个位置的瓶子数，请你给他一个发球位置。

输入格式

输入文件名为 bowling.in。

第一行包含一个正整数 n，表示位置数。

第二行包含 n 个正整数，第 i 个数。表示第 i 个位置的瓶子数，保证各个位置的瓶子数不同。

第三行包含一个正整数 Q，表示 DL 发球的次数。

第四行至文件末尾，每行包含一个正整数 m，表示 DL 需要打倒 m 个瓶子。

输出格式

输出文件名为 bowling.out。

共 Q 行。每行包含一个整数，第 i 行的整数表示 DL 第 i 次的发球位置。若无解，则输出 0。

样例 #1

样例输入 #1

5
1 2 4 3 5
2
4
7

样例输出 #1

3
0

提示

【数据范围】

对于 50%的数据，1 ≤ n,Q ≤ 1000，1 ≤ai,M ≤ 10^5

对于 100%的数据，1 ≤ n,Q ≤ 100000，1 ≤ai,M ≤ 10^9

参考代码

#include <bits/stdc++.h>
using namespace std;
map<int, int> g;
int n, x;
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &x);
		g[x] = i;
	}
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &x);
		printf("%d\n", g[x]);
	}
	return 0;
}

题解

P4305 [JLOI2011]不重复数字

https://www.luogu.com.cn/problem/P4305

题目描述

给定 $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$ 位有符号整数范围内。

参考代码

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
	char c=getchar();int x=0,f=1;
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=x*10+c-48;
	return x*f;
}
int t, n, x;
int main()
{
	t = read();
	for (int tt = 0; tt < t; tt++)
	{
		unordered_set<int> s;
		n = read();
		for (int i = 0; i < n; i++)
		{
			x = read();
			if (s.insert(x).second)
			{
				printf("%d ", x);
			}
		}
		printf("\n");
	}
	return 0;
}

题解

set暴力，
unordered_set
unordered_map
没有有序的性质了（不能lower_bound upper_bound）
不需要指定
出题人能不能造一个数据，让unordered_set超时？
能

P3879 [TJOI2010] 阅读理解

https://www.luogu.com.cn/problem/P3879

题目描述

英语老师留了 $N$ 篇阅读理解作业，但是每篇英文短文都有很多生词需要查字典，为了节约时间，现在要做个统计，算一算某些生词都在哪几篇短文中出现过。

输入格式

第一行为整数 $N$ ，表示短文篇数，其中每篇短文只含空格和小写字母。

按下来的 $N$ 行，每行描述一篇短文。每行的开头是一个整数 $L$ ，表示这篇短文由 $L$ 个单词组成。接下来是 $L$ 个单词，单词之间用一个空格分隔。

然后为一个整数 $M$ ，表示要做几次询问。后面有 $M$ 行，每行表示一个要统计的生词。

输出格式

对于每个生词输出一行，统计其在哪几篇短文中出现过，并按从小到大输出短文的序号，序号不应有重复，序号之间用一个空格隔开（注意第一个序号的前面和最后一个序号的后面不应有空格）。如果该单词一直没出现过，则输出一个空行。

样例 #1

样例输入 #1

3
9 you are a good boy ha ha o yeah
13 o my god you like bleach naruto one piece and so do i
11 but i do not think you will get all the points
5
you
i
o
all
naruto

样例输出 #1

1 2 3
2 3
1 2
3
2

提示

对于 $30\%$ 的数据， $1\le M\le 10^3$ 。

对于 $100\%$ 的数据，$1\le M\le 10^4$，$1\le N\le 10^3$ 。

每篇短文长度（含相邻单词之间的空格）$\le 5\times 10^3$ 字符，每个单词长度 $\le 20$ 字符。

每个测试点时限 $2$ 秒。

感谢@钟梓俊添加的一组数据。

参考代码

#include <bits/stdc++.h>
using namespace std;
map<string, vector<int> > g;
int n, m, l;
string s;
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> l;
		for (int j = 0; j < l; j++)
		{
			cin >> s;
			if (g[s].empty() || g[s].back() != i)
			{
				g[s].push_back(i);
			}
		}
	}
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> s;
		if (g.find(s) != g.end())
		{
			for (int j: g[s])
			{
				cout << j << " ";
			}
		}
		cout << endl;
	}
	return 0;
}

题解

P1059 [NOIP2006 普及组] 明明的随机数

https://www.luogu.com.cn/problem/P1059

题目描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了$N$个$1$到$1000$之间的随机整数$(N≤100)$，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

输入格式

输入有两行，第$1$行为$1$个正整数，表示所生成的随机数的个数$N$

第$2$行有$N$个用空格隔开的正整数，为所产生的随机数。

输出格式

输出也是两行，第$1$行为$1$个正整数$M$，表示不相同的随机数的个数。

第$2$行为$M$个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

样例 #1

样例输入 #1

10
20 40 32 67 40 20 89 300 400 15

样例输出 #1

8
15 20 32 40 67 89 300 400

提示

NOIP 2006 普及组 第一题

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, a[1000];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	sort(a, a + n);
	n = unique(a, a + n) - a;
	printf("%d\n", n);
	for (int i = 0; i < n; i++) {
		printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');
	}
	return 0;
}

题解

1. set / TreeSet
2. sort unique
3. array

100 300 200 400 -> 1 3 2 4
sort unique lower_bound

P1503 鬼子进村

https://www.luogu.com.cn/problem/P1503

题目背景

小卡正在新家的客厅中看电视。电视里正在播放放了千八百次依旧重播的《亮剑》，剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队，于是独立团与鬼子展开游击战。

题目描述

县城里有 $n$ 个用地道相连的房子，第 $i$ 个只与第 $i-1$ 和第 $i+1$ 个相连。这时有 $m$ 个消息依次传来：

1. 若消息为 D x：鬼子将 $x$ 号房子摧毁了，地道被堵上。

2. 若消息为 R ：村民们将鬼子上一个摧毁的房子修复了。

3. 若消息为 Q x：有一名士兵被围堵在 $x$ 号房子中。

李云龙收到信息很紧张，他想知道每一个被围堵的士兵能够到达的房子有几个。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，有如题目所说的三种信息共 $m$ 条。

输出格式

对于每一个被围堵的士兵，输出该士兵能够到达的房子数。

样例 #1

样例输入 #1

7 9
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4

样例输出 #1

1
0
2
4

提示

$1\leq n,m\leq 5\times 10^4$。

若士兵被围堵在摧毁了的房子中，那只能等死了。。。。。。

参考代码

#include <bits/stdc++.h>
using namespace std;
stack<int> a;
char o[2];
set<int> s;
int n, m, x;
int main() {
	scanf("%d%d", &n, &m);
	s.insert(0);
	s.insert(n+1);
	for (int i = 0; i < m; i++) {
		scanf("%s", o);
		if (o[0] == 'D') {
			scanf("%d", &x);
			s.insert(x);
			a.push(x);
		} else if (o[0] == 'R') {
			s.erase(a.top());
			a.pop();
		} else if (o[0] == 'Q') {
			scanf("%d", &x);
			if (s.find(x) != s.end()) {
				printf("0\n");
			} else {
				set<int>::iterator it;
				it = s.lower_bound(x);
//				it = s.upper_bound(x);
				set<int>::iterator ti=it;
				ti--;
				printf("%d\n", *it - *ti - 1);
			}
		}
	}
	return 0;
}

题解

P2073 送花

https://www.luogu.com.cn/problem/P2073

题目背景

小明准备给小红送一束花，以表达他对小红的爱意。他在花店看中了一些花，准备用它们包成花束。

题目描述

这些花都很漂亮，每朵花有一个美丽值W，价格为C。

小明一开始有一个空的花束，他不断地向里面添加花。他有以下几种操作：

操作 含义

1 W C 添加一朵美丽值为W，价格为C的花。

3 小明觉得当前花束中最便宜的一朵花太廉价，不适合送给小红，所以删除最便宜的一朵花。

2 小明觉得当前花束中最贵的一朵花太贵，他心疼自己的钱，所以删除最贵的一朵花。

-1 完成添加与删除，开始包装花束

若删除操作时没有花，则跳过删除操作。

如果加入的花朵价格已经与花束中已有花朵价格重复，则这一朵花不能加入花束。

请你帮小明写一个程序，计算出开始包装花束时，花束中所有花的美丽值的总和，以及小明需要为花束付出的总价格。

输入格式

若干行，每行一个操作，以-1结束。

输出格式

一行，两个空格隔开的正整数表示开始包装花束时，花束中所有花的美丽值的总和。以及小明需要为花束付出的总价格。

样例 #1

样例输入 #1

1 1 1
1 2 5
2
1 3 3
3
1 5 2
-1

样例输出 #1

8 5

提示

对于20%数据，操作数<=100，1<=W,C<=1000。

对于全部数据，操作数<=100000,1<=W,C<=1000000。

参考代码

#include <bits/stdc++.h>
using namespace std;
map<int, int> g;
int main() {
	while (true) {
		int o, x, y;
		scanf("%d", &o);
		if (o == 1) {
			scanf("%d%d", &x, &y);
			if (g.find(y) == g.end()) {
				g[y] = x;
			}
		} else if (o == 2) {
			if (g.size() > 0) {
				g.erase(--g.end());
			}
		} else if (o == 3) {
			if (g.size() > 0) {
				g.erase(g.begin());
			}
		} else {
			break;
		}
	}
	long long s1 = 0;
	long long s2 = 0;
	for (map<int, int>::iterator it = g.begin(); it != g.end(); it++) {
		s1 += it->first;
		s2 += it->second;
	}
	cout << s2 << ' ' << s1 << endl;
	return 0;
}

题解

P2141 [NOIP2014 普及组] 珠心算测验

https://www.luogu.com.cn/problem/P2141

题目描述

珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。

某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？

最近老师出了一些测验题，请你帮忙求出答案。

(本题目为2014NOIP普及T1)

输入格式

共两行，第一行包含一个整数$n$，表示测试题中给出的正整数个数。

第二行有$n$个正整数，每两个正整数之间用一个空格隔开，表示测试题中给出的正整数。

输出格式

一个整数，表示测验题答案。

样例 #1

样例输入 #1

4
1 2 3 4

样例输出 #1

2

提示

【样例说明】

由$1+2=3,1+3=4$，故满足测试要求的答案为$2$。

注意，加数和被加数必须是集合中的两个不同的数。

【数据说明】

对于$100\%$的数据，$3 ≤ n ≤ 100$，测验题给出的正整数大小不超过$10,000$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, a[1020];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	int z = 0;
	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if (a[i] + a[j] == a[k]) {
					z++;
					goto end;
				}
			}
		}
		end:;
	}
	printf("%d\n", z);
	return 0;
}

题解

sort 结构体排序
pair<int, int>

https://codeforces.com/
https://atcoder.jp/
https://www.luogu.com.cn/

https://en.cppreference.com/w/
http://www.cplusplus.com/reference/

STL Algorithm
sort

STL Container

Java

HashSet
TreeSet
TreeMap
ArrayList

1. insert an element
2. query lower_bound / upper_bound

TreeSet s;
for (int i: s)
{
if (i % 2 == 1)
{
s.erase(i);
}
}

multiset in Java

1. add a new class member index
2. use tree map to store the number of occurence.

STL

next_permutation
2 1 4 3 -> 2 3 1 4

inplace_merge

Contestants using C++ may find the following code from KACTL helpful. Known as the Barrett reduction, it allows you to compute a%b several times faster than usual, where b>1

is constant but not known at compile time. (we are not aware of such an optimization for Java, unfortunately).

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef __uint128_t L;
struct FastMod {
	ull b, m;
	FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
	ull reduce(ull a) {
		ull q = (ull)((L(m) * a) >> 64);
		ull r = a - q * b; // can be proven that 0 <= r < 2*b
		return r >= b ? r - b : r;
	}
};
FastMod F(2);

int main() {
	int M = 1000000007; F = FastMod(M);
	ull x = 10ULL*M+3; 
	cout << x << " " << F.reduce(x) << "\n"; // 10000000073 3
}

pair<int, int>

vector

for (set<int>::iterator it = s.begin(); it != s.end(); it++)
{
	cout << *it << endl;
}

for (int i: s)
{
	cout << i << endl;
}

P2061 [USACO07OPEN]City Horizon S
(pos, height)

P4404 [JSOI2010]缓存交换
+1
+2
+3 -2

+2 -1

1 2 3 1 2 3
4 5 6
4 5 6
4 5 6
4 5 6
4 5 6
4 5 6
4 5 6
4 5 6
4 5 6
4 5 6
.....

需要一个有序集合，需要删除 最近一次用最晚的元素

集合存储 (下一次使用的时间，元素是什么)
可以很方面的找到 下一次使用的时间 最大的是什么
把一个元素加入集合的时候，如何知道下一次使用的时间

下标 0 1 2 3 4 5
数值 1 2 3 1 2 3
下次 3 4 5 6 6 6

下标 0 1 2 3 4 5
数值 1 1 1 1 1 1
下次 1 2 3 4 5 6

{}
{1}

for

P1918 保龄球

sort binary_seart
sort lower_bound

map

map<int, int>

wrong:
s.erase(it);
it++

right:
s.erase(it++)

increase it get the new value
erase it
assign the new value to it

P2161 [SHOI2009]会场预约

https://www.luogu.com.cn/blog/Nartsam/solution-p2161
重载运算符时可以发生
a < b
b < c
a == c
的情况

用 s.find() 直接找冲突区间

P2234 [HNOI2002]营业额统计

P3374 【模板】树状数组 1

brute force
change O(1)
query O(n)

prefix sum
change O(n)
query O(1)

blocking algorithm
change O(2)
query O(sqrt(n))

3-layer blocking algorithm
change O(3)
query O(n^(1/3))

segment tree / binary index tree
change O(log n)
query O(log n)

C++
比较快
功能比较多

https://www.luogu.com.cn/problem/P1059

1. 计数

sort(a, a + n);
int n = unique(a, a + n) - a;

1 1 2 2 1 1 2 2
1 2 1 2

100 200 300 400
1 2 3 4

结构体
排序
函数返回多个值

sort
set / Java TreeSet
unordered_set
map

https://www.luogu.com.cn/
中文，使用方便

http://codeforces.com/
英文，使用方便

http://atcoder.jp/
英文，题目比较偏

删除最大值 必须是
s.erase(--s.end());

s.erase(s.rbegin());

// char a, b;
short a, b;
(a - b)

#include <bits/stdc++.h>
using namespace std;
int main()
{
	set<int> s;
	for (int i = 0; i < 1000000; i++)
	{
		s.insert(i);
	}
	long long c = 0;
	for (int i = 0; i < 1000000; i++)
	{
		c += *s.lower_bound(i);
		c += *lower_bound(s.begin(), s.end(), i);
	}
	cout << c << endl;
	return 0;
}

char o[2]
scanf("%s", o);
if (o[0] == 'D')

char o;
scanf(" %c", &c);
if (o == 'D')

char o;
cin >> o;
if (o == 'D')

s.erase(it);
it++;

s.erase(it++);

s.erase(it)
it = it+1;

https://www.luogu.com.cn/problem/P4404

首先用 map 对于每个 i 求出 p[i]
p[i] 表示下一次出现 a[i] 是什么位置
p[i] > i && a[p[i]] == a[i] && p[i] 最小
如果 i位置 之后再也没出现过 a[i]
那么 p[i] = n

for (pair<int, int> i: g)
{
i.first;
i.second;
}

需要一个set 维护
(下次使用的时间, 这是什么内存)

vector 变长数组
图论

初始16个位置
每次用完都翻倍
16 -> 32 -> 64 -> 128
排序/分组
输入一些名字和年龄，将所有人按年龄排序

和 链表

详细的自己查 C++ Reference

priority_queue 有 top
queue 只有 front

set 是 begin 和 end
set 有 iterator

priority queue
queue
stack
没有 iterator