题目传送门:http://codeforces.com/contest/55/problem/D
官方题解:http://codeforces.com/blog/entry/1109
中文题面:number_dp_by_zky
之前做数位dp的题目,一直强调数位间的独立性
然而现在看来,不独立也是可以上数位dp的
题解直接看上面给的“中文题面”里的题解吧,zky的题解真的是超级棒(๑•̀ㅂ•́)و✧
我来说一说代码实现的三种方式:
1)像之前的代码一样,先预处理,然后查询的时候在数组上搞一搞
优点:对于多组询问特别好用
缺点:因为是预处理,所以对于有些题目可能很麻烦,甚至不能预处理
2)对于每一次询问单独dp,记录是否达到上限
优点:代码好写(不用于处理,直接写一个dp就成)
缺点:多组询问没法处理
3)对于每一次询问DFS,如果这一位没有受到任何限制就记忆化
这种方法是我在看这位神犇的代码的时候看到的:http://codeforces.com/contest/55/submission/3692033
优点:代码更好写,且对于多组询问相对友好(仔细想一想,他的查询次数应该不会劣于方法1?)
缺点:如果位数特别大(什么1e5,1e6之类的),则效果可能不太好
总的来说,我似乎爱上了第三种写法 = ̄ω ̄=
以后数位dp的题应该是首选第三种吧!
#include<bits/stdc++.h> #define LL long long using namespace std; int MOD[]={1,1,2,3,4,5,6,7,8,9,10,12,14,15,18,20,21,24,28,30,35,36,40,42,45,56,60,63,70,72,84,90,105,120,126,140,168,180,210,252,280,315,360,420,504,630,840,1260,2520}; int pos[2530],lcm[50][50],sta[20]; LL f[20][50][2530]; LL GCD(LL a, LL b) {return b?GCD(b,a%b):a;} LL LCM(LL a, LL b) {return a/GCD(a,b)*b;} LL DFS(int t, int lm, int mod, bool top) { if (t == 0) { return !(mod % MOD[lm]); } else if (~f[t][lm][mod] && !top) { return f[t][lm][mod]; } else { LL ret = 0; for (int i=0,ty=(top>0?sta[t]:9),tmp;i<=ty;i++) { tmp = lcm[lm][i]; ret += DFS(t-1,tmp,(mod*10+i)%2520,top&&i==sta[t]); } return top?ret:f[t][lm][mod] = ret; } } inline LL cal(LL lim) { int cnt = 0; while (lim) { sta[++cnt] = lim % 10; lim /= 10; } return DFS(cnt,1,0,1); } inline LL read(){ char c=getchar(); LL ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } int main(){ memset(f,-1,sizeof(f)); for (int i=1;i<=48;i++) { pos[MOD[i]] = i; } for (int i=0;i<=48;i++) { for (int j=0;j<=48;j++) { lcm[i][j] = pos[LCM(MOD[i],MOD[j])]; } } for (int T=read();T;--T) { LL l = read(), r = read(); printf("%I64d\n",cal(r)-cal(l-1)); } return 0; }
This piece of writing gives clear idea in favor of the new people of blogging, that
truly how to do running a blog.
I’ll right away grasp your rss as I can’t to find your email subscription link
or newsletter service. Do you have any? Please let me recognize in order that I could
subscribe. Thanks.
It’s remarkable to pay a visit this website and reading the views of
all colleagues on the topic of this piece of writing, while I am also keen of getting
experience.
Nice post. I learn something new and challenging on websites I stumbleupon on a daily basis.
It’s always exciting to read through content from other
authors and practice something from their web sites.
Very good article! We are linking to this particularly great content on our site.
Keep up the great writing.
Why users still use to read news papers when in this technological globe all is accessible on net?
I really like it when folks come together and share ideas.
Great site, continue the good work!
Hurrah, that’s what I was seeking for, what a stuff! existing here at this website, thanks
admin of this site.
Wow that was strange. I just wrote an extremely long comment but after I clicked submit my comment didn’t appear.
Grrrr… well I’m not writing all that over again. Anyhow, just wanted to say great blog!
I used to be able to find good information from your blog posts.
I loved as much as you’ll receive carried out right here.
The sketch is attractive, your authored material stylish.
nonetheless, you command get got an shakiness over that
you wish be delivering the following. unwell unquestionably
come more formerly again as exactly the same nearly a
lot often inside case you shield this increase.
Hi there fantastic blog! Does running a blog similar to this take
a massive amount work? I’ve absolutely no expertise in computer
programming but I had been hoping to start my own blog soon. Anyways, should you have any suggestions or techniques for new blog owners please share.
I know this is off subject but I just needed to ask.
Many thanks!
Having read this I believed it was rather informative.
I appreciate you taking the time and effort to put this short article together.
I once again find myself personally spending
way too much time both reading and leaving comments.
But so what, it was still worth it!
Very descriptive article, I liked that a lot. Will there be a
part 2?
What i do not understood is in truth how you’re now not really much more well-appreciated than you
may be right now. You’re very intelligent.
You recognize therefore considerably on the subject
of this matter, made me in my opinion imagine it from numerous various angles.
Its like women and men don’t seem to be interested until it is
something to do with Woman gaga! Your personal stuffs outstanding.
At all times deal with it up!
You’ve made some good points there. I looked on the net to learn more about the issue and found most individuals will go along with your views on this website.
My husband and i felt quite happy that John could finish off his studies from the precious recommendations he had through your web page. It is now and again perplexing just to be releasing secrets most people might have been making money from. And now we recognize we now have the blog owner to be grateful to for that. These illustrations you made, the straightforward site menu, the friendships you can assist to instill – it’s mostly astounding, and it is facilitating our son in addition to our family do think the subject is satisfying, and that is pretty indispensable. Many thanks for the whole thing!
Hi there, I log on to your blog on a regular basis.
Your writing style is witty, keep it up!
Hello just wanted to give you a quick heads up. The words in your content seem to be running off the screen in Internet explorer.
I’m not sure if this is a format issue or something to do with internet browser compatibility but I figured I’d post to let you know.
The style and design look great though! Hope you get the problem fixed soon. Thanks
What’s up it’s me, I am also visiting this web site daily, this
website is actually good and the visitors are really sharing pleasant thoughts.
Hi my loved one! I want to say that this post is awesome, nice written and
come with almost all important infos. I would like to peer extra posts like this .
Hi, i think that i saw you visited my website so i came to “return the favor”.I’m trying to find things to improve my website!I suppose its ok to use some of your ideas!!
Good web site you have here.. It’s difficult to find good quality writing
like yours these days. I honestly appreciate people like you!
Take care!!
Thank you a lot for sharing this with all of us you really recognise what you are speaking approximately!
Bookmarked. Please also talk over with my website =). We could
have a link alternate contract among us
Very nice post. I just stumbled upon your blog and wanted to mention that I
have really enjoyed browsing your blog posts.
After all I’ll be subscribing to your rss feed and I hope
you write again soon!
Hey! I know this is kind of off topic but I was wondering which
blog platform are you using for this website? I’m getting sick
and tired of WordPress because I’ve had problems with hackers and I’m looking at options for another platform.
I would be fantastic if you could point me in the direction of a good platform.
great issues altogether, you just gained a new reader.
What might you recommend about your submit that you simply made some days in the past?
Any positive?
This is really interesting, You are a very skilled blogger. I’ve joined your rss feed and look forward to seeking more of your great post. Also, I’ve shared your website in my social networks!