自动搬运

查看原文

来自洛谷，原作者为

	Xu_Jinyi_2011 十步AC一题，千里不留行

搬运于2025-08-24 22:25:44，当前版本为作者最后更新于2024-11-04 21:10:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

测试点下载：测试点.zip

算法选择：

首先我们可以知道，这道题中，数只有两种情况：

1. 大于零的一位数。
2. 小于 $n$ 的两位数。

而且这道题的数据范围很小，所以可以使用深度优先搜索的解法。

确定 $n$：

因为是一串连续的正整数构成的序列，所以：

1. 当原始字符串的长度小于十时，$n$ 的值为原始字符串的长度。
2. 当原始的字符串的长度大于等于十时，$n$ 的值为原始字符串的长度减九的差除以二加九（两位数的长度为二，一位数的长度为一）。

搜索推出条件：

当用于存储答案的栈里的数的数量等于 $n$ 时，从第一个元素开始输出到最后一个。然后使用一个很好用的函数——exit(0)退出递归。

关于重复问题：

使用一个桶记录是否已经用过当前数不就解决问题了吗？

一点小问题：

必须判断两位数是否小于 $n$。题目里有解释，就别问我为什么了，半个小时血与泪的教训。

喜闻乐见的 $AC$ 代码分享

#include <iostream>
#include <cstring>

using namespace std;

string s;
int a[60], b[60] = {1}, n;

void dfs(int it, int x) {
	if (x >= n ) {
	    for (int i = 0; i < n; i ++) {
	        cout << a[i] << ' ';
	    }
		exit(0);
	}
	if (it >= s.size()) return;
	if (!b[s[it] ^ 48]) {
		a[x] = s[it] ^ 48;
		b[s[it] ^ 48] = 1;
		dfs(it + 1, x + 1);
		b[s[it] ^ 48] = 0;
	}
	if (it < s.size() - 1 && !b[(s[it] ^ 48) * 10 + (s[it + 1] ^ 48)] && (s[it] ^ 48) * 10 + (s[it + 1] ^ 48) <= n) {
		int y = (s[it] ^ 48) * 10 + (s[it + 1] ^ 48);
		a[x] = y;
		b[y] = 1;
		dfs(it + 2, x + 1);
		b[y] = 0;
	}
}

int main() {
	cin >> s;
	n = s.size() <= 9 ? s.size(): 9 + (s.size() - 9)/2;
	dfs(0, 0);
	return 0; 
}

各位大佬考虑点个赞？(orz)