首页 > 代码库 > POJ3208:Apocalypse Someday
POJ3208:Apocalypse Someday
传送门
很神奇的一道题,正解是AC自动机+数位DP,个人感觉POPOQQQ大爷的方法更方便理解。
按照一般套路,先搞个DP预处理,设$f[i][0/1/2/3]$分别表示对于$i$位数,其中有多少个前0/1/2位为6的个数和整体中包含666的个数。那么就很容易得到以下转移方程。
$f[i][3]=f[i-1][3] \times 10+f[i-1][2]$
$f[i][2]=f[i-1][1]$
$f[i][1]=f[i-1][0]$
$f[i][0]=(f[i-1][0]+f[i-1][1]+f[i-1][2]) \times 9$
剩下的就比较麻烦了。
刚开始我想的是不断剔除排名从而确定每一位上的数。但是这个是很麻烦的,而且不好处理。更换一种方案就是通过二分确定这个排名的个数,只要我们能验证小于$N$的数中有多少个满足要求的数。
这个求的过程相当玄学...我也说不上来QAQ
1 //NOIp DP apo 2 //by Cydiater 3 //2016.10.4 4 #include <iostream> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <cstring> 8 #include <string> 9 #include <algorithm>10 #include <queue>11 #include <map>12 #include <ctime>13 #include <iomanip>14 #include <cmath>15 using namespace std;16 #define ll long long17 #define up(i,j,n) for(ll i=j;i<=n;i++)18 #define down(i,j,n) for(ll i=j;i>=n;i--)19 #define FILE "apo"20 const ll MAXN=1e6+5;21 const ll oo=0x3f3f3f3f;22 const ll mod=(1<<31)-1;23 inline ll read(){24 char ch=getchar();ll x=0,f=1;25 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}26 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}27 return x*f;28 }29 ll f[25][10],leftt,rightt,mid,T;30 namespace solution{31 void pret(){32 memset(f,0,sizeof(f));33 f[0][0]=1;34 up(i,1,21){35 f[i][3]=f[i-1][3]*10+f[i-1][2];36 f[i][2]=f[i-1][1];37 f[i][1]=f[i-1][0];38 f[i][0]=(f[i-1][0]+f[i-1][1]+f[i-1][2])*9;39 }40 }41 ll check(ll num){42 ll di=0,far=1,tmp=0,cnt=0,ans=0;43 for(;far<num;far*=10,di++);44 while(tmp<num){45 ll re_cnt;46 while(tmp+far<=num){47 tmp+=far;48 if(cnt==3) re_cnt=3;49 else if((tmp/far)%10==7) re_cnt=cnt+1;50 else re_cnt=0;51 down(i,3,3-re_cnt)ans+=f[di][i];52 }53 if(cnt!=3)cnt=((tmp/far)%10==6?cnt+1:0);54 di--;far/=10;55 }56 return ans;57 }58 ll slove(ll N){59 leftt=1;rightt=100000000000000000LL;60 N--;61 while(leftt+1<rightt){62 mid=(leftt+rightt)>>1;63 ll tmp=check(mid);64 if(tmp>N) rightt=mid;65 else leftt=mid;66 }67 if(check(leftt)==N) return leftt;68 return rightt;69 }70 }71 int main(){72 freopen(FILE".in","r",stdin);73 //freopen(FILE".out","w",stdout);74 using namespace solution;75 pret();76 T=read();77 while(T--)cout<<slove(read())<<endl;78 return 0;79 }
POJ3208:Apocalypse Someday
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。