为什么会超时?
查看原帖
为什么会超时?
348511
原子げんし楼主2021/2/9 20:47

RT

//7.21
//rng_58 bless me

#include<bits/stdc++.h>
using namespace std;
//fast io:
inline int Read() {
	int s = 0,f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){
		if(ch == '-') {
			f = -1;
		}
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}
inline void Wte(int x) {
    if(x < 0) {
    	putchar('-');
		x = -x;
	}
    if(x > 9)  {
		Wte(x / 10);
	}
    putchar(x % 10 + '0');
}
inline void Write(int x) {
	putchar(',');
	Wte(x);
}
//define:
#define REP(i,n) for(int i = 0; i < n; i++)
//const:
const int MAXN = 1010;
//something:
int p[MAXN],ans[MAXN];
bool vis[MAXN];
int N,M,D;
int n;
bool ok = 0;
void dfs(int x) {
	if(ok) {
		return;
	}
	if(x > n) {
		ok = 1;
		return;
	}
	for(int i = N; i <= M;i++) {
		if(!vis[i]) {
			bool bad = 0;
			for(int j = 2;j <= min(D,x);j++) {
				if(!p[ans[x - 1] - ans[x - j] + i]) {
					bad = 1;
					break;
				}
			}
			if(bad) {
				continue;
			}
			ans[x] = ans[x - 1] + i;
			vis[i] = 1;
			dfs(x + 1);
			if(ok) {
				return;
			}
			vis[i] = 0;
		}
	}
}
void iint_prime() {
	for(int i = 2;i <= sqrt(1000);i++) {
		if(!p[i]) {
			for(int j = i * i;j <= 1000;j += i) {
				p[j] = 1;
			}
		}
	}
	p[1] = 1;
}
void iint() {
	ok = 0; memset(ans,0,sizeof ans); memset(vis,0,sizeof vis);
}
//run:
void solve() {
	iint();
	N = Read(); M = Read(); D = Read();
	n = M - N + 1;
	if(N == 0 && M == 0) {
		exit(0);
	}
	dfs(1);
	if(ok) {
		Wte(ans[1]);
		for(int i = 2;i <= n;i++) {
			Write(ans[i] - ans[i - 1]);
		}
		puts("");
	} else {
		puts("No anti-prime sequence exists.");
	}
}
//times:
void Times(int T) {
	while(1) {
		solve();
	}
}
//begin:
int main() {
	iint_prime();
	int T;
	T = 1;
	//T = read();
	Times(T);
	return 0;
}

2021/2/9 20:47
加载中...