题解：CF461E Appleman and a Game

补充了部分细节问题。

如果

s

确定，如何求出其最小操作数？

g_i

表示前缀

i

最少被分成多少段，

g_i

能从

g_j + 1

转移当且仅当

(j, i]

是

t

的子串。

注意到

g_{i} \ge g_{i - 1}

，因为任意

i

的方案都能砍掉

s_i

后变成

i - 1

的方案。

因此

i

的转移点为最小的

j

满足

(j, i]

是

t

的子串。

有如下贪心：对于每一段，能延伸就延伸（在

t

的 sam 上跑，有转移边就走，否则回到根）。

在段数相同的情况下要最小化总长度，这样才能在总长度确定时最大化段数。

设

f(k, i, j)

表示已经拼了

k

段，以字符

i

开头且不能再往后延伸一个字符

j

的最小总长度。

倍增优化：

f(2^k, i, j) \gets f(2^{k - 1}, i, x) + f(2^{k - 1}, x, j)

。

问题转化为求

f(1, i, j)

。

其代表的子串在将来一定是接一个

j

开头的段，并产生

2

的贡献。

把以

i

开头的字符串

s

分成三类：

是 $t$ 的子串且后面不能加 $j$ ，在后面接一个 $j$ 开头的段，恰好产生两个段。
是 $t$ 的子串且后面能加 $j$ ，不一定能产生两个段。
不是 $t$ 的子串，已经产生至少两个段了，哪怕新接的段不产生贡献，贡献仍然至少为二。

因此在相同长度下，一三比二更优。

固定长度为

k

，第二类有

x = O(n)

种，一三加起来有

4^{k - 1} - x

。

存在一三串当且仅当

4^{k - 1} - x > 0

，取

k = 11

足矣。

对所有后缀建出树高为

11

的字典树即可求出所有有用的

f(1, i, j)

（可能存在大于

11

，但是没用）。

统计答案：从高到低枚举

2^k

，

h_{i, j}

表示

i

开头，后面接不了

j

，在当前答案下的最小长度。

由于有“不能接”这一限制，贪心的让

h_{i, j} < n

，并在最后补一个

j

（体现在答案上就是加

1

）。

CPP

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr int N = 1e5 + 5;

int m, t[N * 15][4], idx;
char s[N];

ll n, f[61][4][4], h[4][4], g[4][4];

void dfs(int u, int v, int d, ll& x) {
	if(!u) return;
	if(!t[u][v]) {
		x = min(x, (ll)d);
		return;
	}
	for(int i = 0; i < 4; ++ i) {
		dfs(t[u][i], v, d + 1, x);
	}
}
main() {
	scanf("%lld%s", &n, s);
	m = strlen(s);
	for(int i = 0; i < m; ++ i) s[i] -= 'A';
	for(int i = 0; i < m; ++ i) {
		for(int j = i, p = 0; j < m; ++ j) {
			if(j - i >= 11) break;
			if(!t[p][s[j]]) t[p][s[j]] = ++ idx;
			p = t[p][s[j]];
		}
	}
	memset(f, 0x3f, sizeof f);
	for(int i = 0; i < 4; ++ i) {
		for(int j = 0; j < 4; ++ j) {
			dfs(t[0][i], j, 1, f[0][i][j]);
		}
	}
	for(int k = 1; k <= 60; ++ k) {
		for(int i = 0; i < 4; ++ i) {
			for(int j = 0; j < 4; ++ j) {
				for(int x = 0; x < 4; ++ x) {
					f[k][i][j] = min(f[k][i][j], f[k - 1][i][x] + f[k - 1][x][j]);
				}
			}
		}
	}
	ll ans = 0;
	for(int k = 60; k >= 0; -- k) {
		ll mi = 1e18;
		for(int i = 0; i < 4; ++ i) {
			for(int j = 0; j < 4; ++ j) {
				h[i][j] = 1e18;
				for(int x = 0; x < 4; ++ x) {
					h[i][j] = min(h[i][j], g[i][x] + f[k][x][j]);
				}
				mi = min(mi, h[i][j]);
			}
		}
		if(mi < n) {
			ans |= 1ll << k;
			swap(g, h);
		}
	}
	printf("%lld", ans + 1);
}

题解：CF461E Appleman and a Game

文章操作

相关推荐

评论

题解：CF461E Appleman and a Game