poj3208 Apocalypse Someday[数位DP]

数位中出现至少3个连续的'6'的数字（称魔鬼数），询问满足要求的排名k的数。

经典题型。采用试填法。

递推做法：预处理出$i$位数字中满足要求的数（下记为'魔鬼数'）。对每一位都从0到9试一遍，然而卡在了试填时试到6这个数时该怎么办，不太会做。然后才知道可以记录填到目前的上一位已有多少个连续的6，这样可以配合当前的计算出来。

所以就有这个$f[i][0]=9*(f[i-1][0]+f[i-1][1]+f[i-1][2]),f[i][1]=f[i-1][0],f[i][2]=f[i-1][1],f[i][3]=10*f[i-1][3]+f[i-1][2]$

其中0表示开头有0个6，1表示开头有一个6，2同理，3表示当前小于等于i位的魔鬼数的数量（也就相当于把各位数的魔鬼数累积起来）

注意是算入前导0的。比如有004566674，因为试填时他也算一种。而开头不必担心，看代码第1次循环就会发现考虑0的时候恰好把小于i位的魔鬼数数量都减掉了，说不太清楚，还是自己想想吧。

用k以辅助记录当前填过的末尾连续的6数量，用于处理填6时计算，每填一个6就多算一下。k到3时表示我已经诞生连续3个的6了，所以后面所有的填法都合法，这是要再单独特殊处理，看code。

其他就是常规的试填。

说两点细节：

注意边界处理 ,考虑预处理DP值的边界，尤其是f[0],f[1]等；

试填也要考虑边界。比如开始时。结束时（最后一位），这直接和f[0][0]的初始化产生了联系。所以两个边界都要看一下检查正确性。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #define dbg(x) cerr<<#x<<" = "<<x<<endl

 #define ddbg(x,y) cerr<<#x<<" = "<<x<<"   "<<#y<<" = "<<y<<endl

 using namespace std;

 typedef pair<int,int> pii;

 typedef long long ll;

 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,:;}

 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,:;}

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 ll f[][],rk,cnt;

 int T;

 inline void preprocess(){

     f[][]=,f[][]=;f[][]=;//←注意边界处理 ,DP和试填都要检验一下

     for(register int i=;i<=;++i)f[i][]=*(f[i-][]+f[i-][]+f[i-][]),f[i][]=f[i-][],f[i][]=f[i-][],f[i][]=*f[i-][]+f[i-][];

 }

 int main(){//freopen("test.in","r",stdin);freopen("test.out","w",stdout);

     read(T);preprocess();while(T--){

         read(rk);int x;for(x=;x<=;++x)if(rk<=f[x][])break;

         for(register int i=x,k=;i;--i){

             for(register int j=;j<=;++j){

                 cnt=f[i-][];

                 if(k==)cnt+=f[i-][]+f[i-][]+f[i-][];

                 else if(j==)for(register int l=-k;l<;++l)cnt+=f[i-][l];

                 if(rk<=cnt){

                     if(k<){if(j==)++k;else k=;}

                     printf("%d",j);break;

                 }

                 else rk-=cnt;

             }

         }

         puts("");

     }

     return ;

 }

然后讲一下记搜的，可以套模板。求第k大的数，可以转化为二分枚举区间[1,n]的右边界n，看[1,n]的满足要求的数，由于其随区间变大而单调增，所以是二分。通过不断调整，可以找到最小n使得区间[1,n]恰有k个满足要求的数。这个因为是套模板，所以很好写。但是二分的话会让复杂度多一个log。。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #define dbg(x) cerr<<#x<<" = "<<x<<endl

 using namespace std;

 typedef long long ll;

 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,:;}

 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,:;}

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 int T;

 ll L,R,f[][][][],b[],aim;

 ll dp(int len,bool las,bool las2,bool fil,bool limit){

     if(!len)return fil;

     if(!limit&&~f[len][las][las2][fil])return f[len][las][las2][fil];

     ll cnt=;int num=limit?b[len]:;

     for(register int i=;i<=num;++i)cnt+=dp(len-,i==,las,fil||(las&&las2&&i==),limit&&i==num);

     return limit?cnt:f[len][las][las2][fil]=cnt;

 }

 inline ll solve(ll x){

     int k=;while(x)b[++k]=x%,x/=;

     return dp(k,,,,);

 }

 int main(){//freopen("tmp.txt","r",stdin);//freopen("test.out","w",stdout)£»

     memset(f,-,sizeof f);

     read(T);while(T--){

         read(aim);L=,R=1e10;ll mid;

         while(L<R){

             mid=L+R>>;

             if(solve(mid)<aim)L=mid+;

             else R=mid;

         }

         printf("%lld\n",L);

     }

     return ;

 }

巴特西

poj3208 Apocalypse Someday[数位DP]

最新文章

热门文章