专栏文章

题解：CF1455F String and Operations

xxz001
CF1455F题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minapi9r
此快照首次捕获于
2025/12/01 23:20
3 个月前
此快照最后确认于
2025/12/01 23:20
3 个月前
查看原文
首先我们发现一个点最多被交换两次，所以首先我们可以记忆化搜索，设 fi,q1,q2,q3,atf_{i,q_1,q_2,q_3,at} 表示到达第 ii 个位置，以 q3q_3 作为第 ii 个字符，q1,q2q_1,q_2 在其前面，atat 表示初始第 ii 个现在在哪里（q2q_2 还是 q3q_3）。然后可以直接转移，用 map 记忆化，加上很多剪枝后可以发现只有 80008000 多个状态，复杂度 8000×5008000\times 500，但因为 10001000 组测试数据，不可行。
发现复杂度瓶颈在于字符串的存储和比较，所以我们不存字符串了，我们存转移点，并用倍增维护哈希值，从而实现单次 log⁡n\log n 的字符串大小比较。
这样大约跑 8000×1000×10=8×1078000 \times 1000\times 10=8\times 10^7 次左右，但我们一开始使用的 map 记忆化，所以不容易过去。
注意到每一种状态都可以变进制哈希成一个小于 4×1074\times 10^7 的数字，因此我们可以先搜出所有状态，给它们编号，然后再写一个搜索将这些编号清空，这样就可以优化掉 map 这个 log⁡\log，即可卡过。
代码：
CPP
#include <bits/stdc++.h>

#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)

using namespace std;

const int N = 1e6 + 5;

int t, idx;

int n, k;

char s[N];

unsigned long long c[N];

bool f[N];

struct node {
	int i, q1, q2, q3, at;
};

node d[N];

int id[40 * N]; 

int st[12][20005];

unsigned long long h[12][20005];

inline unsigned long long hs (const int i, const int q1, const int q2, const int q3, const int at) {
	unsigned long long h = i;
	h = h * 26 + q1;
	h = h * 26 + q2;
	h = h * 26 + q3;
	h = h * 4 + at;
	return h;
} 

inline unsigned long long hs (const node &a) {
	unsigned long long h = a.i;
	h = h * 26 + a.q1;
	h = h * 26 + a.q2;
	h = h * 26 + a.q3;
	h = h * 4 + a.at;
	return h;
}

int cnt;

inline void Dfs (const int i, const int q1, const int q2, const int q3, const int at) {
    unsigned long long now = hs(i, q1, q2, q3, at);
	if (i > n) {
		if (id[now]) return;
		d[ ++ idx] = {i, q1, q2, q3, at};
		id[now] = idx;
		d[ ++ idx] = {i + 1, q2, q3, 0, at};
		id[hs({i + 1, q2, q3, 0, at})] = idx;
		return;
	}
	if (id[now]) return;
	d[ ++ idx] = {i, q1, q2, q3, at};
	id[now] = idx;
	if (at == 2) {
		if (q1 != q2) {
			if (q1 < q2) {
				if (q3 < min((q2 + 1) % k, (q2 - 1 + k) % k)) {
					Dfs (i + 1, q3, q2, s[i + 1] - 'a', 3);
				} else if (q3 > min((q2 + 1) % k, (q2 - 1 + k) % k)) {
					Dfs (i + 1, min((q2 + 1) % k, (q2 - 1 + k) % k), q3, s[i + 1] - 'a', 3);
				} else {
					Dfs (i + 1, q3, q2, s[i + 1] - 'a', 3);
					Dfs (i + 1, min((q2 + 1) % k, (q2 - 1 + k) % k), q3, s[i + 1] - 'a', 3);
				}
			} else {
				Dfs (i + 1, q1, q3, s[i + 1] - 'a', 3);
			}
		} else {
			Dfs (i + 1, q1, q3, s[i + 1] - 'a', 3);
			Dfs (i + 1, q3, q2, s[i + 1] - 'a', 3);
			Dfs (i + 1, min((q2 + 1) % k, (q2 - 1 + k) % k), q3, s[i + 1] - 'a', 3);
		}
	} else {
		if (q3 < q2) {
			Dfs (i + 1, q3, q2, s[i + 1] - 'a', 3);
		} else if (q3 > q2) {
			Dfs (i + 1, q2, min((q3 + 1) % k, (q3 - 1 + k) % k), s[i + 1] - 'a', 3);
		} else {
			Dfs (i + 1, q3, q2, s[i + 1] - 'a', 3);
			Dfs (i + 1, q2, min((q3 + 1) % k, (q3 - 1 + k) % k), s[i + 1] - 'a', 3);
		}
		if (i != n) {
			Dfs (i + 1, q2, s[i + 1] - 'a', q3, 2);
	    }
	}
	return;
}

inline void DFS (const int i, const int q1, const int q2, const int q3, const int at) {
    unsigned long long now = hs(i, q1, q2, q3, at);
	if (i > n) {
		if (!id[now]) return;
		f[id[now]] = false;
		id[now] = 0;
		f[id[hs({i + 1, q2, q3, 0, at})]] = false;
		id[hs({i + 1, q2, q3, 0, at})] = 0;
		return;
	}
	if (!id[now]) return;
	f[id[now]] = false;
	id[now] = 0;
	if (at == 2) {
		if (q1 != q2) {
			if (q1 < q2) {
				if (q3 < min((q2 + 1) % k, (q2 - 1 + k) % k)) {
					DFS (i + 1, q3, q2, s[i + 1] - 'a', 3);
				} else if (q3 > min((q2 + 1) % k, (q2 - 1 + k) % k)) {
					DFS (i + 1, min((q2 + 1) % k, (q2 - 1 + k) % k), q3, s[i + 1] - 'a', 3);
				} else {
					DFS (i + 1, q3, q2, s[i + 1] - 'a', 3);
					DFS (i + 1, min((q2 + 1) % k, (q2 - 1 + k) % k), q3, s[i + 1] - 'a', 3);
				}
			} else {
				DFS (i + 1, q1, q3, s[i + 1] - 'a', 3);
			}
		} else {
			DFS (i + 1, q1, q3, s[i + 1] - 'a', 3);
			DFS (i + 1, q3, q2, s[i + 1] - 'a', 3);
			DFS (i + 1, min((q2 + 1) % k, (q2 - 1 + k) % k), q3, s[i + 1] - 'a', 3);
		}
	} else {
		if (q3 < q2) {
			DFS (i + 1, q3, q2, s[i + 1] - 'a', 3);
		} else if (q3 > q2) {
			DFS (i + 1, q2, min((q3 + 1) % k, (q3 - 1 + k) % k), s[i + 1] - 'a', 3);
		} else {
			DFS (i + 1, q3, q2, s[i + 1] - 'a', 3);
			DFS (i + 1, q2, min((q3 + 1) % k, (q3 - 1 + k) % k), s[i + 1] - 'a', 3);
		}
		if (i != n) {
			DFS (i + 1, q2, s[i + 1] - 'a', q3, 2);
	    }
	}
	return;
}

inline void dfs (const int i, const int q1, const int q2, const int q3, const int at) {
    int now = id[hs(i, q1, q2, q3, at)];
	if (i > n) {
		h[0][now] = q1 + 'a';
		int t = id[hs({i + 1, q2, q3, 0, at})];
		st[0][now] = t;
		h[0][t] = q2 + 'a';
		for (int j = 1; j <= 10; ++ j ) {
			st[j][now] = t;
			h[j][now] = h[j - 1][now] * c[1 << (j - 1)] + h[j - 1][st[j - 1][now]];
		}
		return;
	}
	if (f[now]) return;
	f[now] = true;
	if (at == 2) {
		if (q1 != q2) {
			if (q1 < q2) {
				if (q3 < min((q2 + 1) % k, (q2 - 1 + k) % k)) {
					st[0][now] = id[hs({i + 1, q3, q2, s[i + 1] - 'a', 3})];
					h[0][now] = q1 + 'a'; 
					dfs (i + 1, q3, q2, s[i + 1] - 'a', 3);
				} else if (q3 > min((q2 + 1) % k, (q2 - 1 + k) % k)) {
					st[0][now] = id[hs({i + 1, min((q2 + 1) % k, (q2 - 1 + k) % k), q3, s[i + 1] - 'a', 3})];
					h[0][now] = q1 + 'a';
					dfs (i + 1, min((q2 + 1) % k, (q2 - 1 + k) % k), q3, s[i + 1] - 'a', 3);
				} else {
					const int U = id[hs({i + 1, q3, q2, s[i + 1] - 'a', 3})], V = id[hs({i + 1, min((q2 + 1) % k, (q2 - 1 + k) % k), q3, s[i + 1] - 'a', 3})];
					int u = U, v = V;
					dfs (i + 1, q3, q2, s[i + 1] - 'a', 3);
					dfs (i + 1, min((q2 + 1) % k, (q2 - 1 + k) % k), q3, s[i + 1] - 'a', 3);
					int cnt = 0;
					for (int i = 10; i >= 0; -- i ) {
						if (h[i][u] == h[i][v]) {
							u = st[i][u], v = st[i][v];
							cnt += 1 << i;
						}
					}
					if (cnt >= 1e3) {
						st[0][now] = U;
						h[0][now] = q1 + 'a';
					} else if (h[0][u] < h[0][v]) {
						st[0][now] = U;
						h[0][now] = q1 + 'a';
					} else {
						st[0][now] = V;
						h[0][now] = q1 + 'a';
					}
				}
			} else {
				st[0][now] = id[hs({i + 1, q1, q3, s[i + 1] - 'a', 3})];
				h[0][now] = q2 + 'a';
				dfs (i + 1, q1, q3, s[i + 1] - 'a', 3);
			}
		} else {
			h[0][now] = q2 + 'a';
			dfs (i + 1, q1, q3, s[i + 1] - 'a', 3);
			dfs (i + 1, q3, q2, s[i + 1] - 'a', 3);
			dfs (i + 1, min((q2 + 1) % k, (q2 - 1 + k) % k), q3, s[i + 1] - 'a', 3);
			const int U = id[hs({i + 1, q1, q3, s[i + 1] - 'a', 3})], V = id[hs({i + 1, q3, q2, s[i + 1] - 'a', 3})];
			int u = U, v = V;
			int cnt = 0;
			for (int i = 10; i >= 0; -- i ) {
				if (h[i][u] == h[i][v]) {
					u = st[i][u], v = st[i][v];
					cnt += 1 << i;
				}
			}
			if (cnt >= 1e3) u = U;
			else if (h[0][u] < h[0][v]) {
				u = V;
			} else {
				u = V;
			}
			int tmp = u;
			const int T = id[hs({i + 1, min((q2 + 1) % k, (q2 - 1 + k) % k), q3, s[i + 1] - 'a', 3})];
			v = T;
			cnt = 0;
			for (int i = 10; i >= 0; -- i ) {
				if (h[i][u] == h[i][v]) {
					u = st[i][u], v = st[i][v];
					cnt += 1 << i;
				}
			}
			if (cnt >= 1e3) u = tmp;
			else if (h[0][u] < h[0][v]) u = tmp;
			else u = T;
			st[0][now] = u;
		}
	} else {
	    h[0][now] = q1 + 'a';
	    int u, v;
		if (q3 < q2) {
			dfs (i + 1, q3, q2, s[i + 1] - 'a', 3);
			u = id[hs({i + 1, q3, q2, s[i + 1] - 'a', 3})];
		} else if (q3 > q2) {
			dfs (i + 1, q2, min((q3 + 1) % k, (q3 - 1 + k) % k), s[i + 1] - 'a', 3);
			u = id[hs({i + 1, q2, min((q3 + 1) % k, (q3 - 1 + k) % k), s[i + 1] - 'a', 3})];
		} else {
			dfs (i + 1, q3, q2, s[i + 1] - 'a', 3);
			dfs (i + 1, q2, min((q3 + 1) % k, (q3 - 1 + k) % k), s[i + 1] - 'a', 3);
			const int U = id[hs({i + 1, q3, q2, s[i + 1] - 'a', 3})], V = id[hs({i + 1, q2, min((q3 + 1) % k, (q3 - 1 + k) % k), s[i + 1] - 'a', 3})];
			u = U, v = V;
			int cnt = 0;
			for (int i = 10; i >= 0; -- i ) {
				if (h[i][u] == h[i][v]) {
					u = st[i][u], v = st[i][v];
					cnt += 1 << i;
				}
			}
			if (cnt >= 1e3) u = U;
			else if (h[0][u] < h[0][v]) u = U;
			else u = V;
		}
		if (i != n) {
			const int tmp = u;
			const int T = id[hs({i + 1, q2, s[i + 1] - 'a', q3, 2})];
			v = T;
			dfs (i + 1, q2, s[i + 1] - 'a', q3, 2);
			int cnt = 0;
			for (int i = 10; i >= 0; -- i ) {
				if (h[i][u] == h[i][v]) {
					u = st[i][u], v = st[i][v];
					cnt += 1 << i;
				}
			}
			if (cnt >= 1e3) u = tmp;
			else if (h[0][u] < h[0][v]) u = tmp;
			else u = T;
		}
		st[0][now] = u;
	}
	for (int j = 1; j <= 10; ++ j ) {
		st[j][now] = st[j - 1][st[j - 1][now]];
		h[j][now] = h[j - 1][now] * c[1 << (j - 1)] + h[j - 1][st[j - 1][now]];
	}
	return;
}

signed main() {
//	freopen("g.in","r",stdin);
//	freopen("g.out","w",stdout);
	c[0] = 1;
	for (int i = 1; i <= 1e6; ++ i ) c[i] = c[i - 1] * 33331;
	scanf("%d", &t);
	while (t -- ) {
		for (int i = 1; i <= idx; ++ i ) {
			for (int j = 0; j <= 10; ++ j ) {
				st[j][i] = h[j][i] = 0;
			}
		}
		idx = 0;
		scanf("%d%d%s", &n, &k, s + 1);
		s[n + 1] = 'z';
		Dfs (1, 0, 0, s[1] - 'a', 3);
		dfs (1, 0, 0, s[1] - 'a', 3);
		int u = id[hs({1, 0, 0, s[1] - 'a', 3})]; 
		for (int i = 1; i <= n + 2; ++ i ) {
			if (i > 2) printf("%c", (char)h[0][u]);
			u = st[0][u];
		}
		puts("");
		DFS (1, 0, 0, s[1] - 'a', 3);
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...