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

题目大意：

CF1608C Game Master
题目大意，有n个人（n范围为1e5），分别在a场和b场上有a[i]，b[i]战力，现在你来分配对战顺序和对战场地来使得其中一人最终获胜，问有哪些人可以获胜。

解：

其实是道思维题，我们首先用结构体记录，然后按a[i]上的战力从大到小排序，最大的那个显然是可以赢的，只要在a场上一路暴杀下去就可以了，那么之后呢？
假设刚刚这个人为p，如果有一个人在b场上可以打赢p，那么他就可以赢得比赛，我只要让p先把其他人鲨完再输给他就行了，换句话说，只要在b场上能够打赢p的就能赢。
也就是说，b[i]>b[p]的都能赢。
按b场战力顺序排序，顺序找到b[p]的位置就行（为什么是顺序而不是二分接下来会说，实际上要记录答案也不能二分吧）。在查找的过程中更新一个a[i]的最小值，至于为什么不用多说了。
没错，赢了能赢的就能赢。
接下来再一次遍历a场战力排序的那个数组，只要a[i]大于上轮在b里找到的最小值就能赢，同时再更新b组中的最小值，一直往复更新，每次搜索的时候从上次的最小值到这次的最小值顺序搜索，复杂度不会超过O(n)，直到我无法再找到任何一个大于那个最小值的数，剩下的人就赢不了了。
吐槽一下，题目的标签有dfs，有datastructure，有dp，却没有sorting啊，明明只要sort就结束了。

代码

代码
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
81
82
83
84
85
86
87

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <set>
#include <cstring>
#include <string>
#define ll long long
#define maxn 100005
#define mdl 998244353
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
struct node {
	ll a, b, num, avlb;
	friend bool operator<(node n1, node n2) {
		return n1.a < n2.a;
	}
}ply[maxn];
bool cmp(node n1, node n2) {
	return n1.num < n2.num;
}
int main()
{
	cfast;
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		int f1 = 0,f2=0;
		ll ma1=0, ma2=0;
		for (int i = 0; i < n; i++) {
			cin >> ply[i].a;
			ply[i].num = i;
			ply[i].avlb = 0;
			if (ply[i].a > ma1) {
				ma1 = ply[i].a;
				f1 = i;
			}
		}
		for (int i = 0; i < n; i++) {
			cin >> ply[i].b;
			if (ply[i].b > ma2) {
				ma2 = ply[i].b;
				f2 = i;
			}
		}
		ply[f1].avlb = 1;
		ply[f2].avlb = 1;
		ll aneed = ply[f2].a,bneed=ply[f1].b;
		ll last = n;
		sort(ply, ply + n);
		int f = 1;
		while (f == 1) {
			f = 0;
			for (int i = last-1; i >=0; i--) {
				if (ply[i].b > bneed) {
					f = 1;
					for (int j = i; j < last; j++) {
						ply[j].avlb = 1;
						bneed = min(bneed, ply[j].b);
					}
					last = i;
					break;
				}
			}
		}
		sort(ply, ply + n, cmp);
		for (int i = 0; i < n; i++)cout << ply[i].avlb;
		cout << endl;
	}


}
/*
2
1 3 1 2 3
2 6 -1 4 -2 3 -2 3
*/