Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:半年前ac过这题,重做,居然被卡了2小时

Posted by YT1658501229 at 2017-08-19 08:06:26 on Problem 2034
In Reply To:半年前ac过这题,重做,居然被卡了2小时 Posted by:920394589 at 2017-08-17 17:56:21
> #include<stdio.h>
> #include<string.h>
> #include<iostream>
> using namespace std;
> 
> const int maxn = 1005;
> int n,m,d;
> bool success,vis[maxn],tb[maxn*10];
> int x[maxn];
> 
> void init(){
> 	success = 0;
> 	memset(vis,0,sizeof(vis));
> } 
> 
> void get_prime_table(){
> 	for (int i = 2; i < maxn*10; i++)
> 	for (int j = 2; i*j < maxn*10; j++)
> 		tb[i*j] = 1;
> }
> 
> void dfs(int t){
> 	if(t==m+1){
> 		success = 1;
> 		return;
> 	}
> 	for(int i=n;i<=m;++i){
> 		if(!vis[i]){
> 			if(t>n){
> 				int sum = i;
> 				int bit = t-1;
> 				while(bit>=n&&bit>t-d&&tb[sum+=x[bit]])--bit;
> 				if(bit!=n-1&&bit!=t-d)continue;
> 			}
> 			x[t] = i;
> 			vis[i] = 1;
> 			dfs(t+1);
> 			if(success)return;
> 			vis[i] = 0;
> 		}
> 	}
> }
> 
> int main(){
> 	memset(tb,0,sizeof(tb));
> 	get_prime_table();
> 	while(cin>>n>>m>>d&&(n||m||d)){
> 		init();
> 		dfs(n);
> 		if(success){
> 			for(int i=n;i<m;++i){
> //				printf("%d,",x[i]);
> 				cout<<x[i]<<',';
> 			}
> //			printf("%d\n",x[m]);
> 			cout<<x[m]<<endl;
> 		}else{
> 			printf("No anti-prime sequence exists.\n");
> 		}
> 	}
> 	return 0;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator