 /**//*
求[a,b]中0-9各數(shù)字出現(xiàn)的次數(shù) <=10^12

一開始我用數(shù)位統(tǒng)計(jì)搞
想按照這種方法搞的
http://m.shnenglu.com/Yuan/archive/2011/01/25/139299.html
搞了好久搞不出,逐漸發(fā)現(xiàn)dfs型的寫法,狀態(tài)一般需要(pos,pre),需要壓縮前綴為pre
我定義(pos, preCnt)
preCnt是表示前綴中有多少個(gè)數(shù)字跟當(dāng)前要檢查的數(shù)字相同,不行的,不能正確表示出前綴!
如12,21記錄1出現(xiàn)的個(gè)數(shù)都是一樣的,但是結(jié)果不同
會(huì)被if(dp[pos][pre] != -1)
return dp[pos][pre]
返回錯(cuò)誤的結(jié)果

這個(gè)前綴應(yīng)該具有共用性,也就說不同前綴壓縮得到的結(jié)果有些要一樣,這樣才能記憶化嘛,重復(fù)利用!!
但這題,前綴如果是直接用前面的數(shù)字來表示的話,很多,肯定時(shí)空都不行
所以,搞數(shù)位統(tǒng)計(jì),需要記錄前綴(數(shù)位統(tǒng)計(jì)不記錄應(yīng)該前綴不行吧)
同時(shí)前綴必須是能區(qū)分(不會(huì)返回錯(cuò)誤結(jié)果)的,還要可共用(用來減少運(yùn)算,提高速度)
這道題的正確做法,換做以前,可能會(huì)想到,但是現(xiàn)在感覺思維定勢(shì)了T_T
參考http://hi.baidu.com/736551725/blog/item/8ba4408e4fb74206b21bbae4.html
觀察下表
000
001
.
998
999
對(duì)于長度為3的,總共有3*10^3個(gè)數(shù)字,每個(gè)數(shù)字出現(xiàn)的概率一樣,所以每個(gè)數(shù)字出現(xiàn)的次數(shù)為3*10^3/10
也即寬度為n的表,每個(gè)數(shù)字出現(xiàn)的次數(shù)為n*10^(n-1)
對(duì)于前綴0,要去掉,對(duì)于寬度為n的表,前綴0的個(gè)數(shù)為11..1個(gè)(表的左上角那些0,包括000那個(gè))

有了上面的觀察,就逐位統(tǒng)計(jì)下,就能得到[1,n]各個(gè)數(shù)字出現(xiàn)的次數(shù)了
*/
#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
搜索
最新評(píng)論

|
|