【日常小测】Circle of Stones

Qizy KMP, 字符串, 解题报告

题目大意

给定$(n \le 10^6)$个石头，它们排成一圈
每个石头上有一个小写英文字母
定义优雅为任意两个相邻的石头上的字母不同
请你输出$n$个数(0/1)，第$i$个数表示删除$i-1$个连续的石头能否使原来的圈成为优雅的圈
每个测试点包含$T(1 \le T \le 6)$组数据

解题报告

我们先来解决一个子问题：如果给定一个优雅的长度为$n$的圈$A$，问保留能否选择连续的$1 \sim n$个石头，使之优雅
考虑长度为$l$的询问，那么左端点和右端点的可行解都是一段长度为$n-l+1$的前缀/后缀
如果这两段区间不完全相等（不是原串的循环节），那么肯定可以把不等的那一位拿出来作为可行解
于是我们用$KMP$求一个循环节就可以了

现在我们再来看原问题，考虑原串中相邻的两位$i,i+1$和右边一次相邻的两位$j,j+1$
显然我们至多保留$[i+1,j]$这一串
那么这一串此时已经是优雅的了，于是就成了刚刚我们讨论的子问题
于是找出每一个极大的优雅子串，跑一边$KMP$更新答案，最后输出即可
时间复杂度：$O(Tn)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 2000009;
 
int n,nxt[N],vis[N];
char pat[N],ans[N];
 
inline int read() {
    char c=getchar(); int 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 bool SPJ() {
    if (pat[n] == pat[1]) return 0;
    for (int i=2;i<=n;i++) if (pat[i] == pat[i-1]) return 0;
    return 1;
}
 
inline int cyc(int l, int r) {
    nxt[1] = 0; 
    for (int w=0,i=l+1;i<=r;i++) {
        while (w && pat[w+l] != pat[i]) w = nxt[w];
        if (pat[w+l] == pat[i]) w++;
        nxt[i-l+1] = w;
    } int len = r - l + 1;
    if (nxt[len] &&len % (len - nxt[len]) == 0) return len - nxt[len];
    else return 0;
}
 
inline void update(int l, int r) {
    static int id = 1; id++;
    int lop = cyc(l, r), len = r - l + 1;
    for (int w=nxt[len];w;w=nxt[w]) vis[w] = id;
    for (int i=1,lim=min(len,n);i<=lim;i++) 
        if (vis[len-i+1]!=id) ans[n-i] = '1';
}
 
int main() {
    for (int t=1,lop;~scanf("%s",pat+1);++t) {
        n = strlen(pat+1); printf("Case %d: ",t);
        for (int i=0;i<n;i++) ans[i] = '0';
        ans[n] = 0; ans[n - 1] = '1';  
        memcpy(pat+n+1, pat+1, sizeof(char)*n);
        if (SPJ()) update(1, n<<1);
        else {
            int pre = 0;
            for (int i=n<<1;i;i--) {
                if (pat[i] == pat[i+1]) {
                    if (i < n) update(i+1, pre);
                    pre = i;
                }
            }
            if (pre && pat[1] == pat[n] && n > 1) update(1, pre);
        }
        puts(ans);
    }
    return 0;
}

299 thoughts to “【日常小测】Circle of Stones”

  1. Hey very cool site!! Guy .. Beautiful .. Wonderful .. I will bookmark your
    website and take the feeds also? I am satisfied to search out so
    many useful information here in the publish, we want develop more strategies
    on this regard, thanks for sharing. . . . . .

    Reply

  3. you are in point of fact a excellent webmaster.

    The web site loading velocity is amazing. It sort of feels
    that you are doing any distinctive trick. Also, The contents are
    masterpiece. you’ve performed a great activity on this topic!

    Reply

  4. Thanks for your personal marvelous posting! I actually enjoyed reading it, you might be a great author.
    I will be sure to bookmark your blog and may come back in the future.
    I want to encourage you to continue your great job, have a nice day!

    Reply

  5. Greetings from Ohio! I’m bored at work so I decided to check
    out your website on my iphone during lunch
    break. I enjoy the knowledge you provide here
    and can’t wait to take a look when I get home. I’m
    surprised at how quick your blog loaded on my phone ..
    I’m not even using WIFI, just 3G .. Anyhow, amazing site!

    Reply

  6. I like the valuable info you provide in your articles.
    I will bookmark your blog and check again here frequently.
    I am quite sure I’ll learn a lot of new stuff right here!
    Best of luck for the next!

    Reply

  7. What’s Going down i’m new to this, I stumbled upon this I have discovered It positively helpful and it has helped me
    out loads. I hope to give a contribution & assist different customers like its aided me.
    Great job.

    Reply

  9. Please let me know if you’re looking for a article author
    for your blog. You have some really good posts and I think I would be a good asset.
    If you ever want to take some of the load off, I’d really like to write some articles for your blog in exchange
    for a link back to mine. Please shoot me an email if interested.
    Cheers!

    Reply

  11. Hi I am so glad I found your web site, I really found you by
    mistake, while I was searching on Yahoo for something else, Anyways I
    am here now and would just like to say kudos for a fantastic post
    and a all round entertaining 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 your
    RSS feeds, so when I have time I will be back to read a great deal more,
    Please do keep up the great job.

    Reply

  14. wonderful post, very informative. I wonder why the opposite specialists of this sector do
    not notice this. You should continue your writing.

    I’m sure, you have a huge readers’ base already!

    Reply

  15. Does your website have a contact page? I’m having trouble locating it but,
    I’d like to send you an email. I’ve got some recommendations for your blog you
    might be interested in hearing. Either way, great website and I look forward to seeing it expand over time.

    Reply

  20. Definitely imagine that which you stated.
    Your favourite justification seemed to be on the web the easiest factor to keep in mind of.
    I say to you, I certainly get irked while other folks consider worries
    that they just do not recognize about. You managed to hit the
    nail upon the highest and also defined out the whole thing with no need
    side-effects , other people can take a signal. Will likely be back to get more.
    Thanks

    Reply

  23. I just couldn’t go away your web site before suggesting that I actually
    enjoyed the usual information a person supply on your visitors?
    Is going to be again steadily in order to inspect new posts plenty of fish natalielise

    Reply

  25. Howdy, There’s no doubt that your blog may be
    having web browser compatibility issues. When I take a look at your web site
    in Safari, it looks fine but when opening in Internet Explorer, it’s got some
    overlapping issues. I simply wanted to provide you with a quick heads up!
    Besides that, excellent site!

    Reply

  27. whoah this weblog is great i really like reading your articles.
    Keep up the great work! You realize, many individuals are hunting around for this information, you could
    help them greatly.

    Reply

  31. Hi there very nice web site!! Man .. Excellent
    .. Wonderful .. I’ll bookmark your web site and take the
    feeds additionally? I am glad to find so many useful info here in the post,
    we’d like work out extra strategies in this regard, thank you for sharing.
    . . . . .

    Reply

  36. This design is steller! You definitely know how to keep a reader amused.

    Between your wit and your videos, I was almost
    moved to start my own blog (well, almost…HaHa!) Fantastic job.

    I really loved what you had to say, and more than that, how
    you presented it. Too cool!

    Reply

  38. Generally I do not learn article on blogs, however
    I wish to say that this write-up very pressured me to
    take a look at and do it! Your writing taste has been surprised me.
    Thank you, very great article.

    Reply

  39. This is the right blog for anyone who wants to find out
    about this topic. You realize so much its almost hard to
    argue with you (not that I personally would want to…HaHa).
    You certainly put a brand new spin on a topic which has
    been discussed for ages. Wonderful stuff, just wonderful!

    Reply

  43. Hey there! This post could not be written any better!
    Reading through this post reminds me of my previous room mate!
    He always kept talking about this. I will forward this
    article to him. Pretty sure he will have a good read. Thank you for sharing!

    Reply

  44. Hmm is anyone else encountering problems with the pictures on this blog loading?
    I’m trying to find out if its a problem on my end or if it’s
    the blog. Any responses would be greatly appreciated.

    Reply

  46. I do believe all of the concepts you have offered to your post.

    They are really convincing and can certainly work. Nonetheless,
    the posts are too brief for beginners. May just you please lengthen them a
    bit from next time? Thanks for the post.

    Reply

  47. You really make it seem really easy with your presentation however I to find this
    matter to be actually something which I believe I might by no means understand.
    It kind of feels too complicated and extremely vast for me.
    I am having a look forward to your subsequent submit, I will try to get the dangle of it!

    Reply

  48. Thanks on your marvelous posting! I really enjoyed reading it, you are a great author.
    I will ensure that I bookmark your blog and definitely will come back
    from now on. I want to encourage you to ultimately continue your great writing, have a nice day!

    Reply

  50. We are a group of volunteers and opening a new scheme in our community.
    Your site provided us with valuable info to work on. You have done a formidable job
    and our whole community will be grateful to you.

    Reply

  65. I don’t know whether it’s just me or if everybody
    else experiencing problems with your site. It appears like some of
    the text in your content are running off the screen. Can somebody else please comment and let me
    know if this is happening to them too? This could be a issue with my internet
    browser because I’ve had this happen before. Cheers

    Reply

  81. It’s appropriate time to make some plans for the future and it is time to be happy.
    I’ve read this post and if I could I desire to
    suggest you few interesting things or tips.
    Perhaps you can write next articles referring to this article.
    I want to read even more things about it!

    Reply

  87. Heya! I realize this is kind of off-topic however I had to ask.

    Does running a well-established website like yours take
    a large amount of work? I am completely new to
    writing a blog however I do write in my diary every day.

    I’d like to start a blog so I will be able to share my own experience and feelings online.
    Please let me know if you have any kind of suggestions
    or tips for brand new aspiring bloggers. Appreciate it!

    Reply

  113. We stumbled over here by a different web page and thought I might as well
    check things out. I like what I see so now i’m following
    you. Look forward to looking into your web page yet again.

    Reply

  121. Wow that was odd. I just wrote an extremely long comment but after
    I clicked submit my comment didn’t show up. Grrrr…
    well I’m not writing all that over again. Anyway, just
    wanted to say wonderful blog!

    Reply

  129. Hello my loved one! I want to say that this article is amazing, nice written and include approximately all significant infos. I would like to peer extra posts like this .

    Reply

  135. Hi there, I believe your web site may be having web browser compatibility
    issues. When I look at your website in Safari, it looks fine however,
    when opening in I.E., it has some overlapping issues.
    I merely wanted to provide you with a quick heads up!

    Other than that, excellent website!

    Reply

  181. I know this site presents quality based articles or reviews and other information, is
    there any other web site which offers these information in quality?

    Reply

  192. Pretty nice post. I just stumbled upon your weblog and wanted to say that I’ve
    truly enjoyed surfing around your blog posts. After all I will be subscribing to your rss feed and I hope
    you write again very soon!

    Reply

  206. I am really loving the theme/design of your blog.

    Do you ever run into any internet browser compatibility issues?
    A few of my blog readers have complained about
    my website not operating correctly in Explorer but looks great in Opera.
    Do you have any ideas to help fix this problem?

    Reply

  237. It is really a great and useful piece of info. I’m glad that you shared this helpful information with us. Please keep us informed like this. Thank you for sharing.

    Reply

  257. Hi, Neat post. There’s a problem together with your website in internet explorer, may test this? IE still is the market leader and a big element of other people will leave out your magnificent writing due to this problem.|

    Reply

  259. I was suggested this web site by my cousin. I’m not sure whether this post is written by him as nobody else know such detailed about my difficulty. You’re incredible! Thanks!|

    Reply

  274. Hi 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 hard time making a decision between BlogEngine/Wordpress/B2evolution and Drupal. The reason I ask is because your layout seems different then most blogs and I’m looking for something completely unique. P.S Apologies for being off-topic but I had to ask!|

    Reply

  279. Great blog! Is your theme custom made or did you download it from somewhere? A design like yours with a few simple adjustements would really make my blog shine. Please let me know where you got your design. Bless you|

    Reply

  280. Hi there! This is kind of off topic but I need some guidance from an established blog. Is it hard to set up your own blog? I’m not very techincal but I can figure things out pretty quick. I’m thinking about setting up my own but I’m not sure where to start. Do you have any points or suggestions? Appreciate it|

    Reply

  281. I just couldn’t depart your web site before suggesting that I extremely enjoyed the usual information a person provide for your guests? Is going to be back steadily in order to check out new posts|

    Reply

  283. Hi there! I realize this is sort of off-topic but I had to ask. Does operating a well-established website such as yours take a massive amount work? I am completely new to blogging but I do write in my journal everyday. I’d like to start a blog so I can share my own experience and thoughts online. Please let me know if you have any kind of suggestions or tips for new aspiring blog owners. Appreciate it!|

    Reply

  290. hello there and thank you for your info – I’ve definitely picked up anything new from right here. I did however expertise a few technical issues using this website, since I experienced to reload the web site a lot of times previous to I could get it to load properly. I had been wondering if your web host is OK? Not that I am complaining, but sluggish loading instances times will very frequently affect your placement in google and can damage your quality score if advertising and marketing with Adwords. Anyway I am adding this RSS to my email and can look out for much more of your respective interesting content. Ensure that you update this again soon.|

    Reply

  299. I really like what you guys are up too. This sort of clever work and reporting! Keep up the great works guys I’ve incorporated you guys to my blogroll.|

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *