题解：P6994 [NEERC2014] Joke with permutation

· · 题解

测试点下载：测试点.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)~~**