把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

CF 1619E Mex and Increments
题目大意：给一个大小为N的数组(N范围为2e5)，要求能够使数组的MEX等于i(0<=i<=n)时最小的操作次数，操作为将数组中的一个数+1，要求输出每个i对应的最小次数，如果不能做到就输出-1。

解：

好烦这种MEX的题啊……
MEX要求的是整个数组的MEX，可以轻松发现，MEX的大小和顺序无关，所以首先我们将数组排序一下。
首先，如果MEX要等于i，那么前面的i个数必须是从0到i-1的数，因此如果前面的数中出现了无法变成这些数的数（即大于他们对应位置应该成为的值的数），那么我就无法得到i，化为代数形式也就是：如果a[i]>i，那么i就无法得到，而且之后的i都无法得到了。
那么接下来就要开始讨论如何处理i前面的数才能达到结果了……
（少女思考中……）
可以想出对于每个i，我们的操作分为两个部分，一部分是将小于i的数通过操作使其形成从0到i-1各有至少一个状态，另一部分是将所有等于i的数+1。其中第二种是没有继承性的，也就是说我在i的时候将多少个i加了1对于i+1并没有任何影响，而第一种操作则是拥有继承性的，因为我要组成0-i，首先我依然要组一次0-(i-1)，也就是说，这是个无后效性的最优子问题！
接下来是dp部分，如果说在i-1的时候我们一共需要k次操作来形成0-(i-2)，那么在处理i的时候我们需要来形成0-(i-1)的操作数量就是k+一个数值C，这个数值是将一个不等于i-1的数变为i-1的最小需要的步数，那么如何获得它呢？二分。
使用cnt数组记录下原有数组中每个数的数量，如果cnt>=2则意味着这个数可以用来操作（因为自己也要保留一份嘛），在获取数值C时二分搜索到最大的cnt>=2的数，同时将其cnt值减一表示我已经用过一次了。
dp只需要一维就行了，表示处理数i时第一部分操作需要的操作量，最后每一位i的答案则是dp[i]+cnt[i]（这个cnt需不需要另行拷贝呢？答案是不需要，原因自己想）。
虽然烦，不过还是挺有意思的，这题与其说是dp，不如说模拟意味很重呢。

代码

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cstring>
#include <string>
#define ll long long
#define maxn 200005
#define mdl 998244353
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
using namespace std;
ll a[maxn],cnt[maxn],dp[maxn],ans[maxn];
ll vct[maxn],removed[maxn],to[maxn];
int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll t;
	cin >> t;
	while (t--) {
		
		ll n;
		scanf("%lld", &n);
		ll siz = 1;
		for (ll i = 0; i < n; i++) {
			scanf("%lld", &a[i]);
			cnt[a[i]]++;
			if (cnt[a[i]] >= 2) {
				vct[siz++] = a[i];
			}
		}
		sort(a, a + n);
		ll f = 0;
		dp[0] = 0;
		sort(vct+1, vct + siz+1);
		for (ll i = 0; i <= n; i++) {
			if (i&&a[i - 1] >= i) {
				f = 1;
				ans[i] = -1;
			}
			if (f == 1) {
				ans[i] = -1;
				printf("%lld ", ans[i]);
				continue;
			}
			if (i&&cnt[i - 1] == 0) {
				ll left = 1, right = siz+1;
				while (left < right - 1) {
					ll mid = (left + right) / 2;
					if (vct[mid] >= i)right = mid;
					else left = mid;
				}
				int g = left;
				while (removed[vct[left]] == 1) {
					if (to[left] != 0)left = to[left];
					else
						left--;
				}
				if(left<g)to[g] = left;
				dp[i] = dp[i - 1] + (i - 1 - vct[left]);
				cnt[vct[left]]--;
				if (cnt[vct[left]] == 1)removed[vct[left]] = 1;
			}
			else dp[i] = dp[i - 1];
			ans[i] = dp[i] + cnt[i];
			printf("%lld ", ans[i]);
		}
		printf("\n");
		clr(vct, n+1);
		clr(cnt, n+1);
		clr(removed, n+1);
		clr(to, n+1);
	}
}