Bomb
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 16400 Accepted Submission(s): 5996
Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?
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.
3
1
50
500
0
1
15
题意:
给定一个数n,求[1,n]中含有”49″的数的个数。
思路:
首先我们考虑一个数中有无”49″的几种情况。(假设*中不包含”49″)
1. ***49****
2. *********
3. 9********
4. 49*******
其实1和4是一样的情况,对于3,我们只需要在最高位添加一个4便组成一个含有”49″的数字,而对于2,数字中不包含”49″。
状态转移:
dp[i][0]代表长度为 i 并且不含有”49″的数字的个数;
dp[i][1]代表长度为 i 并且不含有”49″且高位是9的数字的个数;
dp[i][2]代表长度为 i 并且含有49的数字的个数。
数组 a[i] 从低位到高位存储 n 的每一位数字。
dp[i][0] = dp[i-1][0] * a[i] - dp[i-1][1];
表示长度为 i 的不含有49的数字的个数,它等于长度为 i – 1 的不含有49的数字的个数*当前位的数字,因为这个位置可以填0~a[i] – 1,然后再减去长度为 i – 1 的最高位是9的数字的个数,因为如果长度为 i – 1 的最高位是9的话,那么高一位就不能填4了,否则就组成了49。dp[i][1] = dp[i-1][0];
表示长度为 i 的并且不含有49同时最高位是9的数字的个数,它等于长度为 i – 1 的不含有49的数字的个数,因为只要在它的高一位加上一个9就可以了。dp[i][2] = dp[i-1][2] * a[i] + dp[i-1][1];
表示长度为 i 的含有49的数字的个数,它等于长度为 i – 1 满足条件的数字的个数*当前的数字,再加上长度为 i – 1 的不含有49并且最高位是9的数字的个数,因为这个时候,只要在高一位加上一个4就可以了,这样在最高的两位就组成了一个49。
然后我们可以从一个数的最高位开始枚举,首先要加上低一位满足条件数字的个数,如果当前位大于4,还要加上低一位最高位是9且不包含49的数字的个数,因为这种情况下只要我们把当前位设为4便可满足要求。
如果枚举位过程中已经遇到过49,则以后的枚举加上不含有49的数字个数,因为49已经出现过了,所以这样的组合依然满足题意。
AC代码:
#include <iostream>
#include<cstdio>
using namespace std;
#include<algorithm>
#include<string.h>
typedef __int64 LL;
LL dp[21][3];
int a[21];
void init() //预处理长度为i位dp[i][]的值
{
dp[0][0]=1;
for(int i=1; i<21; i++)
{
dp[i][0]=dp[i-1][0]*10-dp[i-1][1]; //长度为 i 并且不含有49的数字的个数
dp[i][1]=dp[i-1][0]; //长度为 i 并且不含有49且高位是9的数字的个数
dp[i][2]=dp[i-1][2]*10+dp[i-1][1]; //长度为 i 并且含有49的数字的个数
}
}
void solve(LL n)
{
int len=0;
while(n) //整数n分解每一位
{
a[++len]=n%10;
n/=10;
}
LL ans=0;
int last=0;
bool flag=false;
for(int i=len; i>0; i--) //从最高位开始枚举
{
ans+=dp[i-1][2]*a[i];
if(flag)ans+=dp[i-1][0]*a[i]; //如果前面出现过49
if(!flag&&a[i]>4)ans+=dp[i-1][1]; //+[i-1]位数最高位为9并且不包含49的情况
if(last==4&&a[i]==9) //如果出现了49
flag=true;
last=a[i];
}
printf("%I64d\n",ans);
}
int main()
{
int T;
init();
scanf("%d",&T);
while(T--)
{
LL n;
scanf("%I64d",&n);
solve(n+1); //n+1可以避免数字末尾是49的时候出错
}
return 0;
}