应该输出不可行的输了答案,检查了 check 也没问题,求教!悬 11 关!
查看原帖
应该输出不可行的输了答案,检查了 check 也没问题,求教!悬 11 关!
482998
jeffstart楼主2024/7/16 08:53

rt.

代码如下:

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
bool chosen[N];
bool is_print;
int n, m, d;
int a[N];

bool is_prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) {
			return false;
		}
	}
	return true;
}

bool check(int pos) {
	for (int len = 2; len <= d; len++) {
		int l = pos - len + 1, r = pos;
		if (l < 1) {
			continue;
		}
		int sum = 0;
		for (int k = l; k <= r; k++) {
			sum += a[k];
		}
		if (is_prime(sum)) {
			return false;
		}
	}
	return true;
}

void dfs(int pos) {
	if (!check(pos) || is_print) {
		return;
	}
	if (pos == m - n + 2) {
		for (int i = 1; i <= m - n + 1; i++) {
			cout << a[i] << " ";
		}
		cout << "\n";
		is_print = true;
		return;
	}
	for (int i = n; i <= m; i++) {
		if (!chosen[i - n]) {
			a[pos] = i;
			chosen[i - n] = true;
			dfs(pos + 1);
			chosen[i - n] = false;
		}
	}
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	while (cin >> n >> m >> d && n && m && d) {
		memset(chosen, false, sizeof(chosen));
		is_print = false;
		dfs(1);
		if (!is_print) {
			cout << "No anti-prime sequence exists.\n";
		}
	}   
	return 0;
}
2024/7/16 08:53
加载中...