题目传送门：https://www.codechef.com/problems/FAVNUM
中文题面：number_dp_by_zky
这个题目还是挺好玩的！
数位DP配上AC自动机！别有一番风味！
然而这个傻Ⅹ的AC自动机写炸了
调试了3个小时！ (╯‵□′)╯︵┻━┻
#include<bits/stdc++.h>
#define LL long long
using namespace std;
char pat[20];
namespace AC_Automaton{
#define AC AC_Automaton
LL f[20][2000][2];
int ch[2000][10],tag[2000],cnt,fail[2000],sta[20];
queue<int> que;
inline void insert(char *s){
int n = strlen(s+1), w = 0;
for (int i=1,c;i<=n;i++) {
c = s[i] - '0';
if (!ch[w]) {
ch[w] = ++cnt;
}
w = ch[w];
}
tag[w] = 1;
}
inline void Build(){
for (int i=0;i<=9;i++) if (ch[0][i]) {
que.push(ch[0][i]);
}
while (!que.empty()) {
int w = que.front(); que.pop();
for (int c=0;c<=9;c++) if (ch[w]) {
int nv = ch[w], pv = fail[w];
while (pv && !ch[pv]) pv = fail[pv];
fail[nv] = ch[pv];
tag[nv] |= tag[fail[nv]];
que.push(nv);
} else {
ch[w] = ch[fail[w]];
}
}
}
LL DFS(int t, int w, bool lim, bool leg) {
if (!t) {
return leg;
} else if (!lim && ~f[t][w][leg]) {
return f[t][w][leg];
} else {
LL ret = 0;
for (int i=0,ty=lim?sta[t]:9;i<=ty;i++) {
ret += DFS(t-1, ch[w][i], lim&&i==sta[t], leg|tag[ch[w][i]]);
}
return lim? ret: f[t][w][leg] = ret;
}
}
inline LL query(LL lim) {
int cnt = 0;
while (lim) {
sta[++cnt] = lim % 10;
lim /= 10;
}
memset(f,-1,sizeof(f));
return DFS(cnt,0,1,0);
}
};
int main(){
LL L,R,k,n,bas,w,stp;
cin>>L>>R>>k>>n;
for (int i=1;i<=n;i++) {
scanf("%s",pat+1);
AC::insert(pat);
}
AC::Build();
k += AC::query(L - 1);
if (AC::query(R) < k) {
puts("no such number");
exit(0);
}
stp = 1; w = L - 1;
while (stp < (R - L + 1)) stp <<= 1;
while (stp) {
if (AC::query(w + stp) < k) {
w += stp;
}
stp >>= 1;
}
printf("%lld\n",w+1);
return 0;
}
Valuable info. Lucky me I found your site unintentionally, and I’m stunned why this coincidence didn’t
took place earlier! I bookmarked it.
I every time spent my half an hour to read this webpage’s content everyday
along with a cup of coffee.
My spouse and I stumbled over here by a different
website and thought I should check things
out. I like what I see so now i am following you. Look forward to looking over your web page
yet again.
I am sure this piece of writing has touched all the internet visitors, its really
really fastidious article on building up new website.
My brother suggested I might like this blog. He was
totally right. This post actually made my day. You cann’t imagine just how
much time I had spent for this information! Thanks!
Hey There. I found your blog using msn. This is an extremely well written article.
I will make sure to bookmark it and return to read more of your useful
info. Thanks for the post. I will definitely comeback.
Nice weblog right here! Additionally your website quite a bit up very fast!
What host are you the use of? Can I get your affiliate hyperlink in your
host? I wish my website loaded up as quickly as yours lol
Howdy! I know this is kinda off topic but I was wondering if you
knew where I could locate a captcha plugin for my comment form?
I’m using the same blog platform as yours and I’m
having problems finding one? Thanks a lot!
What’s Taking place i’m new to this, I stumbled upon this I’ve discovered It positively helpful and it
has aided me out loads. I hope to contribute & assist different users like its aided
me. Great job.
Greetings from Colorado! I’m bored at work so I decided
to browse your site on my iphone during lunch break.
I love the info you provide here and can’t wait to take a
look when I get home. I’m shocked at how quick your blog
loaded on my phone .. I’m not even using WIFI, just 3G ..
Anyways, wonderful site!
Hi I am so grateful I found your webpage, I really found you by
error, while I was searching on Digg for something else, Nonetheless I am here now and would just like to
say thank you for a incredible post and a all round thrilling blog (I also love the theme/design),
I don’t have time to go through it all
at the moment but I have book-marked it and also added in your RSS feeds, so when I have time I will be back
to read more, Please do keep up the great work.
Hello, I think your website might be having internet
browser compatibility issues. When I take a look at your site in Safari, it looks fine however, when opening in I.E., it’s got some overlapping issues.
I simply wanted to give you a quick heads up! Other than that, great
blog!
It’s the best time to make a few plans for the future
and it is time to be happy. I have learn this put up and
if I could I want to suggest you some interesting things or advice.
Perhaps you could write next articles regarding this article.
I desire to read more issues approximately it!
Appreciate this post. Let me try it out.
I got this site from my pal who told me regarding this web site
and at the moment this time I am visiting this web page and reading very informative articles here.
Outstanding post however , I was wondering if you could write a
litte more on this subject? I’d be very thankful if you could elaborate a little
bit more. Many thanks!
This paragraph is really a good one it assists new web
visitors, who are wishing in favor of blogging.
I’m more than happy to uncover this site. I need to to thank you for your time just for this fantastic read!!
I definitely appreciated every part of it and I have you book-marked
to see new stuff in your blog.
I read this article fully about the resemblance of
most up-to-date and previous technologies, it’s amazing article.
Its such as you read my mind! You seem to know a lot approximately this,
like you wrote the ebook in it or something. I feel that you just can do with a
few percent to force the message home a bit, but instead of that,
that is excellent blog. An excellent read.
I will definitely be back. natalielise pof
It’s hard to come by educated people for this subject,
but you sound like you know what you’re talking about! Thanks
natalielise plenty of fish
Great article.
Great goods from you, man. I’ve understand your stuff previous to and
you’re just extremely great. I actually like what you have acquired here, really like what you are saying
and the way in which you say it. You make it enjoyable and you still care for to keep it sensible.
I can not wait to read much more from you. This is really a
wonderful web site.
With havin so much written content do you ever run into any problems of plagorism or copyright
infringement? My website has a lot of completely unique content I’ve either authored myself
or outsourced but it appears a lot of it is popping
it up all over the web without my authorization. Do you
know any ways to help prevent content from being stolen? I’d really
appreciate it.
This article is really a good one it helps new net viewers, who are wishing in favor of blogging.
Thanks for sharing your thoughts. I really
appreciate your efforts and I am waiting for
your further post thank you once again. pof natalielise
This is a topic that’s close to my heart… Best wishes!
Exactly where are your contact details though?
I think that what you typed was actually very reasonable.
However, think about this, what if you composed a catchier title?
I ain’t saying your content isn’t good., however suppose you added a title that
makes people desire more? I mean 【CodeChef FAVNUM】Favourite Numbers – Qizy's Database is a little plain. You ought to glance at Yahoo’s front page and note how they write post headlines to grab people to click.
You might try adding a video or a related pic or two to grab people excited about what you’ve written. In my opinion, it could
bring your posts a little bit more interesting.
Hello there, just became alert to your blog through
Google, and found that it is truly informative.
I’m going to watch out for brussels. I will be grateful if you continue this in future.
Lots of people will be benefited from your writing. Cheers!
Aw, this was an exceptionally good post. Taking the
time and actual effort to create a really good
article… but what can I say… I procrastinate a whole lot and never manage to get anything done.
Its not my first time to pay a quick visit this site,
i am visiting this site dailly and take nice data from here every
day.
Woah! I’m really enjoying the template/theme of this blog.
It’s simple, yet effective. A lot of times it’s tough to get that
“perfect balance” between superb usability and appearance.
I must say you’ve done a great job with this. In addition, the blog loads very quick for me on Safari.
Excellent Blog!
Hello would you mind stating which blog platform you’re
using? I’m looking to start my own blog in the near future but I’m
having a tough time deciding between BlogEngine/Wordpress/B2evolution and Drupal.
The reason I ask is because your design seems different then most
blogs and I’m looking for something unique.
P.S Sorry for being off-topic but I had to ask!
Genuinely when someone doesn’t understand after that its
up to other visitors that they will assist, so here it occurs.
I was suggested this web site through my cousin. I am not certain whether this submit is written through him as no one else realize
such precise approximately my difficulty. You are wonderful!
Thank you!
I like the valuable information you provide in your articles.
I will bookmark your weblog and check again here regularly.
I’m quite certain I’ll learn plenty of new stuff right here!
Best of luck for the next!
Do you mind if I quote a few of your posts as long as I provide credit and sources back to your webpage?
My website is in the very same niche as yours and my visitors would certainly benefit
from some of the information you provide here.
Please let me know if this ok with you. Many thanks!
Thanks , I have just been looking for info approximately
this subject for a while and yours is the best I have found out so far.
However, what about the conclusion? Are you positive concerning the supply?
Hey I am so grateful I found your web site, I really found
you by error, while I was browsing on Digg for something else, Nonetheless I am here now and would just like to say thank you for a
remarkable post and a all round entertaining blog (I
also love the theme/design), I don’t have time
to browse it all at the moment but I have bookmarked it and also added in your RSS feeds, so when I
have time I will be back to read a lot more, Please do keep up the
awesome work.
Greetings! Very helpful advice within this article!
It is the little changes that produce the greatest changes.
Many thanks for sharing!
Appreciate this post. Let me try it out.
I every time spent my half an hour to read this website’s articles all
the time along with a mug of coffee.
Hi there! This is kind of off topic but I need
some guidance from an established blog. Is it very hard to set up your own blog?
I’m not very techincal but I can figure things out pretty
quick. I’m thinking about making my own but I’m not sure where to
begin. Do you have any tips or suggestions?
With thanks
I pay a quick visit each day some sites and
sites to read articles or reviews, except this blog presents quality
based content.
After checking out a few of the blog posts on your site, I seriously appreciate your
way of writing a blog. I book marked it to my bookmark site list and will be checking back in the near future.
Please check out my web site as well and let me know your
opinion.
Someone essentially lend a hand to make seriously posts I would state.
That is the first time I frequented your web page and thus far?
I surprised with the analysis you made to create this actual post incredible.
Magnificent activity!
Link exchange is nothing else however it is simply placing the
other person’s blog link on your page at appropriate place and other
person will also do same in favor of you.
Hi i am kavin, its my first time to commenting anyplace,
when i read this paragraph i thought i could also make comment due to this
sensible paragraph.
Hi would you mind letting me know which web host you’re using?
I’ve loaded your blog in 3 completely different web
browsers and I must say this blog loads a lot
faster then most. Can you recommend a good hosting provider at a
honest price? Cheers, I appreciate it!
My brother suggested I might like this website.
He was totally right. This post truly made my day.
You can not imagine just how much time I had spent for
this info! Thanks!
I think this is one of the most important information for me.
And i’m glad reading your article. But should remark on some general things, The site style is great, the articles is really
nice : D. Good job, cheers
I visited several sites except the audio feature for audio songs
existing at this site is genuinely fabulous.
We are a group of volunteers and starting a new
scheme in our community. Your web site offered
us with valuable information to work on. You have done an impressive job and
our entire community will be grateful to you.
I am extremely impressed with your writing skills and also with the layout on your weblog.
Is this a paid theme or did you modify it yourself? Either way keep up the nice
quality writing, it is rare to see a great blog
like this one these days.
Excellent 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 web site loaded up as fast as yours lol
It’s perfect time to make some plans for the
future and it’s time to be happy. I’ve read this post and if I could I wish
to suggest you some interesting things or suggestions. Perhaps
you can write next articles referring to this article.
I desire to read even more things about it!
Great blog here! Also your web site loads up fast! What 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 the best time to make some plans for the future
and it is time to be happy. I have read this post
and if I could I wish to suggest you some interesting things or tips.
Perhaps you can write next articles referring to this article.
I want to read even more things about it!
I all the time emailed this website post page to all my associates, for the reason that
if like to read it after that my friends will too.
I quite like looking through an article that can make men and
women think. Also, thank you for allowing for me to comment!
Thank you for sharing your info. I really appreciate your efforts and I am waiting
for your next write ups thank you once again.
Stunning quest there. What happened after? Thanks!
Hi, I desire to subscribe for this website to obtain most recent updates, thus where can i do it please help.
Whats up are using WordPress for your blog platform?
I’m new to the blog world but I’m trying to get started and set up my own. Do you require
any coding expertise to make your own blog?
Any help would be really appreciated!
I read this piece of writing fully regarding the resemblance of most recent and preceding technologies, it’s awesome article.
Do you have a spam issue on this site; I also am a blogger,
and I was wanting to know your situation; we have created some nice methods and we are looking to swap
techniques with other folks, please shoot me an email if interested.
Hey very nice blog!
I could not refrain from commenting. Exceptionally well written!
whoah this blog is wonderful i like studying your posts.
Stay up the great work! You know, many persons are hunting
round for this info, you could aid them greatly.
Hi this is kinda of off topic but I was wondering if blogs use WYSIWYG editors or if you have to manually code with HTML.
I’m starting a blog soon but have no coding know-how so I wanted to get guidance from someone with experience.
Any help would be enormously appreciated!
My brother recommended I would possibly like this website.
He was entirely right. This submit truly made my day.
You cann’t imagine simply how so much time I had spent for this info!
Thank you!
I was recommended this blog by my cousin. I am not sure whether this post is written by him as no one else know such detailed about my
difficulty. You are wonderful! Thanks!
Have you ever considered publishing an e-book or guest authoring on other blogs?
I have a blog centered on the same ideas you discuss and would love to have
you share some stories/information. I know my subscribers would value your work.
If you’re even remotely interested, feel free
to shoot me an e mail.
Your style is very unique compared to other people I have read stuff from.
Thanks for posting when you’ve got the opportunity, Guess I will just
book mark this site.
Howdy very nice website!! Guy .. Excellent .. Wonderful .. I’ll bookmark your website and take the feeds also…I am satisfied to find so many helpful info right here within the put up, we’d like work out more techniques on this regard, thanks for sharing.
Hello! I just wanted to ask if you ever have any problems with hackers?
My last blog (wordpress) was hacked and I ended up losing several
weeks of hard work due to no backup. Do you have any solutions to prevent hackers?
Wow! In the end I got a weblog from where I be able to actually obtain valuable data concerning my study and knowledge.
I’m not sure exactly why but this weblog is loading very slow
for me. Is anyone else having this issue or is it a issue on my end?
I’ll check back later on and see if the problem still
exists.
There is apparently a lot to know about this. I feel you made various good points in features also.have a wonderful day.
I do not even know the way I stopped up here, but I believed this put up was good. I don’t recognize who you are however definitely you’re going to a famous blogger if you happen to aren’t already Cheers!please try to visit my site.
Good web site! I really love how it is simple on my eyes and the data are well written. I am wondering how I could be notified whenever a new post has been made. I’ve subscribed to your feed which must do the trick! Have a great day!
Hey I know this is off topic but I was wondering if you knew of any widgets I could add to my blog that automatically tweet my newest twitter updates.
I was recommended this web site by my cousin. I am not sure whether this post is written by him as nobody else know such detailed about my difficulty.
You are wonderful! Thanks!
Great article, just what I was looking for.
Howdy! I know this is kind of off topic but I was wondering which blog platform are
you using for this website? I’m getting fed up of WordPress because I’ve had problems 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.
When I originally commented I appear to have clicked on the -Notify me when new comments are added- checkbox and from now
on whenever a comment is added I recieve four emails with the same comment.
Perhaps there is a way you are able to remove me from
that service? Many thanks!
I was just seeking this info for some time. After six hours of continuous Googleing, finally I got it in your website. I wonder what is the lack of Google strategy that do not rank this type of informative web sites in top of the list. Usually the top websites are full of garbage.