IOI2014解题报告

信息学奥赛的重要资料。对于爱好信息学奥赛的青少年而言，此报告十分难得。
Chapter 1 Day 1 1.1 Day 1 rail 11.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 Wall 21题目大意 维护一个长度为的整数序列,一开始每个元素均为0,支持以下两种操 作 将连续一段中小于k的元素修改为k 将连续段中大于k的元素修改为k 问所有m个操作进行完之后序列各元素的值。 3 IOI2014解题报告 Day 1 Game 1.22算法讨论 不难发现对某一个元素的操作是可加的,即说对于某一个元素来说,应用 在其上的每一个操作可以都表示为“如果它的初值小于L,那么最终它等于l; 如果它的初值大于γ,那么最终它等于η;否则它最终等于初值”这样的形式, 并且多个这样的形式是可以合并的。于是我们可以把每个操作都看成一个值, 这样原问题就转化成“维护一个序列,每次对一段区间加上一个值,问最后每 个元素的值”。这是可以用带标记的线段树直接维护的。该算法的时间复杂度 为O(m+ m log n) 对于“维护一个序列,每次对一段区间加上一个值,问最后每个元素的值” 这个问题,我们也可以使用扫描线进行维护。但本题中的值是不可减也不满足 交换律的,因此在扫描过程中我们需要使用一个线段树来维护覆盖到当前点的 值并将它们按时间顺序依次求和。该算法的时间复杂度为O(m+ m log m) 1.3 Day 1 game 131题目大意 有一张n个点的无向图,小B每次会询问某两个点之间是否有边相连, 小A每次回答yes或no。如果在小B把所有(条边间完之前,小B就能确定这 整张图是否联選,小A就输了。现在让你当小A,依次对每个询问回答yes或no 求一种获胜方案。1<n<1500 13.2算法讨论 考虑到,如果在一个已经联通(这里指的是通过已经回答过ys的那些边而 联通)的联通块中,还存在一些没有询问的边,那么小B总可以把这些边留到 最后问,小A肯定输了。如果小A能每时每刻保证已经联通的联通块中,已经 没有还没询问过的边了,那么小4就肯定获胜了。 邶么每次小B询问一条边(x,y),如果此时x和y所在的联通块之间只有一条 边了,就凹答yes;否则回答no-这样就可以保证上述邦个性质了。维护两个联 通快之间的边数可以使用并查集。时间复杂度On2) Chapter 2 Day 2 2.1 Day 2 gondola 2.11题目大意 初始有一个序列,由1~n循环位移得到,即可能为 1) 是1到n范围内的任意一个数字。 之后有若干操作,每次操作时,首先找到当前最小的还未用过的编号ad, 将序列中的某个数字替换为il 定义替换序列为每次操作中被替换的数字组成的序列 要回答三个问题 1.一个操作完的序列是否合法? 2.构造一个可能的替换序列 3.可能的替换序列的个数(mod1.00,00) 2.1.2数据范围 前三个了任务只需回答第一个问题 子任务分值7 inputted 55 7≤100 从1到n的数字恰好出现一次 7≤100,0001≤ inputted[i]≤ 107≤100,0001≤ inputted[i]≤250,000 IOI2014解题报告 Day 2 gondola 接下来的三个子任务只需回答第个问题 子任务分值n gondolas 4 7<100 1≤ condo1aseq[i]≤n+1 101≤1,0001≤ condo1aseq[i]≤5,000 6 20 n<100,0001≤ condo1aSeq[i]≤250.000 接下来的四个子任务只需要回答第三个问题: 子任务分值 inputted 5 4≤n≤501< input sea[ 1+3 1≤ inputted[i]≤100,1~m中 154≤n≤50 至少有m-3个出现在操作完的序列中。 15m≤100,0001≤ input seg[i]≤250,000 10 107≤100,0001≤ input sea[i]≤1,000000 2.1.3算法讨论 第一问 如果存在1~m中任意一个,那么先检查相对位置是否正确 检查是否所有数字互不相同。 第二问 如果存在1~仉中任意一个,那么可以确定最开始的序列;否则任选一个 初始序列。 从小到大枚举之后放进去的数字,如果出现在最终序列中,那么放在该位 置,否则放在任意一个非确定的位置。 第三问 从之前的构造可以得到计数的方法 首先用第一问检查是否合法。 如果存在1~n中任意一个,那么可以确定最开始的序列;否则任选一个 初始序列,亦即最后答案公乘以n 对于子任务7~9,依然可以枚举放进去旳数字,如果不出现在最终序列 中,那么答案乘以非确定的位置的个数 对最后一个子任务,可以对最终序列中的数字排序,分段计算即可 6 IOI2014解题报告 Day 2 Friend 14时空复杂度 时间复杂度:O( n log n) 空间复杂度:O(m) 2.2 Day 2 Friend 221题目大意 有一个点带权的无向图,最开始只有点0,随后点1至点n-1依次加入 点加入时,会有一个已经加入的点作为它的host,记为host;,它会在点i和其 他一些已经加入的点之间连边。具体连边方式有以下三种: I方式:只将i与host连边。 M方式:只将i与host的所有邻居连边(host;本身不与i连边)。 W方式:将i与hos;及其所有邻居连边。 现在已知每个点的点权,host以及连边方式,求该图的最大点杖独立集。 22.2算法讨论 注意到如果将host;当做点i父亲,我们就能得到一棵以点0为根的树,其 中每个孩子节点根据相应的点的连边方式不同可以分为Ⅰ、M和W三种类型。考 虑树形DP。令f()表示点诃可以被选的情况下以为根的子树的最大权值,g()表 示点能被选的情况下以i为根的子树的最大权值(这里的能否被选是在不考 虑以i为根的子树的情况下)。 首先考虑g(i)的计算。因为点是不能选的,所以点的所有M类和W类孩子 都是不能选的,I类孩子是可以选的。因此 ∑9(u)+∑f() 其中u是的M类或W类儿子,0是iI类孩子 ∫()的计算分两种情况。第一种情况,我们选择了点,那么点i的所有I类 和W类孩子就不能选了,而M类孩子仍是可以选的,所以在这种情况下 f()=∑9(u)+∑ 7 IOI2014解题报告 day 2 holiday 其中α是i的I类吸W类孩子,是的M类孩子。第二种情况,也就是不选择点a 凊况稍微复杂一些,我们需要决定的每个孩子α是否能够被选择,唯一的限制 是,一旦我们决定了一个类或W类儿子是可以选择的,那么在它之后加入(编 号比它大)的M类孩子和W类孩子就是不能选择的了。我们可以对所有孩 子进行一个简单的DP来作出最优决定,再加上i点本身的权值即可得到这种情 况下的f()。最后,在两种情况下得到的∫(i)屮取较大的一个作为最后的f()即 最终,f(0)即为答案。该算法的时间复杂度为O(m) 2.3 Day 2 Holiday 231题目大意 n个城市依次排开,编号为0到m-1。i号城市与讠-1号城市和i+1号城市 相邻。一开始你在 start号城市。每一个时刻,你可以选择移动到相邻的一个城 市,或者游玩当前城市,并获得α;的娱乐值,其中i是你现在所在的城市编号。 你不能游玩同一个城市多次,但是能多次经过同一个城市。问d天你能获得的最 大愉悦值是多少。1<m<100000 2.3.2算法讨论 起点在0号城市 可以发现,在这种情况下,只会一直往右移动,而不会回头。因此可以枚 举往右走到的最右边那个城市,然后再从剩余的天数中,选择愉悦值最大的若 干个城市进行游览。后者可以用可持久化线段树实现。 只往右走,对每个d求得答案 令∫a为可以游览d大,最优的那个右端点。我们有如果x<y,那么f≤f 考虑fx与x+1,假设fx+1<fx。先把能游览x+1天的右端点与游览x天的 右端点放在∫处。右端点每次向左栘动一格,游览π天的与游览x+1天的,都 能游览一个新的城市(当最右端的那个城市本来也被选时,是两个新的城市)。 但由于ε+1天的本来就比天的游览了更多的城市,所以这个天的新城市的愉 悦值要大于等于+1天的新城市的愉悦值。当它们移动到fx+1时,x天的增加 的愉侻值大于等于x+1天的增加的愉悦值。于是就矛盾了。因此有f≤f+1 IOI2014解题报告 day 2 holiday 接下去考虑分治,要求d在1,中的所有fa,并且知道这些fa在[a,b中。令mid 12」,首先暴力找到fmd接下去递归分别找h…fmid-1,fmi+1…f。其中 f;……fmad-1都在a,fmd之间;fmid4+1….f都在[fmtd,b之间。这样总的时间复 东度是O( )的 原问题 最优策略肯定是往右走再折回左边,或者往左走再折回右边。既然可以对 每一个d都求出只在左边或者只在右边的答案,也可以求出对于每一个d往 方向走,再折回 start的答案(具有类似上文中的单调性),那么只要求出两边 分别对于所有d的答案后,就能求出整个问题的最优解了。