【BZOJ 4345】[POI2016] Korale

相关链接

题目传送门: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短路来做也是对的
想一想正确性确实很对,不过似乎会炸内存?

15 thoughts to “【BZOJ 4345】[POI2016] Korale”

  1. 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

  2. 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

  3. 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

  4. 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 🙂

Leave a Reply

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