18年CUG校赛--恶魔的序列
问题描述
小龙同学最近为了完成毕业设计头痛不已。巨大的精神压力导致他经常做 噩梦。这天他又做了一个史诗般的噩梦。他梦见自己被困在一个密室中，密室 的门上有一个谜题，只有解开谜题才能打开此门，逃出这个密室，否则就会永 远地被困在密室中，更可怕的是他还会永远的困在梦境中，无法完成毕设，从 而面临毕业危机。 谜题是这样的，给定一个连续的正整数序列 n, n+1, n+2, ..., m，要求通过 调整序列中数字的顺序，将其变成一个“k 度芝麻开门序列”。 一个简单的“2 度芝麻开门序列”可以理解为重新调整一个连续整数序列 的顺序，使得每对相邻两个数之和是一个合数（非质数）。同样的，一个“k 度 芝麻开门序列”就是指调整后序列中所有长度为 2,3, …, k 的连续子序列数字之 和都是合数。例如对于 n=1，m=10 的序列，排列 1,3,5,4,2,6,9,7,8,10 是一个 2 度芝麻开门序列，但是却不是 3 度芝麻开门序列，因为 5+4+2 之和为 11 是质 数。 小龙同学由于被毕业设计榨干了头脑，已经无法再进行思考，所以请你帮 帮他解开谜题，拯救他的毕业设计。
输入 多组输入。每组输入占一行，包括三个正整数 n，m，k， （1<=n<=m<=1000，2<=k<=10）表示序列左右边界和度数，输入由三个整数 0，0，0 结束。 输出 对于每一组输入，输出一个序列，即从 n 到 m 的 k 度芝麻开门序列，以',' 分隔。如果有多组解，则按照字典序输出第一组（就是说，输出第一个元素最 小的一组，如果第一个元素相同，则输出第二个元素最小的一组，依次类推）。 如果没有解，则输出一行提示：“Your nightmare never ends.”
样例输入
1 10 2
1 10 3
1 10 5
40 60 7
0 0 0
样例输出
1,3,5,4,2,6,9,7,8,10
1,3,5,4,6,2,10,8,7,9
Your nightmare never ends.
40,41,43,42,44,46,45,47,48,50,55,53,52,60,56,49,51,59,58,57,54
解法
有点类似全排列递归的写法，加上一个序列条件的判断。
代码
#include<iostream>
using namespace std;
const int N = 10000;
int vis[N];
int v[1005];
int path[1005];
int n, m, k;
void init() {
int m = sqrt(N + 0.5);
memset(vis, 0, sizeof(vis));
for (int i = 2; i <= m; i++) {
if (!vis[i])
for (int j = i * i; j <= N; j += i)
vis[j] = 1;
}
}
bool flag = 0;
bool dfs(int pos,int x) {
path[pos] = x;
if (pos >= 2) {
int sum = path[pos], d = pos >k?k:pos;
for (int i = pos - 1; i > pos - k; i--) {
sum += path[i];
if (!vis[sum])return false;
}
if (pos == m - n + 1)
{
flag = true;
for (int i = 1; i <= m - n + 1; ++i) {
printf(i == 1 ? "%d" : ",%d", path[i]);
}
cout << endl;
return true;
}
}
for (int i = n; i <= m; i++) {
if (!v[i]) {
v[i] = 1;
if (dfs( pos + 1,i))return true;
v[i] = 0;
}
}
return false;
}
int main() {
init();
while (cin>>n>>m>>k&&n!=0)
{
flag = false;
memset(v, 0, sizeof(v));
for (int i = n; i <= m; ++i) {
v[i] = 1;
if (dfs(1,i)) {
flag = 1;
break;
}
v[i] = 0;
}
if(!flag)
cout << "Your nightmare never ends." << endl;
}
return 0;
}
失业啃老第二年，熬夜玩手机中。。
