http://acm.hdu.edu.cn/showproblem.php?pid=3555
BombTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others) Total Submission(s): 7316 Accepted Submission(s): 2551 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
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", Author
fatboy_cw@WHU
Source
Recommend
|
题意：输入n，输出1~n中含有“49”的整数数量。(1 <= N <= 2^63-1
题解：
数位DP 或 记忆化搜索。
n这么大，不可能枚举。不过我们先看看按位从高到低的枚举深搜：
ll dfs(int w, int state, bool limit) {
if(w<) return state==;
int maxi=limit ? a[w] : ;
ll re=;
for(int i=; i<=maxi; i++) {
int s=state;
if(state==) {
if(i==) s=;
else if(i!=)s=;
} else if(state== && i==) s=;
re+=dfs(w-, s, limit && i==a[w]);
}
return re;
}
ans=dfs(an-1,0,1)。其中state为0表示没49，state为1表示上一位是9，state为2表示有49。a[w]为n的第(w+1)位，n有an位。
可以看出这是一个非常裸的搜索，简直枚举每个数，肯定超时。
但仔细观察可以发现，有好多次递归都返回同样的结果。对，就是limit=0时，w和state固定的调用，都是返回0~w位的数随意取0~9，含有49的种类数。这样，我们可以用记忆化搜索，记录算好的f[w][state]，下次调用的时候就不用算，直接返回值。
还有更快的方法，就是直接数位DP。这个实在是碉，我自己的话根本写不出来。
首先初始化还比较容易，像这样，生成的f[][]是和上面记忆化搜索的一样的：
void init(){
memset(f,,sizeof(f));
f[][]=;
for(int i=;i<;i++){
f[i][] = (ll)f[i-][]* - f[i-][]; ///没49的 = 之前没49的这一位随便 - 之前开头是9的这一位是4
f[i][] = f[i-][]; ///开头是9的 = 之前没49的这1位是9
f[i][] = (ll)f[i-][]* + f[i-][]; ///有49的 = 之前有49的这一位随便 + 之前开头是9的这一位是4
}
}
但是统计的时候就难了，是这样的：
ll farm(ll x) {
an=;
while(x) {
a[an++]=x%;
x/=;
}
a[an]=;
ll ans=;
bool flag=false;
for(int i=an-;i>=;i--){
ans+=(ll)f[i][]*a[i];///后面有49，这一位取0~a[i]-1（取a[i]的情况在之后的循环中计算）
if(flag) ans+=(ll)f[i][]*a[i];///前面全固定取a[i]，有49了，这位0~a[i]-1，后面取没49的（后面有49的情况已经在上一句算过了）
else if(!flag && a[i]>)///前面全固定取a[i]，没49，这一位能取4，后面开头为9的情况数f[i][1]，则就是组成49的情况数
ans+=f[i][];
if(a[i]== && a[i+]==) flag=true;///这一位取a[i]，上一位取a[i+1]时成49，标flag，日后计算
}
return ans;
}
其中for循环每层是固定比当前位更高的位为a[]，即该位的边缘值，进行计算，因为那一位取不边缘的值的情况已经在那一位算过了，具体可以看上面的注释。
记忆化搜索全代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define ll long long ll f[][];///f[i][j]，i位数，j=0是没49的，1是9开头的，2是有49的
int a[],an; ll dfs(int w, int state, bool limit) {
if(w<) return state==;
if(!limit && f[w][state]!=-) return f[w][state]; int maxi=limit ? a[w] : ;
ll re=;
for(int i=; i<=maxi; i++) {
int s=state;
if(state==) {
if(i==) s=;
else if(i!=)s=;
} else if(state== && i==) s=;
re+=dfs(w-, s, limit && i==a[w]);
} if(!limit) f[w][state]=re;
return re;
} ll farm(ll x) {
an=;
while(x) {
a[an++]=x%;
x/=;
}
return dfs(an-,,);
} int main() {
int T;
ll n;
memset(f,-,sizeof(f));
scanf("%d",&T);
while(T--) {
scanf("%I64d",&n);
printf("%I64d\n",farm(n));
}
return ;
}
数位DP全代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define ll long long ll f[][];///f[i][j]，i位数，j=0是没49的，1是9开头的，2是有49的
int a[],an; ll farm(ll x) {
an=;
while(x) {
a[an++]=x%;
x/=;
}
a[an]=;
ll ans=;
bool flag=false;
for(int i=an-;i>=;i--){
ans+=(ll)f[i][]*a[i];///后面有49，这一位取0~a[i]-1（取a[i]的情况在之后的循环中计算）
if(flag) ans+=(ll)f[i][]*a[i];///前面全固定取a[i]，有49了，这位0~a[i]-1，后面取没49的（后面有49的情况已经在上一句算过了）
else if(!flag && a[i]>)///前面全固定取a[i]，没49，这一位能取4，后面开头为9的情况数f[i][1]，则就是组成49的情况数
ans+=f[i][];
if(a[i]== && a[i+]==) flag=true;///这一位取a[i]，上一位取a[i+1]时成49，标flag，日后计算
}
return ans;
} void init(){
memset(f,,sizeof(f));
f[][]=;
for(int i=;i<;i++){
f[i][] = (ll)f[i-][]* - f[i-][]; ///没49的 = 之前没49的这一位随便 - 之前开头是9的这一位是4
f[i][] = f[i-][]; ///开头是9的 = 之前没49的这1位是9
f[i][] = (ll)f[i-][]* + f[i-][]; ///有49的 = 之前有49的这一位随便 + 之前开头是9的这一位是4
}
} int main() {
int T;
ll n;
init();
scanf("%d",&T);
while(T--) {
scanf("%I64d",&n);
printf("%I64d\n",farm(n+));///farm(x)是算小于x的
}
return ;
}