首页 > 代码库 > hdu3555 Bomb

hdu3555 Bomb

2024-08-07 16:57:08   221人阅读

Bomb

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 8554    Accepted Submission(s): 2981


Problem Description
The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence "49", the power of the blast would add one point.
Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?
 

 

Input
The first line of input consists of an integer T (1 <= T <= 10000), indicating the number of test cases. For each test case, there will be an integer N (1 <= N <= 2^63-1) as the description.

The input terminates by end of file marker.
 

 

Output
For each test case, output an integer indicating the final points of the power.
 

 

Sample Input
3150500
 

 

Sample Output
0115
Hint
From 1 to 500, the numbers that include the sub-sequence "49" are "49","149","249","349","449","490","491","492","493","494","495","496","497","498","499",so the answer is 15.
 
 
怎么到处都是英文题……
题意是求1到n中含有“49”子串的数字的个数。多组询问。
这一看就是数位dp啊……（话说如果不只一个限制的话岂不是ac自动机上dp）
预处理:f[i][j]表示i位的数（允许前导0），头一位是j的含"49"的方案数
显然f[i][j]=Σf[i-1][k],0<=k<9.
当第i位是4而第i-1位是9的时候，已经满足条件，因此后面取什么都无所谓了。直接加上第i-2位以后的所有数的个数，即10^(i-2)。
由容斥原理，f[i][j]再减去原来多加的f[i-1][9]。
当处理的时候，先把当前询问的x一位一位提出来。
1、首先考虑当前不存在a[now+1]==4且a[now]==9的情况：注意到此时方案是不会相互影响的，也就是取1000~1999的方案数和取51000~51999的方案数是一样的。因为在头上加上5之后并不会造成额外的"49"产生。
2、如果a[now+1]==4且a[now]==9，显然跟上面一样，接下来取什么都是无所谓的。直接加上x剩下来的后now-1位数rest
#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x7ffffff#define pa pair<int,int>#define pi 3.1415926535897932384626433832795028841971using namespace std;inline LL read(){    LL x=0,f=1;char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}inline void write(LL a){    if (a<0){printf("-");a=-a;}    if (a>=10)write(a/10);    putchar(a%10+‘0‘);}inline void writeln(LL a){write(a);printf("\n");}int n;LL f[30][10];LL sec[20];inline LL wrk(LL x){    LL tot=0,dat=x;    int dig[20]={0},len=0;    while (x)    {        dig[++len]=x%10;        x/=10;    }    while (len)    {        dat-=dig[len]*sec[len-1];        for (int i=0;i<dig[len];i++)        tot+=f[len][i];        if (dig[len+1]==4&&dig[len]==9)        {            tot+=dat+1;            break;        }        len--;    }    return tot;}int main(){    n=read();    sec[0]=1;for(int i=1;i<=17;i++)sec[i]=sec[i-1]*10;    for (int i=2;i<=20;i++)    for (int j=0;j<10;j++)    {        for (int k=0;k<10;k++)f[i][j]+=f[i-1][k];        if (j==4)f[i][j]+=sec[i-2]-f[i-1][9];    }    for(int i=1;i<=n;i++)    {        LL x=read();        writeln(wrk(x));    }    return 0;}

　　

hdu3555 Bomb


联系
我们