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

題目大意：規(guī)定 A 數(shù)組為所有十進(jìn)制下含有 7 或者可以被 7 整除的數(shù)字，例如 A 數(shù)組中的前 10 個(gè)數(shù)為：?{a[1]=7,a[2]=14,a[3]=17,a[4]=21,a[5]=27,a[6]=28,a[7]=35,a[8]=37,a[9]=42,a[10]=47}，同時(shí)規(guī)定 B 數(shù)組為 A 數(shù)組的一個(gè)子集，其中不含有以 A 中元素作為下標(biāo)的 A 數(shù)組，例如 B 數(shù)組中的前 10 個(gè)數(shù)為：?{b[1]=7,b[2]=14,b[3]=17,b[4]=21,b[5]=27,b[6]=28,b[7]=37,b[8]=42,b[9]=47,b[10]=49}，因?yàn)?7 是 A 數(shù)組中的元素，所以 B 中不能含有 A[ 7 ] ，即不能含有 35 這個(gè)元素

題目分析：首先給定一個(gè)數(shù)字 x，不難用 數(shù)位dp 求出 x 前面共有多少個(gè) A 數(shù)組中的元素，不要忘記減去 1 ，代表答案為 0 時(shí)的貢獻(xiàn)，現(xiàn)在需要求一下 B 數(shù)組與 A 數(shù)組的關(guān)系，因?yàn)?B 數(shù)組是 A 數(shù)組的一個(gè)子集，所以考慮先計(jì)算出 A 數(shù)組的大小為 F( x ) ，也就是說(shuō)此時(shí)的 A 數(shù)組為 a[ 1 ] , a[ 2 ] ... a[ F( x ) ] ，此時(shí) A 數(shù)組中最大的下標(biāo)也就是 F( x ) 了，因?yàn)?B 數(shù)組中不能含有的數(shù)字與其在 A 數(shù)組紅的下標(biāo)有關(guān)系，所以再單獨(dú)求一下 F( x ) 前面共有多少個(gè) A 數(shù)組的元素，這些元素是不可以出現(xiàn)在 B 數(shù)組中的，換句話說(shuō)，B 數(shù)組的表達(dá)式就是 F( x ) - F( F( x ) ) 了，打個(gè)表觀察一下不難發(fā)現(xiàn)這個(gè)值具有單調(diào)性，所以可以直接二分答案然后判斷

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;LL dp[70][10][2];//dp[pos][mod][have_7?]int b[70];LL dfs(int pos,int mod,bool flag,bool limit) {if(pos==-1)return flag||mod==0;if(!limit&&dp[pos][mod][flag]!=-1)return dp[pos][mod][flag];int up=limit?b[pos]:9;LL ans=0;for(int i=0;i<=up;i++)ans+=dfs(pos-1,(mod*10+i)%7,flag||(i==7),limit&&i==up);if(!limit)dp[pos][mod][flag]=ans;return ans; }LL solve(LL num) {int cnt=0;while(num){b[cnt++]=num%10;num/=10;}return dfs(cnt-1,0,false,true)-1; }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);memset(dp,-1,sizeof(dp));LL n;while(scanf("%lld",&n)!=EOF){ull l=1,r=LLONG_MAX,ans;while(l<=r){ull mid=l+r>>1;LL temp=solve(mid);if(temp-solve(temp)>=n){ans=mid;r=mid-1;}elsel=mid+1;}printf("%llu\n",ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的SDUT - 2609 A-Number and B-Number(二分+数位dp)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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