IOI 2012 。。。酱油的解题报告。。。

我今天下午看了一下题目。。。。大致上感觉都是可以做的。。。随便写的解题报告。。。有错误请轻喷T_T。。。

Day1:

problem 1:40分还是比较好拿的。。。但是接下来2个task略恶心。。。我有几个思路不知道能拿几分。。。。。。

problem 2:我觉得这题挺简单的吧。。。让我们考虑什么情况下一个图全是链条。。。

条件1:所有点度数<=2(废话)

条件2: 没有环。

那么大致分几种情况讨论和维护一下就行了。。。

problem 3:rope秒杀。。。不用rope的话也可以用类似树的结构。。总之是sb题。。。

Day2:

problem 1:

我们不妨考虑一个简单的情况,如何解决凸多边形的问题?

由于凸多边形比较优美,两点间距离就是曼哈顿。。所以直接算即可。

那么如何解决复杂的情况呢。

不妨以格子为点,相邻点间连边。

给每个格子加权,a和b之间的距离要乘上a和b的权。。
首先处理一个情况,就是桥,显然桥被经过的次数是确定的,同时从其它方向来的点,直接当成权加在桥的两端上就行了。。。

那么现在没有桥了。。。

一开始权都是1。。。

那么如果有度数是1的格子,显然他必须要往它的唯一相邻格走一步,那么就把它的权加到它的相邻格上去然后删掉他,同时这可以看成他走了一步,故答案要加上他的权乘上所有格子的权和。

如果没有度数是1的格子,那么我们考虑最左边的一行,最靠下的点,毫无疑问他的上方和右方必须有点

同时他的右上方也必须有点(不然就有桥了)。

依次类推,可以证明这个点一直往上到不能往上的这一列的右边都有点。

那么显然这一列除了到自己内部之外,都要先往右走一步。

那么在答案中加上这一列内部的情况,然后把他们加到右边那一列上去。。。

同时可以证明之后如果产生了桥,只可能是因为出现了1度点,处理掉即可。。。

看起来很复杂的样子。。。不过复杂度是线性的。。。

UPD:这做法太傻逼了。。

from wqs:注意到把所有横向的最长连续块压成一个点,那么必然形成一棵树,然后树形dp就行了。

我的搞法搞了那么多实际上只是想办法找到树的一个叶子然后往上推。。。本质上是差不多的。。。但是太麻烦了。。。

不过这么搞也行,其实不用求桥,我们可以维护所有边界上的连续块来找。。。。上下左右四个边界上总能找到树的叶子。。。

problem 2:

注意到我们一个点只能保存2个bit。。。

其实2个bit就够了。。。

我们不妨balabala求一个最优解。

然后一个颜料根据是从脚手架上拿的与否跟放不放到脚手架上,有四种状态(注意到,就算一个颜料是从脚手架上拿的,也要记他放不放到脚手架上,不放到的话意思就是会在将来被扔掉)。

那么对于从脚手架上拿的,我们得到了一个rest,如果不放到脚手架上的话,我们维护一个垃圾堆,放到垃圾堆里去。

对于从新的地方拿的,如果不放到脚手架上->直接扔掉。

放到脚手架上->我们随便扔掉一个之前垃圾堆里的颜色。

我傻叉了...不用记是不是从脚手架拿的,直接按脚手架里有没有判断就行了.然后要记一下一开始的k个是不是要直接扔掉.

那么只要N+K bit就能搞定了。。。。

另外这个的原理是什么呢。。。只要注意到这个本质上是一个从网络流的流量中构造解决方案的过程。。。你就明白了。。。

我们可以对这个问题网络流建模,那么可以发现只要2N的信息就能记录这个网络流的流量从而构造出解决方案。

UPD:

根据wqs说的是不用记是不是从脚手架上拿的的,只要记扔不扔掉就可以了,不过这就同时要记一下一开始在脚手架里的那k个扔不扔掉。。。要N+k位。。更优一些。。。

problem 3:

我才发现原来的搞法完全是扯淡。。。

对这个比赛按位置建一个博弈树。

同时将R标称0,比他强的标成1,弱的标成-1。

那么我们注意到,实际上我们要做的是将0跟它右边位置的叶子交换位置,和从0往上数胜利者有几个0。。。

这个是很好搞的。。。

比如说找一个跟当前0 Lca最低的1。。。

这个找0前后最近的两个1试一下就行了。

总体而言day2比day1难。。但是day1有坑爹构造题。。。。momo tourist。。。。 

12 thoughts on “IOI 2012 。。。酱油的解题报告。。。

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>