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。

最近水的一些sgu题目。。

由于基本上前人都有题解。。。。。。所以发这篇的单纯是除草。。。。。

由于做的比较多。。就只说说AC数<20的好了。。。

sgu 331:crazyb0y有题解。。没啥好说的。。。

sgu 387:挺傻逼的一题。。令人吐槽不能的是大小可以为0。。。

sgu 450:挺傻逼的模拟题。。

sgu 470:就几行的傻逼构造题。。。

sgu 472:分治一下算出每个点周围的最短路然后dijstra就行了。。。

sgu 474:挺裸的题目。。。。没啥好说的。。。

sgu 498:意外的居然是傻逼题。。。随便算算就能算出来了。。。

 

个人感觉难的题目的话。。ural总体质量比sgu好?当然这跟ural题目比较多也有关系。。不过sgu上好题也是有些的。。。