IOI2014解题报告

信息学奥赛的重要资料。对于爱好信息学奥赛的青少年而言，此报告十分难得。Chapter 1Day 11.1 Day 1 rail11.1题目大意有两条平行的单向铁路(上方的从右到左,下方的从左到右),分为m段有η个车站,每个车站为C类型(只能从上往下)或D类型(只能从下往上),分布在某些段中,每个段最多一个车站。已知0号车站是C类型,并给出0号车站的位置,最多可以询问两车站之间的距离3(n-1)次(距离指经过段与段连接处的次数,例如上图0号车站到2号车站的距离为5),要求确定每个车站的位置和类型。保证车站两两可达11.2算法讨论先询问得到0号车站到其他车站的距离,而最近的一个,就是0号车站右侧第一个D类型的(称之为j号车站)然后询问得到号车站到其他车站的距离,其中最近的一个,可能是0号车站,也可能是其他车站(都称之为k号车站),显然和k之间不会冉有其他车IOI2014解题报告Day 1 Wall站,而0和k之间也不会有其他的D类型的车站,所有k号车站到其他车站的距离可直接算出有了和k到其他车站的距离,那就可以轻松分出左右了(离j号近,就在k的左侧,否则在j的右侧)。但分出左右后还是不能确定具体位置,而这时对于每个车站我们还留下次询问的机会。接下来称当前车站为号车站而这次询问一定是留给特殊位置的车站,假设当前车站在左侧,则考虑当前确定的最左侧的车站(称之为L号)。按离(或k)号车站的距离从近到远的顺序处理剩下的车站,那么只有这两和情况:L k j以及(注意下面这种L和之间还会有C类型的车站)L i k两者都会有以下关系式:dst(j,L)+|0s;-pos|=dist(j.)+x(x≥0)第一种情况多出来的是L到它右侧第一个D类型车站的距离×2,而第二种情况多出来的是L到它右侧第一个C类型车站的距离×2。所以,算出x之后,只要到L右侧的c/2的距离处看下车站的类型就可以确定位置了。这样问题就解决了如果当前车站在右侧,那么询问与已确定的最右侧车站的距离,类似讨论即可。1.2 Day 1 Wall21题目大意维护一个长度为的整数序列,一开始每个元素均为0,支持以下两种操作将连续一段中小于k的元素修改为k将连续段中大于k的元素修改为k问所有m个操作进行完之后序列各元素的值。3IOI2014解题报告Day 1 Game1.22算法讨论不难发现对某一个元素的操作是可加的,即说对于某一个元素来说,应用在其上的每一个操作可以都表示为“如果它的初值小于L,那么最终它等于l;如果它的初值大于γ,那么最终它等于η;否则它最终等于初值”这样的形式,并且多个这样的形式是可以合并的。于是我们可以把每个操作都看成一个值,这样原问题就转化成“维护一个序列,每次对一段区间加上一个值,问最后每个元素的值”。这是可以用带标记的线段树直接维护的。该算法的时间复杂度为O(m+ m log n)对于“维护一个序列,每次对一段区间加上一个值,问最后每个元素的值”这个问题,我们也可以使用扫描线进行维护。但本题中的值是不可减也不满足交换律的,因此在扫描过程中我们需要使用一个线段树来维护覆盖到当前点的值并将它们按时间顺序依次求和。该算法的时间复杂度为O(m+ m log m)1.3 Day 1 game131题目大意有一张n个点的无向图,小B每次会询问某两个点之间是否有边相连,小A每次回答yes或no。如果在小B把所有(条边间完之前,小B就能确定这整张图是否联選,小A就输了。现在让你当小A,依次对每个询问回答yes或no求一种获胜方案。1