【BZOJ 3917】[Baltic2014] sequence

Qizy 其他, 分治, 搜索, 状态压缩, 解题报告

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3917
神犇题解Ⅰ：http://blog.csdn.net/lcrtest/article/details/51312981
神犇题解Ⅱ：http://blog.csdn.net/neither_nor/article/details/52604754

吐槽

他们说这题是APIO 2016练习赛的题目，为什么我一点印象都没有 QwQ
想了很久都只会$O(\frac{n^2}{64})$的暴力，我也很绝望啊…..

解题报告

我们发现，对于比较高的位数来讲，其一样的数在一起
考虑将一样的数合在一起，并且从低位到高位处理

记录二进制状态$f_{i,j}$表示在第$i$位的时候，第$j$块里需要哪些数
如果当前只需要一个数了，那么就可以直接返回辣！（如果是0需要特判）
否则的话，我们枚举这一位在第一个数中是多少
因为下一层中连续的区间长度大概都比现在这一位连续的区间长10倍
所以我们可以把这一位中的状态每十个合成一块，下一层的话又是一个递归子问题，我们可以递归下去
考虑每一层的总复杂度：第$i$层有$10^i$个分叉，每个分叉内有$\frac{n}{10^i}$个块，于是每一层的复杂度是$O(n)$的
下面我们来总复杂度$T(n)=10 \cdot T(\frac{n}{10}) + n$
根据主定理，这货是$O(n \log{n})$的

293 thoughts to “【BZOJ 3917】[Baltic2014] sequence”

  40. I got this web site from my friend who informed me concerning this website and at the moment
    this time I am browsing this site and reading very informative articles
    or reviews here.

    Reply

  43. Right here is the perfect blog for everyone who wants to find out about this topic.
    You know a whole lot its almost hard to argue
    with you (not that I actually would want to…HaHa).
    You definitely put a fresh spin on a topic which has
    been discussed for many years. Wonderful stuff, just excellent!

    Reply

  57. 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 results. If you know of any please share.
    Thank you!

    Reply

  69. You really make it seem so easy with your presentation but I find this topic to be
    actually something which I think I would never understand.
    It seems too complicated and extremely broad for me.
    I’m looking forward for your next post, I’ll try to get the hang of it!

    Reply

  78. I absolutely love your blog and find many of your post’s to be
    precisely what I’m looking for. can you offer guest writers to write content for yourself?
    I wouldn’t mind publishing a post or elaborating
    on a few of the subjects you write related to
    here. Again, awesome weblog!

    Reply

  88. Oh my goodness! Incredible article dude! Many thanks, However I am experiencing troubles with your RSS.
    I don’t know the reason why I am unable to subscribe to it.
    Is there anyone else having similar RSS problems? Anyone who
    knows the answer will you kindly respond? Thanks!!

    Reply

  91. With havin so much content and articles do you
    ever run into any issues of plagorism or copyright violation? My website has a lot of exclusive
    content I’ve either written myself or outsourced but it appears a lot of it is
    popping it up all over the internet without my agreement.
    Do you know any techniques to help stop content from being
    ripped off? I’d genuinely appreciate it.

    Reply

  100. of course like your website but you have to check the spelling on several of your posts.
    Several of them are rife with spelling issues and I to find it very troublesome to tell the truth nevertheless I will certainly come again again.

    Reply

  104. A person necessarily assist to make significantly articles I would state. This is the very first time I frequented your website page and to this point? I amazed with the research you made to make this particular publish extraordinary. Magnificent task!

    Reply

  169. Hmm it seems like your site ate my first comment (it
    was super long) so I guess I’ll just sum it up what I submitted and say, I’m
    thoroughly enjoying your blog. I as well am an aspiring
    blog writer but I’m still new to everything.
    Do you have any helpful hints for newbie blog
    writers? I’d certainly appreciate it.

    Reply

  183. Having read this I believed it was extremely informative.
    I appreciate you taking the time and effort to put this informative article together.
    I once again find myself personally spending a significant amount of time both reading and
    posting comments. But so what, it was still worthwhile!

    Reply

  187. I think what you published was very logical. However, what about this?
    suppose you typed a catchier title? I am not saying your content isn’t solid., but
    what if you added a post title that makes people desire more?
    I mean 【BZOJ 3917】[Baltic2014] sequence – Qizy's Database is a little vanilla.
    You could look at Yahoo’s front page and note how they create news headlines to get people interested.
    You might try adding a video or a related picture or two to get readers interested
    about what you’ve got to say. Just my opinion, it could make your posts a little
    livelier.

    Reply

  208. Amazing blog! Do you have any suggestions for aspiring
    writers? I’m hoping to start my own blog soon but I’m a little lost on everything.
    Would you suggest starting with a free platform like WordPress or go for a paid option? There are so many options out
    there that I’m completely confused .. Any recommendations?
    Appreciate it!

    Reply

  215. A fascinating discussion is definitely worth comment.
    I think that you ought to write more about
    this topic, it may not be a taboo matter but generally folks don’t talk about such issues.
    To the next! Many thanks!!

    Reply

  224. Howdy! Do you know if they make any plugins to protect against hackers? I’m kinda paranoid about losing everything I’ve worked hard on. Any recommendations? babdabcfdfea

    Reply

  225. hello there and thanks on your info – I have definitely picked up anything new from right here. I did then again experience several technical issues the use of this site, as I experienced to reload the site many times prior to I could get it to load correctly. I had been considering in case your hosting is OK? Not that I am complaining, however slow loading circumstances times will often impact your placement in google and could harm your high-quality rating if advertising and ***********|advertising|advertising|advertising and *********** with Adwords. Well I am including this RSS to my email and can glance out for much extra of your respective exciting content. Ensure that you update this again soon..

    Reply

  227. Hello would you mind letting me know which hosting company you’reworking with? I’ve loaded your blog in 3 different browsers and I must say this blog loads a lotfaster then most. Can you suggest a good hosting provider at a honest price?Many thanks, I appreciate it!

    Reply

  229. My spouse and i were absolutely joyous Raymond could conclude his web research from the ideas he was given out of your web page. It is now and again perplexing just to choose to be giving for free points that other folks have been making money from. And now we recognize we now have you to appreciate for that. All the explanations you made, the easy site menu, the friendships you will give support to promote – it is many fabulous, and it’s making our son in addition to us believe that this content is fun, and that is exceedingly important. Thanks for all!

    Reply

  234. Hi, Neat post. There is a problem along with your site in internet explorer, would check this… IE nonetheless is the market chief and a big component of folks will omit your excellent writing because of this problem.

    Reply

  243. Sivas nakliyat fiyatları veya hizmet talep eden insanlara yaklaşımı ile birlikte güvenilir bir firmanın nakliye çalışmalarına bakmak lazım. Ücretler ve yan yana konulmuş olan kaliteli hizmetler ile beraber, mevcut performansın avantajları burada insanlar için sağduyulu bir sonuç oluşturmaya devam etmektedir. Son derece detaylı ve karakterli bir duruş sergileyen Sivas nakliyat ile birlikte, problemler çözülüyor ve sorunlar tamamen gideriliyor. Daha sonrasında ise kaliteli firmanın çalışmaları ile beraber sizin için hazırlanmış mükemmel hizmetler gündemde kalmaya devam ediyor. Kendi müşterisi için ürettiği çözümler ile beraber, bildiğiniz ve tercih ettiğiniz firmanın en cazip koşullarına buradan bakabilirsiniz. Yol koşulları zorlu olsa da ya da ambalaj hizmeti biraz daha zorlu bir süreç başlatsa da elemanlar bu konuda hazırlıklıdır.

    Reply

  244. Hello there. I found your blog by way of Google at the same time as looking for a related topic, your web site got here up. It seems great. I’ve bookmarked it in my google bookmarks to come back then.

    Reply

  252. An interesting discussion is definitely worth comment. I do believe that you need to write more on this topic, it may not be a taboo subject but typically people do not talk about such subjects. To the next! Many thanks!!|

    Reply

  265. The other day, while I was at work, my cousin stole my iPad and tested to see if it can survive a forty foot drop, just so she can be a youtube sensation. My apple ipad is now destroyed and she has 83 views. I know this is completely off topic but I had to share it with someone!|

    Reply

  267. Hello! I’m at work browsing your blog from my new apple iphone! Just wanted to say I love reading through your blog and look forward to all your posts! Carry on the outstanding work!|

    Reply

  272. Heya i’m for the first time here. I came across this board and I find It truly useful & it helped me out a lot. I hope to give something back and aid others like you helped me.|

    Reply

  273. This design is incredible! You obviously know how to keep a reader amused.Between your wit and your videos, I wasalmost moved to start my own blog (well, almost…HaHa!) Great job.I really loved what you had to say, and more than that, howyou presented it. Too cool!

    Reply

  276. It’s a pity you don’t have a donate button! I’d definitely donate to this superb blog! I suppose for now i’ll settle for bookmarking and adding your RSS feed to my Google account. I look forward to brand new updates and will talk about this site with my Facebook group. Talk soon!|

    Reply

  281. It is perfect 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 want to suggest you some interesting things or suggestions. Perhaps you could write next articles referring to this article. I desire to read even more things about it!|

    Reply

  282. Pretty great post. I just stumbled upon your weblog and wished to mention that I have truly enjoyed browsing your blog posts. After all I will be subscribing for your rss feed and I’m hoping you write once more soon!|

    Reply

  287. My spouse and I stumbled over here different page and thought I might check things out. I like what I see so now i’m following you. Look forward to finding out about your web page yet again.|

    Reply

  292. It’s really very difficult in this full of activity life to listen news on TV, therefore I just use world wide web for that reason, and take the latest news.|

    Reply

  293. What’s Happening i’m new to this, I stumbled upon this I’ve found It absolutely helpful and it has helped me out loads. I am hoping to give a contribution & help different customers like its helped me. Great job.|

    Reply

Leave a Reply

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