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

题目大意：

1620C BA-String
题目大意：给你一个长度为N的字符串，包含a和，你可以将每个转换成(0-k)个’b’，现在要求你能得到的字典序第x大的字符串。

解：

看似非常简单，实际上就是一个进制问题，每一串连续的表示nk个单位，而一个单位的大小则是后一个串能表示的最大数量，可以用dp来记录也可以纯粹地用函数去计算，n只有2000，不用担心t的问题，求答案时将单位从大到小除一下取值就行。
问题在于，虽然题面说了x的大小不会大于1e18，但你的单位的大小却有可能超过1e18，超过1e18之后下场自然是溢出，溢出就会造成错误的判断，于是你需要用取对数的方法来判断你即将得到的单位是否超过1e18，但这依然不够，因为有可能你在判断溢出的过程中它就已经溢出了，所以建议是将乘区的两部分分别转化为double再去计算log10的值，log2应该也行。
Debug了好久，总之就是很sb，除了知道要判溢出以外什么都没学到。
本来不想专门写一篇的，结果还是写了……

代码

代码
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

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#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 dp[2005],seg[2005],ans[2005];
char a[2005],res[4000005];

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll t;
	cin >> t;
	while (t--) {
		ll n, k, x;
		cin >> n >> k >> x;
		scanf("%s", a);
		ll xb = 0,tmp=0;
		for (ll i = 0; i < n; i++) {
			if (a[i] == '*') {
				tmp++;
				if (i == n - 1 || a[i + 1] == 'a') {
					seg[xb++] = tmp;
					tmp = 0;
				}
			}
		}
		dp[0] = 1;
		int ii = 0;
		for (ll i = 1; i <= xb; i++) {
			dp[i] = dp[i - 1] * (1+seg[xb - i]*k);
			ii = i;
			if (i<xb&&log10((double)dp[i])+log10((double)(1+seg[xb-i-1]*k))>=18) {
				ii++;
				break;
			}
			
		}
		ll xx = ii;
		x--;
		while (xx) {
			if (x < dp[xx-1]) {
				ans[xb - xx] = 0;
			}
			else {
				ans[xb - xx] = x / dp[xx - 1];
				x -= x / dp[xx - 1] * dp[xx - 1];
			}
			xx--;
		}
		ll stp = 0,sg=0;
		for (ll i = 0; i < n; i++) {
			if (a[i] == '*') {
				for (int j = 0; j < ans[sg]; j++) {
					res[stp++] = 'b';
				}
				i += seg[sg] - 1;
				sg++;
			}
			else res[stp++] = 'a';
		}
		for (ll i = 0; i < stp; i++) {
			printf("%c", res[i]);
		}
		printf("\n");
		clr(ans, 2005);
	}

}