摘要：
能够ac的处理方式是打表。代码：1#include23structdataxy{4intx;//普通愤怒5inty;//特别愤怒6}a[1000005];78intmain(){9inti,j,k=0;10//普通愤怒最早从125开始，特别愤怒最早从521开始11//打表，将125到1000000中的数据全部测试一遍，本次打表还有点动态规划的意味，因为12//计算0~x只需要测试x本身就好了，如果x本身是包含1/2/5的那就a[x]=a[x-1]+1,否则就是a[x]=a[x-1]13//对于数512是同理14for{15intc[3]={0};16if17c[2]=1;18if19c[1]=1;20if21c[0]=1;22ifa[i].x=a[i-1].x+1;23elsea[i].x=a[i-1].x;2425ifa[i].y=a[i-1].y+1;26elsea[i].y=a[i-1].y;27}2829while(scanf("%d%d",&i,&j)!=EOF){30k++;31printf;32}33return0;34}ViewCode看完这个题，让我想起了另一个能够打表处理的问题：找素数。比如找出1~n之间的素数。
这道题一开始本着很朴素的想法就是先输入两头的数据，然后对每组的数据范围下测试中间的数据即可，但是是超时的。原因也很明显，比如计算1~1000的数据之后，假如下一组数据是1~1001，本来只需要多测试下1001是否符合再加上前面的结果（1~1000）即可，而这种做法需要重复计算。
能够ac的处理方式是打表。就是分别计算1~n (n的范围是1~1000005) 中符合题设要求的数有多少，然后记录在data[n]中。在具体操作时，每步只增加1，然后增加的这个数字是否符合，然后将结果和前一位的结果相加即可。
代码：
1 #include<stdio.h> 2 3 structdataxy{ 4 int x;//普通愤怒 5 int y;//特别愤怒 6 }a[1000005]; 7 8 intmain(){ 9 int i,j,k=0; 10 //普通愤怒最早从125开始，特别愤怒最早从521开始 11 //打表，将125到1000000中的数据全部测试一遍，本次打表还有点动态规划的意味，因为 12 //计算0~x只需要测试x本身就好了，如果x本身是包含1/2/5的那就 a[x] = a[x-1] +1 ,否则就是a[x]=a[x-1] 13 //对于数512是同理 14 for(i=125; i<1000001; i++){ 15 int c[3]={0}; 16 if(i%10==5||i%100/10==5||i%1000/100==5||i%10000/1000==5||i%100000/10000==5||i%1000000/100000==5) 17 c[2]=1; 18 if(i%10==2||i%100/10==2||i%1000/100==2||i%10000/1000==2||i%100000/10000==2||i%1000000/100000==2) 19 c[1]=1; 20 if(i%10==1||i%100/10==1||i%1000/100==1||i%10000/1000==1||i%100000/10000==1||i%1000000/100000==1) 21 c[0]=1; 22 if(c[0]&&c[1]&&c[2]) a[i].x=a[i-1].x+1; 23 else a[i].x=a[i-1].x; 24 25 if(i%1000==521||i%10000/10==521||i%100000/100==521||i%1000000/1000==521) a[i].y=a[i-1].y+1; 26 else a[i].y=a[i-1].y; 27 } 28 29 while(scanf("%d %d",&i,&j)!=EOF){ 30 k++; 31 printf("Case %d:%d %d ",k,a[j].x-a[i-1].x,a[j].y-a[i-1].y); 32 } 33 return 0; 34 }
看完这个题，让我想起了另一个能够打表处理的问题：找素数。 比如找出1~n(n的范围是1~1000005)之间的素数。题目和上面类似，也是圈定1~n之间的数符合某种规则，然后可能的提问方式是“输出某个区间内符合条件的值”，“在某个区间内符合条件的值有多少个”......处理的方式的第一步都是找到这些数。而打表的方法让OJ多个测试案例无需重复计算，而利用 [1,n-1]来计算[1,n]中符合的数的方法（在找素数中就是利用之前找到的素数来筛掉后面的合数），也减少了计算量。
这里贴一个找输出1~n之间素数的筛法的代码：
1 #include <iostream> 2 #include <cstring> 3 using namespacestd; 4 5 //筛法求素数 6 #define N 100000 7 intvalid[N],primers[N]; 8 int count=0; 9 10 void GenPrimer(int n){ //参数n代表找出n以内的所有素数 11 inti,j,k; 12 for(i=2;i<=n;i++){ //初始化，将valid[n]的值赋为1 13 valid[i]=true; 14 } 15 16 for(i=2;i*i<=n;i++){ //从2~sqrt(n) 进行筛选 17 if(valid[i]){ //从(valid[i] ) 素数i开始 18 for(j=i*i;j<=n;j+=i){ //从i^2开始，之前搜过的不再重复；将i*i、i*(i+1)、i*(i+2)、i*(i+3)...统统筛掉 19 valid[j]=false; 20 } 21 } 22 } 23 24 for(i=2;i<=n;i++){ 25 if(valid[i]){ 26 primers[count++]=i; 27 } 28 } 29 } 30 31 intmain(){ 32 memset(primers,-1,sizeof(primers));//初始化 33 GenPrimer(7000); //找出7000以内的所有素数。 34 35 for(int i=0;i<count;i++){ 36 cout<<primers[i]<<" "; 37 if((i+1)%10==0) cout<<endl; 38 } 39 }