分类 数位DP 下的文章

BZOJ 1833: [ZJOI2010]count 数字计数

Description给定两个正整数a和b,求在[a,b]中的所有整数中,每个数码(digit)各出现了多少次。Input输入文件中仅包含一行两个整数a、b,含义如上所述。Output输出文件中包含一行10个整数,分别表示0-9在[a,b]中出现了多少次。Sample Input1 99Sample Output9 20 20 20 20 20 20 20 20 20HINT30%的数据中,a<=b<=10^6;100%的数据中,a<=b<=10^12。Solution又是一道数位 DP 的题,照旧写记忆化搜索,需要处理一下前导零的情况。Code#i- 阅读剩余部分 -

BZOJ 1026: [SCOI2009]windy数

Descriptionwindy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道,在A和B之间,包括A和B,总共有多少个windy数?Input包含两个整数,A B。Output一个整数Sample Input【输入样例一】1 10【输入样例二】25 50Sample Output【输出样例一】9【输出样例二】20HINT100%的数据,满足 1 <= A <= B <= 2000000000 。Solution数位 DP 入门题,记忆化搜索一波就可以了。Code#include <cstdi- 阅读剩余部分 -

HDU 2089: 不要62

Problem Description杭州人称那些傻乎乎粘嗒嗒的人为62(音:laoer)。杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来,就可以消除个别的士司机和乘客的心理障碍,更安全地服务大众。不吉利的数字为所有含有4或62的号码。例如:62315 73418 88914都属于不吉利号码。但是,61152虽然含有6和2,但不是62连号,所以不属于不吉利数字之列。你的任务是,对于每次给出的一个牌照区间号,推断出交管局今次又要实际上给多少辆新的士车上牌照了。Input输入的都是整数对n、m(0<n≤m<1- 阅读剩余部分 -

HDU 3555: Bomb(不要49)

Problem给定一个 n ,求 [1, n] 有多少个数包含 49。Code数位 DP#include <cstdio> #include <algorithm> #include <cstdlib> #include <cstring> #define long unsigned long long using namespace std; long a[100]; long dp[100][3]; /* dp[i][0] 前 i 位不包含 49 的个数 dp[i][1] 前 i 位以 9 开头但不包含 49 的个数 dp- 阅读剩余部分 -