POI18 简要题解

这两天闲的慌把POI18水完了。。。决定发一篇题解以除草。。。。。

Stage I和II似乎发过了。。就发下Stage III的吧。。
Party:每次找到两个不是朋友的人,把他们都删掉,就可以得出结果,为什么很容易证明。
Sticks:我觉得这题有点傻逼。。将所有排序之后,扫描一遍,维护最大且颜色不同的三个即可。

Periodicity:这个题目还是很有意思的,首先这货其实是要求一些长度的前缀和后缀相等,比如1,2,4,10。。那么我们依次构造,比如1,2,4的结果是A,那么可以知道1,2,4,10的结果是A**A。中间当然是能全添0最好,如果不能全添0,把最后一个改成1就行了。如果是1,2,4,7这样的话。直接在A的前面补上一个长度正好的前缀就行了。

Meteors:我们进行分治处理,比如处理到[l,r)这个操作区间,答案在这个区间的国家集合是S,那么我们添加[l,m=(l+r)/2)这些操作,如果一些国家已经够了,那么它的答案就在[l,m)否则就在[m,r),递归处理即可,复杂度是nlogn。

Inspection:这题貌似没有什么难度。。树形dp出每个子树的大小和结果然后判断一下计算结果就行了。

Dynamite:首先二分答案,然后不难发现一个lighted fuel越靠近根越好,那么我们可以从底向上处理,必须放的时候才放。另外这个idea已经年娇处了吧>_<。。。。

Programming Contest:不难建出费用流模型,但是注意到有些边的代价是二次函数,不过这不影响费用流算法>_<,直接做就行了。同时由于此题的特殊性,可以实现的很简单,比如BZOJ上我就写了800B。

7 thoughts on “POI18 简要题解

  1. Party:每次找到两个不是朋友的人,把他们都删掉,就可以得出结果,为什么很容易证明。可我N^2实现这个东西在main只得了9分,后面几乎每一大组数据都错一个点。这是为什么。。

  2. My wife and i got so ecstatic that Ervin managed to finish up his homework through your ideas he came across in your web site. It’s not at all simplistic to simply possibly be giving out concepts that many people today might have been selling. Therefore we understand we need the website owner to be grateful to for that. All the illustrations you’ve made, the easy website menu, the relationships you will make it easier to instill – it’s all excellent, and it’s assisting our son and our family know that the content is exciting, which is certainly pretty vital. Thank you for everything!

Leave a Reply

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>