/**//* 求[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
搜索
最新评论
|
|