相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4345
神犇题解:http://sr16.com:8081/【bzoj4345】【poi2016】korale/
解题报告
这题看到$k$这么玄学,那就一定是与$k$相关辣!
想一想可不可以用线段树合并做。或者可持久化Treap?
然而似乎都不好做。
我们考虑暴搜的搜索树,如果我们使用$BFS$加上小根堆,显然没有问题
于是我们定义二元组$(i,j)$表示当前集合的权值为$i$,最大的元素编号为$j$
类比搜索树,则转移为 $(i,j) \Rightarrow (i + a[j + 1],j + 1)\& (i + a[j + 1] – a[j],j + 1)$
于是我们就可以求出第$k$小的值$ans$了!
然后我们再来考虑如何输出方案:我们暴搜方案,将结果$>ans$的直接剪掉就可以啦!
考虑这样复杂度为什么是对的,因为 $ \le ans$ 的方案数不会超过$k$个啊!
—————————— UPD 2017.3.22 ——————————
今天考试考了这个题,然后wuvin说直接那k短路来做也是对的
想一想正确性确实很对,不过似乎会炸内存?
262651 805431Yours can be a prime example of informative writing. I feel my students could learn a lot from your writing style and your content. I could share this article with them. 489947
251374 657352I see something actually fascinating about your internet internet site so I saved to bookmarks . 139084
562753 980477I as well conceive so , perfectly indited post! . 92115
883369 412774Your blog has the same post as an additional author but i like your much better.~:; 714686
755832 639548Very good post, properly put together. Thanks. I will likely be back soon to look at for updates. Cheers 936914
546774 792486I was reading some of your content material on this web site and I believe this internet web site is really informative! Keep putting up. 15718
951487 402990Hello DropshipDragon provides dropping for quality, affordable products direct from China to your customers. Perfect for eBay sellers and web site owners alike! 578963
367854 269024Any person several opportune pieces, it comes surely, as well as you bring in crave of various the numerous other types of hikers close to you with hard part your question. pre owned awnings 466244
929218 694925Wonderful write-up. I appreciate your attention to this topic and I learned a lot 492496
380463 753240Just wanna comment that you have a really good web site, I the style and design it actually stands out. 583818
211827 540491This website is really a walk-through for all with the data you wanted about it and didnt know who to question. Glimpse here, and you will undoubtedly discover it. 6445
821354 671099I undoubtedly didnt understand that. Learnt some thing new nowadays! Thanks for that. 666668
Great website. A lot of helpful info here. I?¦m sending it to some friends ans additionally sharing in delicious. And obviously, thank you for your effort!
456496 35195The posh distributed could be described as distinctive; customers are really yearning for bags is a Native aspirations. Which strange surroundings is built that is to market diversity furthermore importance with travel and leisure market trends. hotels special offers 944701
Very nice post and right to the point. I don’t know if this is really the best place to ask but do you guys have any ideea where to employ some professional writers? Thx 🙂