当前位置: 代码迷 >> 综合 >> poj 3208 Apocalypse Someday 自动机+dp
  详细解决方案

poj 3208 Apocalypse Someday 自动机+dp

热度:50   发布时间:2024-01-19 05:52:14.0

题意:

求第n个包含3个连续6的数。

分析:

设状态0表示末尾没有6,状态1表示末尾有1个6,状态2表示末尾有2个6,状态3表示末尾有3个6或之前有3个6,可构造出确定状态自动机。然后对该自动机进行dp,a[i][j]表示位于自动机的j状态,再走i步,能包括含3个6的数的个数。之后再用数位dp的思想由高位至低位确定最终答案每位上的数。这和AC自动机是有区别的,需好好体会。

代码:

//poj 3208
//sep9
#include <iostream>
using namespace std;
typedef long long LL;
const int maxN=16;
int s[4][12];
LL a[maxN][4],n;int main()
{memset(s,0,sizeof(s));memset(a,0,sizeof(a));s[0][6]=1;s[1][6]=2;s[2][6]=3;int i,j,k;for(i=0;i<10;++i)s[3][i]=3;	a[0][3]=1;for(i=1;i<maxN;++i)for(j=0;j<4;++j)for(k=0;k<10;++k)a[i][j]+=a[i-1][s[j][k]];	int T;scanf("%d",&T);while(T--){int w;scanf("%lld",&n);for(w=0;w<maxN;++w)if(a[w][0]>=n)	break;int state=0;LL ans=0;while(w--){LL tmp=0;for(i=0;i<10;++i){tmp+=a[w][s[state][i]];if(tmp>=n){n-=tmp-a[w][s[state][i]];state=s[state][i];ans=10*ans+i;break;}		}	}printf("%lld\n",ans);}	return 0;	
}