題目鏈接：點(diǎn)擊查看

題目大意：給出平衡數(shù)的定義：每一個(gè)偶數(shù)出現(xiàn)的次數(shù)必須是奇數(shù)次，每一個(gè)奇數(shù)出現(xiàn)的次數(shù)必須是偶數(shù)次，求給定區(qū)間中有多少個(gè)平衡數(shù)

題目分析：數(shù)位dp，這個(gè)題目就難在怎么確定狀態(tài)轉(zhuǎn)移，本來(lái)我看錯(cuò)題目了，以為只要有奇數(shù)個(gè)偶數(shù)和偶數(shù)個(gè)奇數(shù)就行，但還是想的太簡(jiǎn)單了，看了網(wǎng)上大佬們的題解才知道，原來(lái)我們可以把每一個(gè)數(shù)字的狀態(tài)壓縮，每一個(gè)數(shù)字都有三種狀態(tài)：0表示沒出現(xiàn)過，1表示出現(xiàn)了奇數(shù)次，2表示出現(xiàn)了偶數(shù)次，普通的狀態(tài)壓縮都是0和1的兩種狀態(tài)，這個(gè)題有三種狀態(tài)，所以我們用三進(jìn)制來(lái)儲(chǔ)存就好了，三的11次方?jīng)]超過60000，所以dp數(shù)組開dp[20][60000]就好，dp[i][j]代表在第i位，狀態(tài)位j時(shí)的符合條件的數(shù)量，在轉(zhuǎn)移狀態(tài)的時(shí)候我用到了一個(gè)change函數(shù)，具體怎么實(shí)現(xiàn)的非常巧妙，也算是學(xué)到了進(jìn)制轉(zhuǎn)換的一點(diǎn)小技巧，假如想修改第i位上的數(shù)字時(shí)（從右向左的第i個(gè)），我們需要先得到第i位上的數(shù)字是多少，常規(guī)操作是先一直除3，直到讓第i位變成當(dāng)前的個(gè)位，然后對(duì)3取模即可，如果想增加的話也是需要加三的i次方，聽起來(lái)好像已經(jīng)很簡(jiǎn)單了，但是卻有更簡(jiǎn)單的方法，就是利用一個(gè)輔助數(shù)組f儲(chǔ)存3的i次方(1<=i<=10)，然后用表示狀態(tài)的數(shù)對(duì)f[i+1]取余先令其范圍變?yōu)?~f[i+1]，然后在繼續(xù)除以f[i]，就可以直接獲得第i位上的數(shù)了，具體的看代碼吧：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<cmath> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=20; LL dp[N][60000];//dp[pos][sta]int b[N];int f[N];//儲(chǔ)存3的i次方bool check(int sta) {for(int i=0;i<=9;i++,sta/=3){if((i&1)&&sta%3==1)return false;if(!(i&1)&&sta%3==2)return false;}return true; }int change(int sta,int i) {int x=(sta%f[i+1])/f[i];//獲得第i位上的數(shù)if(x==2)return sta-f[i];elsereturn sta+f[i]; }LL dfs(int pos,int sta,bool lead,bool limit) {if(pos==-1)return check(sta);if(!limit&&dp[pos][sta]!=-1)return dp[pos][sta];LL ans=0;int up=limit?b[pos]:9;for(int i=0;i<=up;i++){if(lead&&i==0)ans+=dfs(pos-1,0,true,limit&&i==b[pos]);elseans+=dfs(pos-1,change(sta,i),false,limit&&i==b[pos]);}if(!limit)dp[pos][sta]=ans;return ans; }LL solve(LL n) {int cnt=0;while(n){b[cnt++]=n%10;n/=10;}return dfs(cnt-1,0,true,true); }int main() { // freopen("input.txt","r",stdin)int w;cin>>w;f[0]=1;for(int i=1;i<=10;i++)f[i]=f[i-1]*3; memset(dp,-1,sizeof(dp));while(w--){LL a,b;scanf("%lld%lld",&a,&b);printf("%lld\n",solve(b)-solve(a-1));}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的SPOJ - BALNUM Balanced Numbers(数位dp+进制转换)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。