题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=3709
中文题面：http://blog.csdn.net/to_be_better/article/details/50731499
就是枚举一下平衡点，然后dp一下
另外……
我似乎真的爱上这种递归的写法了…..
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int sta[20];
LL f[20][20][1500];
inline LL read(){
char c=getchar(); LL ret=0;
while (c<'0'||c>'9') c=getchar();
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret;
}
LL DFS(int t, int crt, int val, bool ruf) {
if (val < 0) return 0;
else if (!t) {
return !val;
} else if (~f[t][crt][val] && !ruf) {
return f[t][crt][val];
} else {
LL ret = 0;
for (int i=0,lim=ruf?sta[t]:9;i<=lim;i++) {
ret += DFS(t-1,crt,val+(t-crt)*i,ruf&&i==sta[t]);
}
return ruf? ret: f[t][crt][val] = ret;
}
}
inline LL cal(LL lim) {
int cnt = 0;
while (lim) {
sta[++cnt] = lim % 10;
lim /= 10;
}
LL ret = 0;
for (int i=1;i<=cnt;i++) {
ret += DFS(cnt,i,0,1);
}
return ret - cnt + 1;
}
int main(){
memset(f,-1,sizeof(f));
for (int T=read();T;--T) {
LL l = read(), r = read();
printf("%I64d\n",cal(r)-((l>0)?cal(l-1):0));
}
return 0;
}
It’s going to be finish of mine day, however before end I am reading this impressive piece
of writing to increase my knowledge.
When someone writes an post he/she maintains the thought of a user in his/her brain that how a user can understand it.
So that’s why this piece of writing is perfect.
Thanks!
Great info. Lucky me I recently found your website
by chance (stumbleupon). I’ve saved it for later!
I do agree with all of the ideas you’ve presented on your post.
They’re very convincing and can certainly work.
Nonetheless, the posts are too brief for newbies.
May just you please lengthen them a bit from next time?
Thank you for the post.
Simply desire to say your article is as astounding.
The clarity for your submit is just cool and i can think you’re a professional in this subject.
Fine together with your permission allow me to grasp
your RSS feed to stay up to date with drawing close post.
Thank you 1,000,000 and please continue the enjoyable work.
I like the valuable information you provide in your articles.
I will bookmark your blog and check again here frequently.
I am quite certain I’ll learn many new stuff right here!
Best of luck for the next!
Hi there, everything is going sound here and ofcourse every one is sharing data,
that’s truly excellent, keep up writing.
Thanks for the marvelous posting! I truly enjoyed reading it, you
happen to be a great author. I will be sure
to bookmark your blog and definitely will come back from
now on. I want to encourage you continue your great posts, have a nice afternoon!
Wonderful blog! I found it while surfing around on Yahoo
News. Do you have any suggestions on how to get listed in Yahoo News?
I’ve been trying for a while but I never seem to get there!
Thanks
Hello there! Would you mind if I share your blog with my myspace
group? There’s a lot of people that I think would really
enjoy your content. Please let me know. Many thanks
Magnificent site. Plenty of helpful info here. I’m sending it to several buddies ans also sharing in delicious.
And obviously, thanks for your sweat!
I think this is one of the most important info for
me. And i am glad reading your article. But wanna remark on some general things, The website
style is great, the articles is really great : D. Good job,
cheers
I’d perpetually want to be update on new posts on this website , saved to favorites! .
Woah! I’m really enjoying the template/theme of this site.
It’s simple, yet effective. A lot of times it’s very difficult to get that “perfect balance” between user friendliness and visual appeal.
I must say you have done a fantastic job with this. Additionally,
the blog loads very quick for me on Chrome. Outstanding Blog!
Link exchange is nothing else however it is simply placing the
other person’s webpage link on your page at appropriate place and other
person will also do same in favor of you.
Valuable info. Lucky me I found your web site by accident, and I am shocked why this accident did not happened earlier! I bookmarked it.