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
Input
Output
Sample Input
Sample Output
HINT
30%的數(shù)據(jù)中,a<=b<=10^6;
100%的數(shù)據(jù)中,a<=b<=10^12。
Source
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

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