8
26
2012
1

构造式枚举:Prime Palindromes

在解决PackingRectangles这个问题的时候我强调枚举时要“将粗暴进行到底”,但并不是说可以无限度“粗暴”,当粗暴会导致TLE时,适当地构造解空间往往能大大优化程序的执行时间。


The number 151 is a prime palindrome because it is both a prime number and a palindrome (it is the same number when read forward as backward). Write a program that finds all prime palindromes in the range of two supplied numbers a and b (5 <= a < b <= 100,000,000); both a and b are considered to be within the range .


区间上限是1亿,如果我们直接枚举所有数据并检验是否是回文和素数会超时,实际上我们可以先构造出所有的回文数再检测他们是否是素数,n以内的回文数是很稀疏的,构造回文时我们只需枚举各个数位就可以了,这可以用o(√n)时间完成,另外检测n是否是素数的时间是o(√n),所以我们得到了一个o(n)的方法。

进化:

通过PackingRectangles和此问题,我们涉及到了构造和枚举的问题,过度构造会增加编程的复杂度,过度枚举又会超时,这就需要贴切的时间分析来选择了。在可接受的时间之内尽量减少构造,保持K.I.S.S(keep it simple and stupid)原则是个很好的方法。

点击查看我的程序源码:

/*
ID: *******
LANG: C++
TASK: pprime
*/
#include<stdio.h>
#include<stdlib.h>

int a,b;
FILE *fin,*fout;

typedef struct{
	int digital[9];
}Num;

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

void createPalinAndTest(int n,int L,Num num){//构造长度L的回文数
	int i;
	if(L%2==0&&n>L/2 || L%2==1&&n>L/2+1){
		//利用前一半构造整个回文数并且检测是否是素数
		for(i=n;i<=L;i++)
			num.digital[i-1]=num.digital[1+L-i-1];
		int t=1,N=0;
		for(i=0;i<L;i++){
			N+=t*num.digital[i];
			t*=10;
		}
		if(N<=b&&N>=a&&isPrime(N)){
			fprintf(fout,"%d\n",N);
		}
		return;
	}
	for(i=0;i<=9;i++){
		if(n==1&&i==0)continue;//首位不得为0
		num.digital[n-1]=i;
		createPalinAndTest(n+1,L,num);
	}
	return;
}

int main(){
	fin=fopen("pprime.in","r");
	fout=fopen("pprime.out","w");
	fscanf(fin,"%d %d",&a,&b);
	int i;
	Num num;
	for(i=1;i<=8;i++)
		createPalinAndTest(1,i,num);
	return 0;
}

 

Category: USACO | Tags: usaco | Read Count: 702
instagram password h 说:
2019年10月01日 08:49

Printing notebook is very great idea. It will make notebook more beautiful and attractive. Today i found another idea to hack insta account and it is very safe.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com