?
大致题意：给出区间[n,m],对这个区间的数进行排列使得相邻的2个、3个......d个数之和都不是素数。输出字典序最小的。
思路：裸的dfs。TLE了无数次是因为素数打表的范围太小，最大应打到10000。
#include #include #include #include #include #include #include #include #include #include #include #define LL long long #define _LL __int64 #define eps 1e-8 #define PI acos(-1.0) using namespace std; const int maxn = 10010; bool prime[maxn]; int vis[1010],ans[1010]; int n,m,d; int ok; void init() { memset(prime,true,sizeof(prime)); prime[0] = prime[1] = false; for(int i = 2; i <= 10000; i++) { if(prime[i] == true) { for(int j = i*i; j <= 10000; j += i) prime[j] = false; } } } void dfs(int dep) { if(ok == 1) return; if(dep == m-n+2) { ok = 1; for(int i = 1; i < dep-1; i++) printf(%d,,ans[i]); printf(%d ,ans[dep-1]); return; } for(int i = n; i <= m; i++) { if(!vis[i]) { bool flag = 0; for(int k = 2; k <= d && dep-k>=0; k++) { int sum = 0; for(int j = dep-k+1; j <= dep-1; j++) sum += ans[j]; if(prime[sum + i] == true) flag = 1; } if(flag == 1) continue; ans[dep] = i; vis[i] = 1; dfs(dep+1); vis[i] = 0; } } } int main() { init(); while(~scanf(%d %d %d,&n,&m,&d)) { if(n == 0 && m == 0 && d == 0) break; memset(vis,0,sizeof(vis)); ok = 0; dfs(1); if(ok == 0) printf(No anti-prime sequence exists. ); } return 0; }