 /**//*
求[a,b]中0-9各数字出现的次数 <=10^12

一开始我用数位统计搞
想按照这种方法搞的
http://www.cppblog.com/Yuan/archive/2011/01/25/139299.html
搞了好久搞不出,逐渐发现dfs型的写法,状态一般需要(pos,pre),需要压缩前缀为pre
我定义(pos, preCnt)
preCnt是表示前缀中有多少个数字跟当前要检查的数字相同,不行的,不能正确表示出前缀!
如12,21记录1出现的个数都是一样的,但是结果不同
会被if(dp[pos][pre] != -1)
return dp[pos][pre]
返回错误的结果

这个前缀应该具有共用性,也就说不同前缀压缩得到的结果有些要一样,这样才能记忆化嘛,重复利用!!
但这题,前缀如果是直接用前面的数字来表示的话,很多,肯定时空都不行
所以,搞数位统计,需要记录前缀(数位统计不记录应该前缀不行吧)
同时前缀必须是能区分(不会返回错误结果)的,还要可共用(用来减少运算,提高速度)
这道题的正确做法,换做以前,可能会想到,但是现在感觉思维定势了T_T
参考http://hi.baidu.com/736551725/blog/item/8ba4408e4fb74206b21bbae4.html
观察下表
000
001
.
998
999
对于长度为3的,总共有3*10^3个数字,每个数字出现的概率一样,所以每个数字出现的次数为3*10^3/10
也即宽度为n的表,每个数字出现的次数为n*10^(n-1)
对于前缀0,要去掉,对于宽度为n的表,前缀0的个数为11..1个(表的左上角那些0,包括000那个)

有了上面的观察,就逐位统计下,就能得到[1,n]各个数字出现的次数了
*/
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<cmath>
#include<string>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<set>
#include<list>
#include<numeric>
#include<cassert>
#include<ctime>

using namespace std;

 void gao(__int64 n, __int64 cnt[]) {//count all digits in [1,n] , not [0,n]
 /**//*
check a form like this .
000
001
.
010
.
099
100
101 ------N
*/
int digit[20], num = 0;
__int64 p = 1, N = n, sub = 0;
 do {
digit[num++] = n % 10;
n /= 10;
p *= 10;
}while(n > 0);
 for(int i = num - 1,j ; i >= 0 ; i --) {
p /= 10;
 for(j = 0 ; j < digit[i] ; j++) {
cnt[j] += p;
 for(int k = 0; k < 10 ; k++) {
cnt[k] += p/10*i;
}
}
N %= p;
cnt[j] += N+1;//要加1
sub += p;
}
cnt[0] -= sub;
}

int main()
  {
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
#endif

 for(__int64 left, right ; cin >> left >> right; ) {
 __int64 cnt[10] = {0};
gao(left-1, cnt);
 for(int i = 0 ; i < 10 ; i++) {
cnt[i] = -cnt[i];
}
gao(right, cnt);
 for(int i = 0; i < 10 ; i++) {
 if(i) {
putchar(' ');
}
printf("%I64d", cnt[i]);
}
puts("");
}
return 0;
}
|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|