余点击题解,观其大略,只道码风奇特,然亦有恨,未见一人以大法师(DFS)解之
仓促之间作此篇,以了平生与数位DP之缘
题目描述
给定两个整数 a 和 b,求 a 和 b 之间的所有数字中0~9的出现次数。
例如,a=1024,b=1032,则 a 和 b 之间共有9个数如下:
1024 1025 1026 1027 1028 1029 1030 1031 1032
其中‘0’出现10次,‘1’出现10次,‘2’出现7次,‘3’出现3次等等…
输入样例
1 10
44 497
346 542
1199 1748
1496 1403
1004 503
1714 190
1317 854
1976 494
1001 1960
0 0
输出样例
1 2 1 1 1 1 1 1 1 1
85 185 185 185 190 96 96 96 95 93
40 40 40 93 136 82 40 40 40 40
115 666 215 215 214 205 205 154 105 106
16 113 19 20 114 20 20 19 19 16
107 105 100 101 101 197 200 200 200 200
413 1133 503 503 503 502 502 417 402 412
196 512 186 104 87 93 97 97 142 196
398 1375 398 398 405 499 499 495 488 471
294 1256 296 296 296 296 287 286 286 247
C++ 代码
//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define RG register
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int N=2001;
ll f[N][N],k[N];
ll a,b;
inline ll dfs(bool lead,bool limit,int dep,int x,ll sum)
{//lead为0说明有前导0
if(!dep) return sum;
//已经搜完了
if(lead&&!limit&&(~f[dep][sum])) return f[dep][sum];
//记忆化
int ed=(limit) ? k[dep]:9;
//这一个位上的取值范围
ll res=0;
for (int i=0;i<=ed;i++)
res+=dfs(lead|i,limit&&(i==ed),dep-1,x,sum+((lead|i)&&(i==x)));
if(lead&&!limit) f[dep][sum]=res;
return res;
}
inline ll dp(ll n,int x)
{
int cnt=0;
while(n) k[++cnt]=n%10,n/=10;
/*对每一位的限制,比如5555,如果当前到了百位并且我们先从高位取,上一次取了5,如果百位上
取的数字是6,即使后面全取0,也是5600,超过了5555这个范围,明白了吧
*/
return dfs(0,1,cnt,x,0);//前导0,最高位限制,数位,数
/*
这里记录有没有前导0,是我们在找0这个数字时,如果范围还是5555,而当前遍历到的数
时245,即0245,如果不记录,这个前导0也会被记入总数,所以这个对有无前导0的判断
是针对0的统计
*/
}
int main()
{
while(scanf("%lld%lld",&a,&b))
{
if(a==0&&b==0) break;
if(a>b) swap(a,b);
for (int i=0;i<=9;i++)
{
memset(f,-1,sizeof(f));//初始化(毕竟每一次要用)
printf("%lld ",dp(b,i)-dp(a-1,i));
//差分的思想,对0->9这10个数字分别查找
}
printf("\n");
}
return 0;
}
习惯了dfs版本的数位dp,妙啊!
因为只会写搜索QwQ
sum > 2001 了吧, 数组越界了吧
厉害
巨巨,这种记忆化搜索的DFS,这种的状态表示,为什么是对的?
sum和limit表示什么
sum是到当前深度已经出现x的个数, limit是标记当前位能不能取满0~9
佬一语点醒梦中人, 多谢!
虽然写的很简洁,但明白f数组和sum的物理含义不明白。
甚妙
妙啊,妙啊
能问一下f[i][j] i,j分别表示的什么吗
i表示搜到的层数,j表示当前层数的数
DFS,计甚妙,分析高,注释位,乃好文
余观此题解,甚是妙哉.
文言文tql!