社区讨论

可以加强的数据

mmyxRUC
P10488[BAPC 2006 资格赛] Booksort参与者 1已保存回复 1

讨论操作

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

当前回复
1 条
当前快照
1 份
快照标识符
@mhjkghsv
此快照首次捕获于
2025/11/04 04:02
4 个月前
此快照最后确认于
2025/11/04 04:02
4 个月前
查看原帖

探讨一下超时问题（注意并不是题解，因为在acwing不是满分，有一个测试点超时）

本人用的双向广度搜索，在洛谷AC，但是在acwing会超时（可能是acwing把他归在了IDA*，需要启发函数），希望大家讨论一下如何优化BFS，过不了的数据在下面大家可以自测。下面是我的双向广度搜索函数

CPP

int bfs(string start) {
	string end;
	for (int i = 0; i < start.length(); i++) {
		end.push_back('a' + i);
	}

	queue<node>Q1, Q2;
	unordered_map<string, int>mp1, mp2;

	Q1.push({ 0,start });
	Q2.push({ 0,end });
	mp1[start] = 0, mp2[end] = 0;
	if (start == end) {
		return 0;
	}
	while (!Q1.empty()) {
		auto k = Q1.front();
		Q1.pop();

		if (k.v > 1)continue;

		int len = 1;
		while (len < k.str.length()) {

			for (int i = 0; i + len - 1 < k.str.length(); i++) {
				string A, B;
				for (int j = 0; j < k.str.length(); j++) {
					if (j >= i && j <= i + len - 1) {
						A.push_back(k.str[j]);
					}
					else {
						B.push_back(k.str[j]);
					}
				}

				for (int j = 0; j < B.length(); j++) {
					string C;
					for (int r = 0; r < B.length(); r++) {
						C += B[r];
						if (r == j) {
							C += A;
						}
					}
					if (C == end) {
						return k.v + 1;
					}
					if (!mp1.count(C)) {
						mp1[C] = k.v + 1;
						Q1.push({ k.v + 1,C });
					}
				}
				string C = A + B;
				if (C == end) {
					return k.v + 1;
				}
				if (!mp1.count(C)) {
					mp1[C] = k.v + 1;
					Q1.push({ k.v + 1,C });
				}
			}
			len++;
		}
	}
	while (!Q2.empty()) {
		auto k = Q2.front();
		Q2.pop();
		if (k.v > 1) {
			continue;
		}
		int len = 1;
		while (len < k.str.length()) {
			for (int i = 0; i + len - 1 < k.str.length(); i++) {
				string A, B;
				for (int j = 0; j < k.str.length(); j++) {
					if (j >= i && j <= i + len - 1) {
						A.push_back(k.str[j]);
					}
					else {
						B.push_back(k.str[j]);
					}
				}

				for (int j = 0; j < B.length(); j++) {
					string C;
					for (int r = 0; r < B.length(); r++) {
						C += B[r];
						if (r == j) {
							C += A;
						}
					}
					if (mp1.count(C)) {
						return mp1[C] + k.v + 1;
					}
					if (!mp2.count(C)) {
						mp2[C] = k.v + 1;
						Q2.push({ k.v + 1,C });
					}
				}
				string C = A + B;
				if (mp1.count(C)) {
					return mp1[C] + k.v + 1;
				}
				if (!mp2.count(C)) {
					mp2[C] = k.v + 1;
					Q2.push({ k.v + 1,C });
				}

			}
			len++;
		}
	}
	return -1;
}

数据

PYTHON
3
15
1 2 4 5 7 8 9 10 12 13 14 15 11 6 3
15
15 10 1 12 2 11 13 3 4 7 6 5 14 9 8
15
15 7 9 13 8 10 12 1 4 11 5 6 14 2 3

回复

共 1 条回复，欢迎继续交流。

正在加载回复...