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

一開始我用數位統計搞
想按照這種方法搞的
http://www.shnenglu.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
搜索
最新評論

|
|