首页 > 代码库 > TOJ 2294 POJ 3286 How many 0's? 数位dp
TOJ 2294 POJ 3286 How many 0's? 数位dp
http://acm.tju.edu.cn/toj/showp2294.html
http://poj.org/problem?id=3284
题外话:集训结束,回学校了。在宿舍看了这题,没什么好想法,去洗澡了。转了两个澡堂都特么没开。。倒是在路上把这题想了。用回自己的电脑,不得不说苹果的字体渲染,真心高一个等级。
题意:给定两个数a和b,从a写到b,问一共写了多少个0。
分析:当然先转化为求0..a写多少个0。网上有更简单的做法,就是枚举每位作为0,则如果这一位本来是0,左边取1..a-1(不能取0,取0这位也没了),右边则可以任意取,如果取a,则右边只能取0到右边最大值。如果本来不是0,就是没什么限制地取。
然后我是类似上次49那题数位dp的做法。f[i]表示长度为i的数串有多少个0(没限制),g[i]表示长度为i的数串,第一位为0,有多少个0。
一样转化为求0..a写多少0。考虑a,假设长度为len,最高位填0的情况是g[len],最高位为x,那么1..x-1这些可以补在长度为len-1的数串前面,即(x-1)*f[len-1]。然后最高位就是x了,继续枚举每位下去(每次枚举的当前位,是计算当前位小于当前位的最大值的方案数,然后到下一位时,已经枚举过的都是当做对应的最大值)。如果这一位是x(!= 0),那么可以填1..x-1 * f[restlen],当前位填0,那么后面可以任意填。这一位是0,那么之后只能填从0到之后的最大值。(反正就是这么个意思。。意会一下吧。。)
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 #define debug 0 7 #define bug 0 8 long long a, b; 9 long long f[40], g[40];10 int d[40];11 long long G(int x)12 {13 if (x == 1) return 1;14 return G(x-1) + f[x-2] * 9; //当前位填0,那么可以是下一位填1-9,或是下一位填0的相同情况(递归)15 }16 void init()17 {18 f[0] = 0;19 long long exp = 1;20 for (int i = 1; i < 40; i++){ //这一位任填0-9,所以原来的变为10倍,同时计算这位为0的总数(之前的任填)。21 f[i] = f[i-1] * 10 + exp;22 exp = exp * 10;23 }24 for (int i = 1; i < 40; i++)25 g[i] = G(i);26 }27 long long cal(long long x)28 {29 if (debug) printf("%lld\n", x);30 if (x == -1) return 0;31 if (x == 0) return 1;32 int len = 0;33 while(x){34 d[len++] = x % 10;35 x /= 10;36 }37 long long ret = g[len] + f[len-1] * (d[len-1]-1);38 if (debug) printf("%lld\n", ret);39 long long exp = 1;40 for (int i = 0; i < len-2; i++)41 exp = exp * 10;42 for (int i = len-2; i >= 0; i--){43 if (d[i]) ret = ret + exp;44 else{45 long long tmp = 0;46 for (int j = i-1; j >= 0; j --)47 tmp = tmp * 10 + d[j];48 ret = ret + tmp + 1;49 }50 exp = exp / 10;51 ret = ret + f[i] * d[i];52 }53 if (debug) printf("%lld\n", ret);54 return ret;55 }56 int main()57 {58 init();59 while(scanf("%lld %lld", &a, &b))60 {61 if (a < 0 || b < 0) break;62 if (bug) printf("%lld %lld\n", cal(b), cal(a-1));63 printf("%lld\n", cal(b) - cal(a-1));64 }65 return 0;66 }
TOJ 2294 POJ 3286 How many 0's? 数位dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。