反恐专家
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 50 Accepted Submission(s) : 30
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
紧急！
有人发现了一枚定时炸弹！
反恐专家杨逸舟奉命赶到现场紧急处理。
经过分析，杨逸舟发现，这次恐怖分子改进了定时炸弹——定时炸弹的数字序列从1到N计数，如果当前数字序列包含子序列“49”，炸弹的威力就将增加一个点。
现在，已知数字N，反恐专家杨逸舟想知道炸弹最终的威力是多少。
Input
输入数据第一行是一个整数T (1 <= T <= 10000)，表示测试数据的组数。
每组数据包含一个整数N (1 <= N <= 2^63-1)，其含义如题目描述。
Output
每组数据请输出一个表示炸弹威力的整数，每组数据输出一行。
Sample Input
3
1
50
500
Sample Output
0
1
15
Hint
从1到500，包含49的数字有"49","149","249","349","449", "490","491","492", "493","494", "495", "496","497","498","499", 所以答案是15.
#include<bits/stdc++.h>
using namespace std;
long long dp[25][3];
long long bin[25];
long long balala(long long n){ long long len=0; while(n) { bin[++len]=n; n/=10; } bin[len+1]=0; bool flag=false; long long ans=0; for(long long i=len;i>=1;i--) { ans+=dp[i-1][2]*bin[i]; if(flag) { ans+=dp[i-1][0]*bin[i]; } else { if(bin[i]>4) ans+=dp[i-1][1]; } if(bin[i+1]==4&&bin[i]==9) { flag=true; } } if(flag) { ans++; } return ans;}int main(){ dp[0][0]=1; dp[0][1]=0; dp[0][2]=0; long long m,n; cin>>n; for(int i=1;i<21;i++) { dp[i][0]=10*dp[i-1][0]-dp[i-1][1];//前面不行的减去9前加4的 dp[i][1]=dp[i-1][0];//前面不行前面加9 dp[i][2]=dp[i-1][2]*10+dp[i-1][1];//前面可以的随便加还有9前加4的 // printf("%lld %lld %lld\n",dp[i][0],dp[i][1],dp[i][2]); } while(n--) { cin>>m; cout<<balala(m)<<endl; }
