题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4521
数据生成器：http://paste.ubuntu.com/23135878/
官方数据：http://pan.baidu.com/s/1hsqc4Va
这个题，瞄一眼就知道是数位DP
然而转移比较恶心，在考场上代码就写了两个小时
然而最后因为一个局部变量没有清零，结果wa得只剩一个点
为什么本机对拍不wa (╯‵□′)╯︵┻━┻
#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;
LL f[12][10][5][5],l,r;
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;
}
inline void prework(){
for (int i=0;i<=9;i++) if (i != 4 && i != 8) f[1][i][1][0] = 1;
f[1][4][1][1] = f[1][8][1][2] = 1;
for (int i=2;i<=11;i++) for (int j=0;j<=9;j++) {
if (j == 4) {
for (int p=0;p<=9;p++) if (p != j) for (int k=1;k<=2;k++) for (int ty=0;ty<=1;ty++)
f[i][j][1][1] += f[i-1][p][k][ty];
f[i][j][2][1] = f[i-1][4][1][1];
f[i][j][3][1] = f[i-1][4][2][1];
for (int p=0;p<=9;p++) for (int ty=0;ty<=1;ty++)
f[i][j][3][1] += f[i-1][p][3][ty];
} else if (j == 8) {
for (int p=0;p<=9;p++) if (p != j) for (int k=1;k<=2;k++) f[i][j][1][2] += f[i-1][p][k][0] + f[i-1][p][k][2];
f[i][j][2][2] = f[i-1][8][1][2];
f[i][j][3][2] = f[i-1][8][2][2];
for (int p=0;p<=9;p++) f[i][j][3][2] += f[i-1][p][3][0] + f[i-1][p][3][2];
} else for (int t=0;t<=2;t++) {
for (int p=0;p<=9;p++) if (p != j) for (int k=1;k<=2;k++) f[i][j][1][t] += f[i-1][p][k][t];
f[i][j][2][t] = f[i-1][j][1][t];
f[i][j][3][t] = f[i-1][j][2][t];
for (int p=0;p<=9;p++) f[i][j][3][t] += f[i-1][p][3][t];
}
}
}
inline bool judge(LL w) {
static int dig[15]; bool t1=0,t4=0,t8=0;
for (int i=1;i<=11;i++) dig[i] = w % 10, w /= 10;
for (int i=1;i<=11;i++) if (dig[i] == 4) t4 = 1;
for (int i=1;i<=11;i++) if (dig[i] == 8) t8 = 1;
for (int i=3;i<=11;i++) if (dig[i] == dig[i-1] && dig[i-1] == dig[i-2]) t1 = 1;
return t1 && !(t4 && t8);
}
inline LL cal(LL lim) {
LL ret = 0; bool t4=0, t8=0, CNT=0; static int dig[15];
for (int i=1;i<=11;i++) dig[i] = lim % 10, lim /= 10;
for (int i=1;i<dig[11];i++) for (int ty=0;ty<=2;ty++) ret += f[11][i][3][ty];
for (int k=10;k;k--) {
if (dig[k+1] == 4) t4 = 1; if (dig[k+1] == 8) t8 = 1;
if (t4 && t8) break;
int cnt = 1; for (int w=k+2;w<=11;w++) if (dig[w] != dig[k+1]) break; else cnt++;
if (cnt >= 3) CNT = 1;
for (int j=0,tmp=(k!=1);j<=dig[k]-tmp;j++)
if (CNT) for (int t=1;t<=3;t++) {
ret += f[k][j][t][0];
if (!t4) ret += f[k][j][t][2];
if (!t8) ret += f[k][j][t][1];
} else {
if (dig[k+1] == j) {
int stp = max(1,3-cnt);
for (int t=stp;t<=3;t++) {
ret += f[k][j][t][0];
if (!t4) ret += f[k][j][t][2];
if (!t8) ret += f[k][j][t][1];
}
} else {
ret += f[k][j][3][0];
if (!t4) ret += f[k][j][3][2];
if (!t8) ret += f[k][j][3][1];
}
}
}
return ret;
}
int main(){
prework();
l = read(); r = read();
cout<<cal(r)-cal(l)+judge(l);
return 0;
}
I love it whenever people come together and share
ideas. Great blog, keep it up!
Hey there! Someone in my Facebook group shared this website with
us so I came to look it over. I’m definitely loving the information. I’m book-marking
and will be tweeting this to my followers! Outstanding blog and outstanding design.
Great site you have here but I was curious about if you knew of any forums that cover the same topics discussed in this article?
I’d really love to be a part of group where I can get opinions from other experienced individuals that share the same interest.
If you have any recommendations, please let me know.
Thanks!
Wonderful web site. A lot of useful information here.
I’m sending it to some friends ans also sharing in delicious.
And of course, thank you in your effort!
Thanks for any other informative website. Where else may just I am getting that kind of information written in such a perfect way?
I have a challenge that I’m just now operating on, and I’ve
been at the glance out for such info.
excellent issues altogether, you simply won a new reader.
What may you suggest in regards to your put up that
you just made some days ago? Any positive?
Excellent post. I was checking continuously this blog and I am impressed!
Very helpful info specially the last part 🙂 I care for such info a lot.
I was seeking this particular information for a very long time.
Thank you and best of luck.
Hello there! I know this is kinda off topic but I’d figured I’d ask.
Would you be interested in trading links or maybe guest authoring a blog post or vice-versa?
My website discusses a lot of the same topics
as yours and I feel we could greatly benefit from each other.
If you’re interested feel free to shoot me an e-mail.
I look forward to hearing from you! Fantastic blog by the
way!
I blog frequently and I truly appreciate your information. This
great article has really peaked my interest.
I’m going to bookmark your site and keep checking for new details about
once a week. I subscribed to your RSS feed too.
Hello to all, how is all, I think every one
is getting more from this website, and your views
are nice in support of new people.
Excellent web site you have got here.. It’s difficult to find
good quality writing like yours nowadays. I honestly appreciate individuals like you!
Take care!!
Hi there! I know this is kinda off topic but
I was wondering which blog platform are you using for this site?
I’m getting tired of WordPress because I’ve had issues
with hackers and I’m looking at options for another platform.
I would be awesome if you could point me in the direction of a good platform.
Oh my goodness! Awesome article dude! Thank you so much, However I am going through issues with your
RSS. I don’t understand the reason why I am
unable to subscribe to it. Is there anyone else getting the
same RSS issues? Anyone that knows the solution will you kindly respond?
Thanx!!
continuously i used to read smaller posts that also clear their motive, and that is also happening with
this paragraph which I am reading here.
Do you mind if I quote a few of your posts as long as I provide
credit and sources back to your blog? My website is in the exact same niche as yours and my users would
genuinely benefit from some of the information you provide here.
Please let me know if this okay with you. Many thanks!
I’ve been browsing online greater than 3 hours lately, but I by no means discovered any interesting
article like yours. It’s lovely worth sufficient for me.
In my view, if all webmasters and bloggers made just right content material as you probably did, the net will probably be much more useful than ever before.
What i do not realize is actually how you are not really much more neatly-liked than you might be now.
You’re very intelligent. You realize thus significantly in the case of this matter, made me individually imagine it from numerous numerous
angles. Its like women and men are not involved unless it is one thing to accomplish with Girl gaga!
Your own stuffs outstanding. At all times care for it
up!
These are in fact enormous ideas in concerning blogging.
You have touched some good factors here. Any way keep
up wrinting.
Hi, i feel that i saw you visited my website thus i got here
to go back the want?.I am attempting to to
find things to enhance my web site!I guess its adequate
to make use of some of your ideas!! natalielise pof
Hi i am kavin, its my first occasion to commenting anywhere, when i read this article i thought
i could also make comment due to this brilliant piece of writing.
natalielise pof
For newest news you have to visit world-wide-web and on internet
I found this web site as a best web page for most recent updates.
Hi there, this weekend is pleasant designed for me, since this occasion i am reading this fantastic informative article here at my home.
Thanks for sharing your thoughts about pof.
Regards
I was curious if you ever thought of changing the page layout of
your blog? Its very well written; I love what youve got to say.
But maybe you could a little more in the way of content so people could connect with it better.
Youve got an awful lot of text for only having one or two pictures.
Maybe you could space it out better?
It’s going to be ending of mine day, except before end
I am reading this wonderful piece of writing to improve my know-how.
What’s up to every one, it’s truly a pleasant for me to visit this web page, it consists of important Information.
Hi, I do think your web site could possibly be having internet browser compatibility problems.
When I take a look at your web site in Safari, it
looks fine however when opening in Internet Explorer, it’s got some overlapping issues.
I merely wanted to give you a quick heads up!
Other than that, wonderful blog!
Everything is very open with a precise description of the issues.
It was definitely informative. Your site is very helpful. Thanks
for sharing!
Hi there, I enjoy reading all of your article. I wanted to write a
little comment to support you.
Awesome issues here. I’m very glad to peer your
post. Thank you a lot and I am taking a look ahead to touch
you. Will you please drop me a e-mail?
It’s appropriate time to make a few plans for the future and it is time to be happy.
I’ve read this publish and if I could I want to suggest you few
fascinating things or advice. Perhaps you can write next articles relating to this article.
I want to read more issues about it!
Hello mates, nice post and nice urging commented here,
I am truly enjoying by these.
Hurrah! After all I got a weblog from where I be able to truly
obtain valuable data regarding my study and knowledge.
certainly like your web-site but you need to test the spelling on quite a few of
your posts. Many of them are rife with spelling issues and I
find it very troublesome to tell the truth then again I’ll
definitely come again again.
Your style is really unique in comparison to other
people I have read stuff from. I appreciate you for posting when you’ve got the opportunity,
Guess I will just bookmark this web site.
Do you mind if I quote a couple of your articles as long as
I provide credit and sources back to your weblog? My website is
in the very same area of interest as yours and my visitors would certainly benefit from some of the information you present
here. Please let me know if this okay with you. Thanks!
I’m not sure exactly why but this blog is loading incredibly slow for me.
Is anyone else having this problem or is it
a issue on my end? I’ll check back later on and see if the problem
still exists.
Hello! Do you know if they make any plugins to help with SEO?
I’m trying to get my blog to rank for some targeted keywords but I’m not seeing
very good success. If you know of any please share. Kudos!
Tremendous issues here. I’m very glad to peer your post.
Thank you so much and I’m looking forward to contact you.
Will you please drop me a e-mail?
Useful info. Fortunate me I found your site unintentionally,
and I am stunned why this accident didn’t took place earlier!
I bookmarked it.
I think that what you said made a lot of sense. However, what about this?
what if you added a little information? I am not saying your
information is not good., however suppose you added something that makes people desire more?
I mean 【BZOJ 4521】[Cqoi2016] 手机号码 – Qizy's Database is
kinda vanilla. You might peek at Yahoo’s home page and note how they
write news titles to grab people to open the links.
You might try adding a video or a related pic or
two to get people excited about everything’ve got to say.
Just my opinion, it might make your posts a little livelier.
Thanks for another magnificent article. Where else could anybody get that type of information in such an ideal method of writing?
I have a presentation next week, and I am on the search for such info.
I am not certain the place you’re getting your information, but great topic.
I must spend some time learning more or working out more.
Thank you for great information I was in search of this info
for my mission.
I want to to thank you for this great read!! I certainly loved
every bit of it. I have you bookmarked to check out new things you post…
Spot on with this write-up, I actually believe this website
needs a great deal more attention. I’ll probably be returning
to see more, thanks for the advice!
In fact when someone doesn’t know then its up to other users that they will assist, so here
it happens.
hi!,I like your writing so much! proportion we keep in touch more about your article
on AOL? I require a specialist in this house to solve my problem.
May be that is you! Looking forward to peer you.
Im thankful for the blog post.Thanks Again. Fantastic.
Definitely believe that which you said. Your favorite reason appeared to be on the net the simplest thing to be aware of.
I say to you, I definitely get annoyed while people consider worries that they plainly do not know about.
You managed to hit the nail upon the top and also defined out the whole
thing without having side-effects , people could take a signal.
Will probably be back to get more. Thanks
Excellent way of describing, and pleasant paragraph to take facts about my presentation topic, which i am
going to deliver in university.
Superb, what a web site it is! This webpage gives helpful information to us, keep it up.
When some one searches for his required thing, thus he/she desires to be
available that in detail, therefore that thing is maintained over
here.
Excellent post. I used to be checking continuously
this blog and I am inspired! Extremely useful
information specially the final part 🙂 I
handle such information much. I used to be looking for this
certain info for a long time. Thank you and good luck.
Thanks for your marvelous posting! I actually enjoyed reading
it, you might be a great author.I will ensure that I bookmark your blog and
will often come back later in life. I want to encourage you continue your great job, have a nice holiday weekend!
Fine way of describing, and nice paragraph to get facts regarding my presentation topic, which i am going to
deliver in institution of higher education.
Hi, Neat post. There’s a problem together with your site in web explorer, might test this?
IE nonetheless is the market chief and a good component of other folks will miss your magnificent writing because of this
problem.
Hi, I do believe this is a great blog. I stumbledupon it ;
) I am going to return once again since i have book-marked it.
Money and freedom is the greatest way to change, may you be
rich and continue to guide others.
Hello, this weekend is nice designed for me, as this moment i am reading this wonderful educational article here
at my home.
Greate pieces. Keep posting such kind of info on your site.
Im really impressed by your blog.
Hi there, You’ve performed an incredible job.
I’ll definitely digg it and in my opinion recommend to my friends.
I am confident they’ll be benefited from this website.
You really make it appear so easy along with your presentation but I in finding this matter
to be actually something which I believe I’d
by no means understand. It kind of feels too complicated and extremely
wide for me. I’m taking a look ahead to your subsequent post, I’ll try to get the dangle of it!
You made some decent points there. I checked on the web
to find out more about the issue and found most individuals will go along with
your views on this web site.
This piece of writing is genuinely a pleasant one it helps new web people,
who are wishing for blogging.
Right away I am going to do my breakfast, afterward having my breakfast coming over
again to read further news.
Great blog here! Also your site loads up very fast! What web host are you
using? Can I get your affiliate link to your host? I wish my site loaded up as fast
as yours lol
It’s remarkable to pay a visit this site and
reading the views of all friends about this
article, while I am also eager of getting familiarity.
Thanks in favor of sharing such a nice thought, post is good, thats why i have read it completely
Wohh exactly what I was looking for, thankyou for putting up.
Today, I went to the beach front with my kids. I found a sea shell and gave it to
my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put
the shell to her ear and screamed. There was a hermit crab inside and it
pinched her ear. She never wants to go back!
LoL I know this is totally off topic but I had to
tell someone!
I’m extremely pleased to discover this great site.
I want to to thank you for ones time for this fantastic read!!
I definitely really liked every bit of it and I have
you saved as a favorite to check out new stuff on your website.
It’s difficult to find educated people on this topic,
however, you sound like you know what you’re talking
about! Thanks
What’s up to all, the contents present at this web site are genuinely awesome for people knowledge, well, keep up
the nice work fellows.
Highly energetic post, I enjoyed that a lot. Will there be a part 2?
Good post. I learn something totally new and challenging on websites I stumbleupon everyday.
It’s always helpful to read content from other writers and use a little something from other sites.
Hey very nice blog!
Can I simply say what a comfort to find a person that truly knows what
they are discussing on the web. You certainly realize how to bring an issue
to light and make it important. A lot more people really need to read
this and understand this side of your story.
I was surprised you aren’t more popular since you surely have the
gift.
Hey there! Quick question that’s completely off
topic. Do you know how to make your site mobile friendly?
My site looks weird when browsing from my iphone 4.
I’m trying to find a theme or plugin that might be able to correct this issue.
If you have any suggestions, please share. Thank you!
Thanks for the auspicious writeup. It if truth be told was once a entertainment account it.
Look complex to more brought agreeable from you! However, how can we keep in touch?
When I initially commented I clicked the “Notify me when new comments are added” checkbox and now each time a comment is
added I get three emails with the same comment. Is there any way you can remove me from that service?
Thanks a lot!
Wow, this piece of writing is nice, my younger sister is analyzing
these kinds of things, thus I am going to let know her.
I’m gone to convey my little brother, that he should also pay a quick visit this webpage on regular basis
to obtain updated from newest reports.
Hi, I think your blog might be having browser compatibility issues.
When I look at your blog site in Safari, it looks fine but when opening in Internet Explorer, it has some
overlapping. I just wanted to give you a quick heads up!
Other then that, terrific blog!
There are definitely loads of details like that to take into consideration. That is a great level to convey up. I provide the thoughts above as basic inspiration however clearly there are questions like the one you convey up where crucial thing shall be working in honest good faith. I don?t know if greatest practices have emerged around issues like that, however I’m certain that your job is clearly identified as a fair game. Each boys and girls really feel the affect of just a second’s pleasure, for the rest of their lives.
Thanks a lot for the blog post.Thanks Again. Much obliged.
Thanks a lot for the blog. Really Cool.