[暑假集训--数位dp]hdu3555 Bomb

时间：2023-03-09 17:07:57
[暑假集训--数位dp]hdu3555 Bomb
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
3
1
50
500
Sample Output
0
1
15
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.

数位dp，找子序列‘49’

记一下有没有出现过'4',是否已经出现过"49"

 #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 mkp(a,b) make_pair(a,b)

 #define pi 3.1415926535897932384626433832795028841971

 using namespace std;

 inline LL read()

 {

     LL x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 LL n,len;

 LL f[][][];

 int d[];

 inline LL dfs(int now,int dat,int sat,int fp)

 {

     if (now==)return sat;

     if (!fp&&f[now][dat][sat]!=-)return f[now][dat][sat];

     LL ans=,mx=(fp?d[now-]:);

     for (int i=;i<=mx;i++)

     {

         if (sat||!sat&&dat==&&i==)ans+=dfs(now-,i,,fp&&mx==i);

         else ans+=dfs(now-,i,,fp&&mx==i);

     }

     if (!fp&&f[now][dat][sat]==-)f[now][dat][sat]=ans;

     return ans;

 }

 inline LL calc(LL x)

 {

     LL xxx=x;

     len=;

     while (xxx)

     {

         d[++len]=xxx%;

         xxx/=;

     }

     LL sum=;

     for (int i=;i<=d[len];i++)

     sum+=dfs(len,i,,i==d[len]);

     return sum;

 }

 int main()

 {

     memset(f,-,sizeof(f));

     int T=read();

     while (T--)n=read(),printf("%lld\n",calc(n));

 }

hdu 3555

相关文章