HDU 3555 Bomb 【数位DP】
HDU 3555 Bomb【数位DP】
数位DP第三题。学习ing~
题目传送门:这里
题目大意:
求$[1,x]$中含有$49$的数的个数。$T$次询问,$1 \leq T \leq 10000$,$1 \leq x \leq 2^{63}-1$。
前面讲的貌似是第一种数位DP的方法啦,现在我们来讲第二种。
这种一般用三个dp数组来表达,好像叫“有穷自动机”(雾?)好高端。
本题的话,$f[i,0]$表示长度小于等于$i$且不含$49$的数的个数,$f[i,1]$表示长度等于$i$且最高位含有$9$的不含$49$的数的个数,$f[i,2]$表示长度小于等于$i$含$49$的数的个数。
听起来十分的饶舌,但是很好写转移方程。
对于$f[i,0]$,长度小于等于$i$不含$49$的个数:那么就把长度小于等于$i-1$不含49的个数乘10就好了吧!(捂脸),不对,还要减去长度等于$i-1$最高位含有$9$的不含$49$的个数。所以$f[i,0]=f[i-1,0] \times 10 - f[i-1,1]$。
对于$f[i,1]$,长度等于$i$的最高位为$9$的不含$49$的个数,那么就是长度小于等于$i-1$的不含49的个数,第$i$位填个$9$就好啦!好有道理,那么$f[i,1]=f[i-1,0]$。
对于$f[i,2]$,表示长度小于等于$i$含$49$的数的个数,等于长度小于等于$i-1$的含$49$的个数,最高位随便填都行,完了吗?没有!还要加上长度为$i-1$最高位为$9$的不含$49$的个数,因为填一个$4$就造出$49$了!所以,$f[i,2]=f[i-1,2] \times 10 + f[i-1,1]$。
好啦,$dp$预处理好了,下面就是正常的处理程序啦。
关于状态的设计一般有3个方面:
$f[i,0]$表示长度小于等于$i$且不符合条件的数的个数,$f[i,1]$表示长度等于$i$且(不)符合条件(+特殊限制)的的数的个数,$f[i,2]$表示长度小于等于$i$符合条件的数的个数。
特殊限制一般就有几个方面,比如本题要49,特殊限制就是最高位是9;因为这样设计,下一个填4就会造出49,好进行转移。上一题数位dp:不要62好像也可以这样来做呀,诸君稍等,容我打打代码。
$2015/08/21/18:30$已更新,下一篇博文啦。
# include <stdio.h> # include <string.h> using namespace std; typedef unsigned long long ull; ull dp[25][3]; int T; //dp[i][0]:长度<=i的不含49的数的个数 //dp[i][1]:长度为i,且最高位含有9的不含49的数的个数 //dp[i][2]:长度<=i的含有49的数个数 inline void getdp() { memset(dp,0,sizeof(dp)); dp[0][0]=1; for (int i=1;i<=22;++i) { dp[i][0]=dp[i-1][0]*10-dp[i-1][1]; dp[i][1]=dp[i-1][0]; dp[i][2]=dp[i-1][2]*10+dp[i-1][1]; } } int d[25],dn; inline void getd(ull x) { dn=0;memset(d,0,sizeof(d)); while(x) d[++dn]=x%10,x/=10; } ull calc(ull x) { ull cnt=0; bool flag=0; for (int i=dn;i>=1;--i) { cnt+=dp[i-1][2]*d[i]; if(flag) cnt+=dp[i-1][0]*d[i]; else { if(d[i]>4) cnt+=dp[i-1][1]; if(d[i+1]==4&&d[i]==9) flag=1; } } if(flag) cnt++; return cnt; } int main() { ull x; scanf("%d",&T); getdp(); while(T--) { scanf("%I64u",&x); getd(x); printf("%I64u\n",calc(x)); } return 0; }
2022年8月10日 17:08
Well, to be precise it is very important for anything to run properly such as a business creative which is grammar perfect or else a news outlet or a blog article which is properly checked for any grammar mistakes. Grammarly Alternative At the same time, people love to believe that working knowledge of grammar better resides with humans but it is true that the modern softwares, tools and plugins like Grammarly has been a great help to anyone who is looking to ensure that their words make sense.
2023年4月18日 18:37
Board 12th Class Model Paper 2023 Aspirants who had Registered for the Board 12th Class Exam can Download the Previous Paper When Board 12th Announces the Dates to Download the Question Paper. 12thmodelpapers.in Board 12th Question Papers will be Provided Very Soon Through Online Mode and all the Applicants Should Visit the Official Page Regularly for More Information Regarding Previous Paper, Examination Date. Check the Below Provided Details for More Information About the Board 12th Model Paper.