題目連接：hdu_5085_Counting problem

題意：給你一個計算公式，然后給你一個區間，問這個區間內滿足條件的數有多少個

題解：由于這個公式比較特殊，具有可加性，我們考慮講一個數分為兩個部分，這樣就可以用莫隊的思想均攤時間復雜度，將9位數分為一個4位和一個5位，這里我感覺sqr為10000 速度比較快。然后如果b小于sqr，那么直接暴力就行，如果b大于sqr,那么我們要把a和b都分為頭部和尾部（注意是閉區間，a需要減1），如果a小于sqr，那么他的頭部就為0，然后計算0-a的尾部，并將相應的值插入Hash表，然后計算以a頭部開頭滿足條件的數，記為reta，同理，計算0-b的尾部，記為retb，如果b尾小于a尾，就要先計算b再計算a，然后將0到sqr-1的數對應的值也全部插入Hash表，然后從a的頭到b的頭，尋找對應的值，這里要用一下容斥定理，retb-reta就是從[a,b]之間滿條件的數的個數.

1 #include<cstdio> 2 #define F(i,a,b) for(int i=a;i<=b;i++) 3 typedef long long LL; 4 5 const LL M=(1<<20)-1,N=1e5+7,sqr=1e4; 6 LL K,a,b,ahd,bhd,bt,at,reta,retb,T,S,dt[10][16]; 7 inline LL pow(LL x,LL k){ 8 LL an=1; 9 while(k){ 10 if(k&1)an*=x; 11 k>>=1,x*=x; 12 } 13 return an; 14 } 15 //------------Hash table------------------------ 16 struct E{LL key;LL cnt;E *nxt;}*g[M+1],pool[N],*cur=pool,*p;LL vis[M+1]; 17 void init_Hash(){T++,cur=pool;} 18 inline void ins(LL key){ 19 if(key>S)return; 20 LL u=key&M; 21 if(vis[u]<T)vis[u]=T,g[u]=NULL; 22 for(p=g[u];p;p=p->nxt)if(p->key==key){p->cnt++;return;} 23 p=cur++,p->key=key,p->cnt=1,p->nxt=g[u],g[u]=p; 24 } 25 26 inline LL ask(LL key){ 27 if(key<0)return 0; 28 LL u=key&M; 29 if(vis[u]<T)return 0; 30 for(p=g[u];p;p=p->nxt)if(p->key==key)return p->cnt; 31 return 0; 32 } 33 //---------------------------------------------- 34 inline LL cal(LL x){ 35 LL an=0; 36 while(x)an+=dt[x%10][K],x/=10; 37 return an; 38 } 39 void init(){F(i,0,9)F(j,1,15)dt[i][j]=pow(i,j);} 40 int main(){ 41 init(); 42 while(~scanf("%lld%lld%lld%lld",&a,&b,&K,&S)){ 43 init_Hash(); 44 ahd=(a-1)/sqr,bhd=b/sqr,at=(a-1)%sqr,bt=b%sqr; 45 if(at<bt){ 46 F(i,0,at)ins(cal(i)); 47 reta=ask(S-cal(ahd)); 48 F(i,at+1,bt)ins(cal(i)); 49 retb=ask(S-cal(bhd)); 50 F(i,bt+1,sqr-1)ins(cal(i)); 51 }else{ 52 F(i,0,bt)ins(cal(i)); 53 retb=ask(S-cal(bhd)); 54 F(i,bt+1,at)ins(cal(i)); 55 reta=ask(S-cal(ahd)); 56 F(i,at+1,sqr-1)ins(cal(i)); 57 } 58 F(i,ahd,bhd-1)retb+=ask(S-cal(i)); 59 printf("%lld\n",retb-reta); 60 } 61 return 0; 62 } View Code

?

?

轉載于:https://www.cnblogs.com/bin-gege/p/5696092.html

總結

以上是生活随笔為你收集整理的hdu_5085_Counting problem(莫队分块思想)的全部內容，希望文章能夠幫你解決所遇到的問題。

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