#include#include#include#include" />

亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

【BZOJ】1833: [ZJOI2010]count 數(shù)字計數(shù)(數(shù)位

系統(tǒng) 1864 0

http://www.lydsy.com/JudgeOnline/problem.php?id=1833

數(shù)位dp什么的最惡心了。

dfs時注意考慮兩種邊界,一種是此時正好在這個數(shù)上,那么答案應(yīng)該加的是后邊的數(shù)+1+dfs

否則就加10^(x-1)+dfs;這兩個是顯然的。自己多想想就懂了

具體看代碼:

      #include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

#include <queue>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << (#x) << " = " << (x) << endl

#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }

#define printarr1(a, b) for1(_, 1, b) cout << a[_] << '\t'; cout << endl

inline const ll getint() { ll r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }



ll f[100], c[100], a[100], p[100];



ll dfs(int x, int dig, int front, int line) {

	if(!x) return 0;

	if(!front && !line && f[x]!=-1) return f[x];

	ll last=(line?a[x]:9), tot=0;

	for1(i, 0, last) {

		if(front && i==0) tot+=dfs(x-1, dig, 1, line&&i==last);

		else if(i==dig) {

			if(i==last && line) tot+=c[x-1]+1+dfs(x-1, dig, 0, line&&i==last); //正好在這個數(shù)上

			else tot+=p[x-1]+dfs(x-1, dig, 0, line&&i==last);

		}

		else tot+=dfs(x-1, dig, 0, line&&i==last);

	}

	if(!front && !line) f[x]=tot;

	return tot;

}

ll getans(ll x, int dig) {

	CC(f, -1);

	ll t=x; int len=0;

	while(t) a[++len]=t%10, t/=10, c[len]=c[len-1]+a[len]*p[len-1];

	return dfs(len, dig, 1, 1);

}

int main() {

	ll a=getint(), b=getint();

	p[0]=1; for1(i, 1, 15) p[i]=p[i-1]*10;

	rep(i, 9) printf("%lld ", getans(b, i)-getans(a-1, i));

	printf("%lld\n", getans(b, 9)-getans(a-1, 9));

	return 0;

}


    

?

?


?

?

Description

給定兩個正整數(shù)a和b,求在[a,b]中的所有整數(shù)中,每個數(shù)碼(digit)各出現(xiàn)了多少次。

Input

輸入文件中僅包含一行兩個整數(shù)a、b,含義如上所述。

Output

輸出文件中包含一行10個整數(shù),分別表示0-9在[a,b]中出現(xiàn)了多少次。

Sample Input

1 99

Sample Output

9 20 20 20 20 20 20 20 20 20

HINT

30%的數(shù)據(jù)中,a<=b<=10^6;
100%的數(shù)據(jù)中,a<=b<=10^12。

Source

【BZOJ】1833: [ZJOI2010]count 數(shù)字計數(shù)(數(shù)位dp)


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯(lián)系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發(fā)表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 波多野结衣绝顶大高潮 | 夜间福利影院 | 欧洲成人免费视频 | 天天碰夜夜 | 久久99精品久久久久久久野外 | 亚洲香蕉毛片久久网站老妇人 | 亚洲精品一区二区三区四区手机版 | 精品免费福利视频 | 国产一区三区二区中文在线 | 欧美国产亚洲精品高清不卡 | 精品久久久久久中文字幕专区 | 亚洲综合极品香蕉久久网 | 亚洲欧美一区二区久久 | 欧美精品在线播放 | 亚洲欧美成人综合久久久 | 久久日韩 | 免费涩涩视频 | 国产亚洲在线观看 | 日本一级一片免费 | 日韩亚洲第一页 | 欧美日韩在线成人 | 国产五月色婷婷六月丁香视频 | 欧美日韩中文国产一区 | 亚洲高清资源在线观看 | 亚洲一二三区在线观看 | 亚洲精品视频久久久 | 久99久热只有精品国产99 | 国语精品91自产拍在线观看二区 | 一级骚片超级骚在线观看 | 亚洲香蕉国产高清在线播放 | 91无限资源 | 日本不卡高清免费v日本 | 中文字幕国产在线 | 亚洲精品乱码久久久久久蜜桃欧美 | 日韩欧美在线观看视频一区二区 | 毛片短视频 | 成人毛片在线视频 | 亚洲综合网址 | 精品国产高清a毛片无毒不卡 | 日本aa视频 | 亚洲一区二区三区国产精品 |