算法复键——5道ABC F题

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162058972

ABC 462 F（动态规划）

显然dp

设 dp(i,j,k)dp(i,j,k) 表示前 ii 个字符，目前的贡献为 jj ，最后两个字母为 kk 的方案数。

jj 最大为 KK ， 但可能为负，但顶多-1.

kk 的话其实本质只需要区分三种状态 ABAB 、 XAXA 、 XXXX 。只有这三种状态是必要的

然后转移的话，我们在每个 ABC 的末尾计算贡献。如果本来可以，现在不行，就-1。如果本来不行，现在可以，就+1

done…

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
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
#define N 300010
//#define mo
#define M 15
int n, m, i, j, k, T;
int f[M][3], g[M][3], ans, mx, a[N], K, n1, n2; 
char s[N]; 

int Z1(int x) {
	return x + 2; 
}

int Z2(char a, char b) {
	if(a == 'A' && b == 'B') return 0; 
	if(b == 'A') return 1; 
	return 2; 
}

int N2(int k, char c) {
	if(k == 1 && c == 'B') return 0; 
	if(c == 'A') return 1; 
	return 2; 
}

int N1(int i, int j, int k, char c, int op) {
	int cnt = 0; 
	if(a[i]) cnt = -1; 
	if(k == 0 && c == 'C') ++cnt; 
	j += cnt; 
	if(j < -2 || j > K) return -1; 
//	if(cnt == 0 && op == 1) return -1; 
	return j + 2; 
}

void Min(int &a, int b) {
	a = min(a, b); 
}

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
	T = read();
	while(T--) {
		scanf("%s", s + 1); n = strlen(s + 1); 
		for(i = 3; i <= n; ++i) {
			if(s[i] == 'C' && s[i - 1] == 'B' && s[i - 2] == 'A') a[i] = 1; 
			else a[i] = 0; 
		}
//		for(i = 1; i <= n; ++i) debug("%d ", a[i]); debug("\n"); 
		K = read(); 
		memset(f, 0x3f, sizeof(f)); 
		memset(g, 0x3f, sizeof(g)); 
		f[Z1(0)][2] = 0; mx = f[Z1(0)][0]; 
		for(i = 1; i <= n; ++i) {
			for(j = -2; j <= K; ++j) {
				for(k = 0; k <= 2; ++k) {
					if(f[Z1(j)][k] == mx) continue; 
//					debug("[%d](%d %d) %d\n", i - 1, j, k, f[Z1(j)][k]); 
					for(char c = 'A'; c <= 'C'; ++c) {
						n1 = N1(i, j, k, c, 1); 
						n2 = N2(k, c); 
						if(n1 == mx) continue; 
						Min(g[n1][n2], f[Z1(j)][k] + 1); 
//						debug("Go to %d %d [%d]\n", n1, n2, g[n1][n2]); 
					}
					n1 = N1(i, j, k, s[i], 0); 
					n2 = N2(k, s[i]); 
					if(n1 == mx) continue; 
					Min(g[n1][n2], f[Z1(j)][k]); 
				}
			}
			for(j = -2; j <= K; ++j) 	
				for(k = 0; k <= 2; ++k) {
//					debug("g[%d][%d] = %d\n", j, k, g[j][k]); 
					f[Z1(j)][k] = g[Z1(j)][k], g[Z1(j)][k] = mx; 
				}
		}
		for(k = 0, ans = mx; k <= 2; ++k) ans = min(ans, f[Z1(K)][k]); 
		printf("%d\n", ans == mx ? -1 : ans); 
	}

	return 0;
}



ABC 461 F（搜索、计数）

不难发现，合法的状态数（在不考虑排列的情况下）必然不多，于是我们可以预处理因子后直接搜索，搜索过程记录当前有多少个数和数的和。最后拿和乘以排列数即可。

但直接这样子做会T掉，我们尝试把数从大往小排序，然后就过了

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
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
#define mo 998244353
#define N 2010
int n, m, i, j, k, T;
int fac[N], ans; 
unordered_map<int, bool>mp;  
vector<int>v, v2; 

void dfs(int n, int stp, int sum, int i) {	
	for(; i < m; ++i) {
		if(n == v[i]) {
			ans += (sum + n) % mo * fac[stp + 1] % mo; 
			ans %= mo; 
		}
		if(n % v[i] == 0) {
			dfs(n / v[i], stp + 1, sum + v[i], i + 1); 
		}
	}
}

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T = read();
//	while(T--) {
//
//	}
	n = read(); 
	for(i = fac[0] = 1; i <= 2000; ++i) 
		fac[i] = fac[i - 1] * i % mo; 
	for(i = 1; i * i <= n; ++i) {
		if(n % i == 0 && i * i != n) v.pb(i), v.pb(n / i); 
		else if(n % i == 0) v.pb(i);  
	} 
	m = v.size(); 
	sort(v.begin(), v.end()); 
	reverse(v.begin(), v.end()); 
	dfs(n, 0, 0, 0);  
	printf("%lld\n", ans); 
	return 0;
}


ABC 460 F（树、dfs序、线段树）

在这里插入图片描述

题目本质是动态求树的直径。

动态求树的直径是套路，先跑出dfn序，然后用线段树维护即可。

具体得，我们要维护区间最深点、区间最浅点，区间答案，区间左+中最大值，区间中+右最大值。

用这几个就能拼凑出答案了。

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 100010
int n, m, i, j, k, T; 
int x, y; 
int dep[N], dfn[N << 2], q, rt, cnt; 
int c[N << 2], cale[N << 2]; 
vector<int>v[N]; 

void dfs(int x, int fa) {
	dfn[++cnt] = x; dep[x] = dep[fa] + 1; 
	c[x] = cnt; cale[cnt] = 1; 
	for(int y : v[x]) 
		if(y != fa) {
			dfs(y, x);  
			dfn[++cnt] = x; 
		}
}

struct Segment_tree {
	int tot, ls[N << 4], rs[N << 4]; 
	int ans[N << 4], depmx[N << 4], depmn[N << 4], ld[N << 4], rd[N << 4]; 
	int legal[N << 2]; 
	void push_up(int k) {
//		legal[k] = (legal[ls[k]] | legal[rs[k]]); 
//		if(!legal[k]) return ; 
//		int x = 0; 
//		if(!legal[ls[k]]) x = rs[k]; 
//		if(!legal[rs[k]]) x = ls[k]; 
//		if(x) {
//			ans[k] = ans[x]; 
//			depmx[k] = depmx[x]; depmn[k] = depmn[x]; 
//			ld[k] = ld[x]; rd[k] = rd[x]; 
//			
//		}
		ans[k] = max(ans[ls[k]], ans[rs[k]]); 
		depmx[k] = max(depmx[ls[k]], depmx[rs[k]]); 
		depmn[k] = min(depmn[ls[k]], depmn[rs[k]]); 
		ans[k] = max(ans[k], rd[ls[k]] + depmx[rs[k]]); 
		ans[k] = max(ans[k], depmx[ls[k]] + ld[rs[k]]); 
		ld[k] = max(max(ld[ls[k]], ld[rs[k]]), depmx[rs[k]] - 2 * depmn[ls[k]]); 
		rd[k] = max(max(rd[ls[k]], rd[rs[k]]), depmx[ls[k]] - 2 * depmn[rs[k]]); 
	}
	void build(int &k, int l, int r) {
		if(!k) k = ++tot; 
		if(l == r) {
			ans[k] =  0; legal[k] = 1; 
			depmn[k] = dep[dfn[l]]; 
			if(cale[l]) depmx[k] = dep[dfn[l]], ld[k] = rd[k] = -dep[dfn[l]]; 
//			debug(">> [%d] %d %d\n", l, depmx[k], depmn[k]); 
//			if(cale[l]) debug("=== %d\n", l); 
			else depmx[k] = ld[k] = rd[k] = - 5 * n; 
			return ; 
		}
		int mid = (l + r) >> 1; 
		build(ls[k], l, mid); 
		build(rs[k], mid + 1, r); 
		push_up(k); 
//		debug("[%d %d] mx %d mn %d ans : %d\n", l, r, depmx[k], depmn[k], ans[k]); 
//		debug("[%d %d][%d %d]\n", depmx[ls[k]], depmx[rs[k]], depmn[ls[k]], depmn[rs[k]]); 
	}
	void modify(int k, int l, int r, int x) {
		if(l == r) {
			if(legal[k]) {
				depmx[k] = ld[k] = rd[k] = - 5 * n; 
			}
			else {
				depmx[k] = dep[dfn[l]]; 
				ld[k] = rd[k] = -dep[dfn[l]]; 
			}
			legal[k] = 1 - legal[k]; 
			return ; 
		}
		int mid = (l + r) >> 1; 
		if(x <= mid) modify(ls[k], l, mid, x); 
		else modify(rs[k], mid + 1, r, x); 
		push_up(k); 
		debug("[%d %d] mx %d mn %d ans : %d || %d %d\n", l, r, depmx[k], depmn[k], ans[k], ld[k], rd[k]); 
//		debug("[%d %d][%d %d]\n", depmx[ls[k]], depmx[rs[k]], depmn[ls[k]], depmn[rs[k]]); 
	}
}Seg; 

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T = read();
//	while(T--) {
//
//	}
	n = read(); 
	for(i = 1; i < n; ++i) {
		x = read(); y = read(); 
		v[x].pb(y); v[y].pb(x); 
	}
	dfs(1, 0); 
	for(i = 1; i <= cnt; ++i) debug("%2d ", i); debug("\n"); 
	for(i = 1; i <= cnt; ++i) debug("%2d ", dfn[i]); debug("\n"); 
	for(i = 1; i <= cnt; ++i) debug("%2d ", dep[dfn[i]]); debug("\n"); 
	for(i = 1; i <= n; ++i) debug("%d ", dep[i]); debug("\n"); 
	Seg.build(rt, 1, cnt); 
	q = read(); 
	while(q--) {
		x = read(); 
		Seg.modify(rt, 1, cnt, c[x]); 
		printf("%d\n", Seg.ans[rt]); 
	} 
	return 0;
}



ABC 459 F（贪心、单调队列）

先减各自序号，把题目转化为单调不下降

我们可以直接贪心，用单调队列维护连续段。

每次取出末尾一段，然后和当前拼接成一段或两段

可以发现，只有如下三种情况：

在这里插入图片描述

在这里插入图片描述

各自处理即可

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
93
94
95
96
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo 
//#define N
#define E9 1000000000
int n, m, i, j, k, T; 
int ans, x, l1, l2, lx, h1, h2, hx, nh1, nh2, nl1, nl2; 
int S, L; 
stack<pair<int, int> >z; 

int count(int a, int b, int c) {
	debug("count[%lld %lld] * %lld\n", a, b, c); 
	if(a < 0 || b < 0 || c < 0) return 0; 
	return (a * (a - 1) / 2 + a * c) * b;  
}

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
	T = read();
	while(T--) {
		n = read(); ans = 0; 
		while(!z.empty()) z.pop(); 
		for(i = 1; i <= n; ++i) {
			x = read() - i + E9; 
//			printf("%d ", x - E9); 
			if(z.empty() || x > z.top().fi) z.push({x, 1}); 
			else if(x == z.top().fi) {
				auto t = z.top(); z.pop(); 
				z.push({t.fi, t.se + 1}); 
			}
			else {
				debug("For i = %lld : \n", i); 
				h1 = x; l1 = 1; h2 = E9; l2 = 0; 
				while(!z.empty() && h1 <= z.top().fi) {
					auto t = z.top(); z.pop(); 
					hx = t.fi; lx = t.se; 
					debug("[%lld %lld] [%lld %lld][%lld %lld] ==> ", hx - E9, lx, h1 - E9, l1, h2 - E9, l2); 
					S = hx * lx + h1 * l1 + h2 * l2; 
					L = lx + l1 + l2; 
					nh1 = S / L; nh2 = nh1 + 1; 
					nl2 = S % L; nl1 = L - nl2; 
					debug("[%lld %lld][%lld %lld]\n", nh1 - E9, nl1, nh2 - E9, nl2); 
					if(nl1 <= lx) {
						ans += count(nl1, hx - nh1, lx - nl1 + 1); 
						ans += count(lx - nl1, hx - nh2, 1); 
						ans += count(l1, nh2 - h1, 0); 
						if(l2) ans += count(l2, nh2 - h2, l1); 
					} 
					else if(nl1 <= lx + l1) {
						ans += count(lx, hx - nh1, 1); 
						ans += count(nl1 - lx, nh1 - h1, 0); 
						ans += count(lx + l1 - nl1, nh2 - h1, nl1 - lx); 
						if(l2) ans += count(l2, nh2 - h2, l1); 
					}
					else {
						ans += count(lx, hx - nh1, 1); 
						ans += count(l1, nh1 - h1, 0); 
						ans += count(nl1 - l1 - lx, nh1 - h2, l1); 
						if(l2) ans += count(nl2, nh2 - h2, nl1 - lx); 
					}
					debug("		now ans is %lld\n", ans); 
					l1 = nl1; h1 = nh1; l2 = nl2; h2 = nh2; 
				}
				z.push({h1, l1}); if(l2) z.push({h2, l2}); 
			}
			debug("now ans is %lld\n", ans); 
		}	
//		debug("\n"); 
		printf("%lld\n", ans); 
	}

	return 0;
}



ABC 458 F（AC自动机、矩阵快速幂）

nn 极大，显然要矩阵快速幂

矩阵的构建过程拿AC自动机即可

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
#define mo 998244353
#define N 110
int n, m, i, j, k, T, rt;
char str[N]; 

void Add(int &a, int b) {
	b %= mo; 
	a = ((a + b) % mo + mo) % mo; 
}

struct Matrix {
	int i, j, k; 
	int a[N][N]; 
	void clear() {
		memset(a, 0, sizeof(a)); 
	}
	void add(int x, int y, int z) {
		a[x][y] = z; 
	}
	void print() {
		#ifdef LOCAL
		 	for(i = 1; i <= n; ++i, debug("\n"))
		 		for(j = 1; j <= n; ++j)
		 			debug("%lld ", a[i][j]); 
		 	debug("----------\n"); 
		#endif
	}
//	Matrix operator * (const Matrix &B) {
//		Martix C; C.clear(); 
//		for(i = 1; i <= n; ++i) 
//			for(j = 1; j <= n; ++j) 
//				for(k = 1; k <= n; ++k) 
//					Add(C.a[i][k], a[i][j] * B.a[j][k]); 
//		return C;  
//	}
}ans, A; 

void MUL(Matrix &A, Matrix B, int nx) {
	int i, j, k; Matrix C; C.clear();  
	for(i = 1; i <= nx; ++i)
		for(j = 1; j <= n; ++j) 
			for(k = 1; k <= n; ++k) 
				Add(C.a[i][k], A.a[i][j] * B.a[j][k]); 
	A = C; 
}

void Run(int b) {
	ans.a[1][1] = 1; 
	while(b) {
		if(b & 1) MUL(ans, A, 1); 
		MUL(A, A, n); b >>= 1;  
		A.print(); 
	}
	int sum = 0; 
//	ans.print(); 
	for(i = 1; i <= n; ++i) Add(sum, ans.a[1][i]); 
	printf("%lld", sum); 
}

struct Trie {
	int ch[N][27], fail[N], End[N], vis[N]; 
	queue<int>q; 
	void add(int &x, int i) {
		if(!x) x = ++n; 
		if(!str[i + 1]) End[x] = 1;  
		if(str[i + 1]) add(ch[x][str[i + 1] - 'a'], i + 1); 
//		debug("%lld -> %lld[%c] | %lld\n", x, ch[x][str[i] - 'a'], str[i], i); 
//		if(str[i + 2]) A.add(x, son[x][str[i + 1] - 'a'], 1); 	
	}
	void bfs() {
		q.push(1); fail[1] = 0; fail[0] = 1; 
		while(!q.empty()) {
			int u = q.front(), v; q.pop(); 
			for(i = 0; i < 26; ++i) {
				if(!(v = ch[u][i]) || fail[v]) continue; 
				k = fail[u]; 
				fail[v] = (ch[k][i] ? ch[k][i] : 1); 
				End[v] |= End[fail[v]]; 
				for(j = 0; j < 26; ++j) 
					if(!ch[v][j]) ch[v][j] = ch[fail[v]][j]; 
				q.push(v); 
			}
		}
	}
	void run(int x) {
		int k = 26; vis[x] = 1; 
		for(int i = 0; i < 26; ++i) {
//			if(ch[x][i]) debug("%lld --> %lld\n", x, ch[x][i]); 
			if(ch[x][i] > 1) {
				--k; 
				if(!End[ch[x][i]]) A.add(x, ch[x][i], 1); 
				if(!vis[ch[x][i]]) run(ch[x][i]); 
			}
		}
		A.add(x, rt, k); 
	}
}Tr;

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T = read();
//	while(T--) {
//
//	}
	int Times; 
	Times = read(); m = read(); 
	rt = n = 1; 
	for(i = 1; i <= m; ++i) {
		scanf("%s", str + 1); 
		Tr.add(Tr.ch[rt][str[1] - 'a'], 1); 
//		A.add(rt, Tr.ch[rt][str[1] - 'a'], 1); 
	}
	Tr.bfs(); 
	Tr.run(rt); 
//	A.print(); 
	Run(Times); 
	return 0;
}