POI 2010 Stage II 题解

终于搞定了Stage II >_<
下面是题解:
Antisymmetry
这个题目很容易想到枚举中间的,然后二分向两边扩展并用倍增hash快速判断。。注意到NLogN的空间会悲剧。。
我的办法是。。空间是NLogN的。。但是底数是可以变的>_<。。我把底数开到20。。需要的空间就少多了。。
虽然速度慢了。。但还好不至于MLE。
PS。我傻叉。。标程是O(N)的。。
Hamsters
这题的话相信一看到基本会想到快速幂吧。。我注意到这个问题可以转化为一个图论问题,就是n个点的图,AB两点之间的边权是B接在A后面需要新增加的长度。那么其实说白了就是求一个给定边数的最短路径。。这是一个经典问题。。套一下就可以了。。
Blocks:
首先我看到这个题目之后。。想了一会儿。。直觉告诉我贾如当前询问k,那么令C[i]=A[i]-k。。i到j这一段可以全部变得大于等于k的条件是Sum(Ci..j)>=0。。我不怎么会证明。。不过就这样吧。。
然后可以感觉到我们需要求的就是最长的和为正的子串。。
我一开始随便弄了NLogN的做法。。后来发现傻叉爆了>_<。。
看了标程之后才明白。。。把这个看成几何的问题,令Sum[i]为Ci的部分和。
考虑所有点(i,Sum[i])。其实求的就是x跨度最长的终点比起点高的线段。。
那么对于一个终点。。如果它的右上方有点。。显然那个点更优。。
起点也一样。。
所以的话。。我们可以找两条链。。都由那些右上方无点(左下方无点)的点构成。。
然后显然答案就是在两者之间。。然后扫描一条链。。另一条链上的对应点显然会单调移动。。就O(N)了。。。
Sheep
这个题目题型比较经典。。关键是如果在dp的过程中判断对角线是否违反条件的话。。显然是会悲剧的>_<
。。。。其实最关键的一点是。。合法的对角线永远是合法的,非法的永远是非法的。。
比如说一条对角线上有点。。那么显然点不会变没。。
一个对角线两边是偶数。。那么多条两边是偶数的对角线混在一起分开的区域显然也都是偶数,偶数-偶数=偶数。。
两边有一边是奇数。。那边无论怎么也分不好。。
所以预处理出所有合法的对角线。。直接dp就好了。。
Teleportation
这题目好囧。。
首先最终的结果的话。。按照与点1的距离。。当然分为6层(这个可以调整来证明)。分别是距离0到5。。
然后可以发现跟1距离为1、2的点,跟2距离为1和2的点。。层数是无法改变了。。
其他的点则可以随意+到某些层里去。。
首先发现把层1的点调到层2去。。结果不会变差,
层3调到层4也是一样。。
所以把剩下的点放到第2层或第3层。。
考虑到2、3层之间的对调。。可以发现必然是要么全放在2层,要么全放在3层。。
然后就好弄了。。

3 thoughts on “POI 2010 Stage II 题解

  1. 请问有没有poi2010的数据,题目啊,我在官网上下载的时候总是not found。还有poi1999的gra那个题目的数据。poi所有的东西就差这两样啦。有的话给我发一下li2ding1long6@foxmail.com  谢谢啦。膜拜神牛。

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>