這道題一開始本著很樸素的想法就是先輸入兩頭的數據，然后對每組的數據范圍下測試中間的數據即可，但是是超時的。原因也很明顯，比如計算1~1000的數據之后，假如下一組數據是1~1001，本來只需要多測試下1001是否符合再加上前面的結果（1~1000）即可，而這種做法需要重復計算。

? ? ? 能夠ac的處理方式是打表。就是分別計算1~n (n的范圍是1~1000005) 中符合題設要求的數有多少，然后記錄在data[n]中。在具體操作時，每步只增加1，然后增加的這個數字是否符合，然后將結果和前一位的結果相加即可。

? ? 代碼：

1 #include<stdio.h> 2 3 struct dataxy{ 4 int x;//普通憤怒 5 int y;//特別憤怒 6 }a[1000005]; 7 8 int main(){ 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\n",k,a[j].x-a[i-1].x,a[j].y-a[i-1].y); 32 } 33 return 0; 34 } View Code

?

?

　　看完這個題，讓我想起了另一個能夠打表處理的問題：找素數。 ?比如找出1~n(n的范圍是1~1000005)之間的素數。題目和上面類似，也是圈定1~n之間的數符合某種規則，然后可能的提問方式是“輸出某個區間內符合條件的值”，“在某個區間內符合條件的值有多少個”......處理的方式的第一步都是找到這些數。而打表的方法讓OJ多個測試案例無需重復計算，而利用 [1,n-1]來計算[1,n]中符合的數的方法（在找素數中就是利用之前找到的素數來篩掉后面的合數），也減少了計算量。 ??

? ? ?這里貼一個找輸出1~n之間素數的篩法的代碼：

1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 //篩法求素數 6 #define N 100000 7 int valid[N],primers[N]; 8 int count=0; 9 10 void GenPrimer(int n){ //參數n代表找出n以內的所有素數 11 int i,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 int main(){ 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 } View Code

?

轉載于:https://www.cnblogs.com/liugl7/p/6239949.html

總結

以上是生活随笔為你收集整理的NYOJ 975的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。