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

题目大意：

CF1537 E2 Erase and Extend (hard version)
题目大意：一个字符串（5e5），你可以消去其结尾，也可以将其整个扩大两倍，求得任意次操作后使得字符串长度达到k的时候字典序最小的字符串。

解：

经过证明（其实一想就知道）问题可以转化为求得一个前缀，使得这个前缀一直延续到k后字典序最小。那么这个前缀满足的条件显然是：放大n倍直到其与原本字符串中存在不同的字符时，放大后的前缀比原字符串小。
但由于无法直接枚举前缀的分界点，这里采用动态维护的方法，即当认同一个点为前缀分界点的时候去证明之后合格。
那么怎么去选取分界点呢？关键在于第一个字符，可以很容易发现，复制一次之后第二段的开头相等于第一个字符，那么如果字符串里原本这个位置是大于这个字符的，复制一定更优，如果是小于，那么显然不能去取这个位置，所以只有当前缀头的字符和开头字符相等时才有去继续往后讨论的必要。
而一旦相等，往后的讨论就变成了一个相同的子问题，即从第二段开头到第一段开头长度相等的区间内谁的字典序更小，如果第一段更小，那么直接让它去取代第二段，否则把整个两段作为新的前缀然后继续向下讨论。
注意扩展的时候如果遇到了比开头字符小的字符，那么是可以无条件将其加入前缀中的。
有非常多的细节值得注意，但只要理清思维之后也没有这么复杂，关键是第一段到第二段的重复问题转移，使得这道显然是字符串的题目也有了dp的味道（虽然tag里没有）。
非常考验耐心和细心的题目，建议每天进行一个顾的回。

代码

代码
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
88
89
90
91
92

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#include <fstream>
#define ll long long
#define maxn 500005
#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);
#define pll pair<ll,ll>
#define pii pair<int,int>
#define inc(i,a,n) for(int i=a;i<n;i++)
#define vset(a,n,m) for(ll i=0;i<n;i++)a[i]=m;
#define endl '\n'
using namespace std;
string bs;
int main() {
	cfast;
	int n, k;
	cin >> n >> k;
	string str;
	cin >> str;
	char tc = str[0];
	int bst = 0;
	int f = 0;
	int flg = 0;
	inc(i, 1, n) {
		if (f == 1)break;
		if (str[i] < tc) {
			flg = 1;
			bst=i;
		}
		else if (str[i] == tc) {
			if (flg == 0) {
				bst = i;
				continue;
			}
		//	cout << "i=" << i << endl;
			f = 1;
			int j;
			int g = 0;
			for (j = i + 1; j < min(n,i+i); j++) {
				if (str[j] < str[j - i]) {
					f = 0;
					bst = j;
				//	cout << "bst=" << bst << endl;
					break;
				}
				if (str[j] != str[j - i]) {
					g = 1;
				}
				if (str[j] > str[j - i]) {
					break;
				}
			}
			if (g == 0) {
				f = 0;
				//bst = min(bst + i, n - 1);
			}
			i = j;
		}
		else {
			break;
		}
	}
	int tmpk = 0;
	string ans = "";
	while (tmpk < k) {
		inc(i, 0, bst+1) {
			ans += str[i];
			tmpk++;
			if (tmpk == k)break;
		}
	}
	cout << ans << endl;
}
/*
2022.4.21   (13:00 - 13:22) - (14:03 - 15:35)

*/