HEOI 2018 | 九省联考 2018 题解&游记


题解

Day1

T1:一双木棋(chess)

考场上基本上一眼50分,打完之后弃掉直接去做后面的题,离考试结束还有1.5h的时候回来优化,发现只要hash+记忆化一波就好了,自然溢出+map极限要跑300ms,怕不稳就和双取模+hash表拍,没啥问题。

 

T2:IIIDX(iiidx)

先写了个显然的贪心,感觉不会这么简单就让我AC,于是就造各种数据开始hack,最后发现权值相同时直接贪心根本就是错的,瞬间变成了55分。写了个n^2模拟预留的过程,感觉和正解比较接近,期望70,但是最后还是挂成了55分。

我们先将权值从大到小排序,设f[i]表示在i左边的可用元素个数(初始f[i]=i),那么给当前点选可以选到的最大的权值的最右边的,然后在它左边预留出子树大小个元素(并不需要真的知道预留的是哪些元素),也就是给右边的元素区间减去当前子树大小(左边不用管)。那么我们每次只要在线段树上二分出一个位置,满足该位置右边的f值最小值>=当前子树大小就可以不创造矛盾,即不影响之前的预留操作。找到了这个位置,就可以跳到和他相等的最靠右的元素,这个点就是根的答案。注意,每次到第一个儿子的时候需要把父亲预留的给补回来。

 

T3:秘密袭击(coat)

考场上25分暴力滚粗,并没有去想60分的DP做法。

这道题的正解十分不可做,而且有暴力踩正解的做法,于是我就写的暴力做法。

考虑枚举每个点成为所在连通块的第k大,那么问题转化为求方案数。把点从大到小加进去,那么问题转化为在以当前点x为根的连通块中,选出k个(一定包含x)已加入的点的方案数。类似树形背包的做法,维护一条链一侧的DP数组,也就是先把父亲的扔给儿子,用儿子的子树更新之后再还给父亲,理解一下运算顺序就可以知道DP数组的含义了。

 

Day2

T1:劈配(mentor)

考场上一眼70分暴力,觉得一定是一道网络流神题,写完想了想就弃了。

感觉正解跑dinic不是很优美,那我们就用二分图匹配来解决这个问题。二分图中,左边的点代表选手,右边的点代表导师,且每个导师拆成b[i]个点。将每个选手向导师连边,连边时按照志愿高低来决定先后。这样,我们在匈牙利算法中只要保证每个人匹配的不比目前已经匹配到的差就好了,时间复杂度O(n^4logn)。一点对于边数的优化就是在第二步二分答案的时候,[1,x-1]区间中一定仍然是最优的,那么我们只要连O(n)条连向每个人最优志愿的边就好了,这样的复杂度应该是O(n^3logn)。

 

T2:林克卡特树(lct)

神题,考场上写了10分之后剩下的就不想写了,最后还挂了5分= =

先转换设问,转化为在原树中选出k+1条点不相交的链,使得选中部分的边权和最大。

这样,我们就有了类似HEOI2017 摧毁树状图的一个O(nk)的DP。

官方题解是这样优化的:设f[i]表示选出i条链的最优解,那么差分f后发现是一个单调减的数组(其实就是说f[i]的斜率单调递减,也就是一个上凸壳)。现在,我们可以画出f[x]-x图像,求出图像上最高点的函数值,但我们并不知道具体的f值。在这种情况下,为了求出最高点的坐标,我们可以二分斜率。为什么要和斜率挂钩?因为我们如果确定了一条直线的斜率k,就有直线f(x)=kx+b,截距b=f(x)-kx,我们可以轻易的求出斜率确定的情况下的截距大小。在斜率确定的情况下,为了求出目前与直线的切点,就需要最大化截距,而截距的实际含义就是:多选一条链需要支付k的代价,同时收益就是所有边权之和,那么我们就可以用一个线性DP来解决这个问题。之后,在求出当前切点后,如果发现横坐标小于K+1就将直线顺时针旋转,反之亦然。最后,利用求出来的最优斜率,再DP一次,求出切点坐标,那么切点的纵坐标就是答案了。

据说这玩意好像就是“王钦石二分”?很久以前达哥出过关于这个的联赛题= =

 

T3:制胡窜(cutting)

码农神题。

说来也搞笑,考场上想写nq暴力发现根本不会,之后写了n^2q也不对,应该算是两天的考试里最大的失误了。

考虑进行补集转换。原问题就转化为了在每个串内至少有一个位置是左/右端点(不能和串的左右端点重合)的方案数。这样,可以大致分成如下三种情况来计数:

1.所有串有公共部分,左端点选在第一个串左边,右端点自己割掉所有的串。

2.所有串有公共部分,左端点割掉所有的串,右端点随便放(可以割在串上)。

3.设共有m个串,[1,i]被左端点割掉,[i+1,m]被右端点割掉(右端点也可以割到前面的)。

前两种情况都可以在知道了串公共部分之后O(1)算出来,最后一种情况需要讨论。

我们首先对原串建出后缀自动机,之后给每个接受态节点开一个treap节点表示在串中出现的位置,之后离线询问,在parent树上倍增定位节点,DFS一次进行启发式合并treap,并在每个节点回答询问。

对于第三种情况,l[i]表示第i个串的左端点,r[i]表示右端点,则答案的式子可以写成这样:

$$\sum _{i=1}^{m-1} [l_{i},l_{i+1}-1]与第一个串的交集大小*[l_{i+1},r_{i+1}]与第m个串的交集大小$$

如果假设所有的串都和第一个以及第m个串有交集,那么答案的式子可以继续变形:

$$=\sum _{i=1}^{m-1} (r_{i+1}-r_{i})*(r_{i+1}-l_{m})$$

这样,我们拆一下括号就可以用无旋treap搞定了。

继续考虑边界问题。我们需要先把满足两个要求的部分都split出来,再加进答案里面,那么只剩下两种小情况了:

1.串i与m无交集,串i+1与m有交集。

2.串i与1有交集,串i+1与1无交集。

显然这两种情况都不会被直接统计到,那我们就分别特判,求出左右端点的可行区间,乘一下就好了。

 

题面(pdf)&官方题解&成绩等比赛资料:
Download

 

 


游记

咕咕咕咕

[Update 26.4.18 开更= =]

Day -1

考了学长们去年这时候做的一套题,但是老吕出锅了把T1模数给弄没了,导致这题根本不可做,全场爆零= =

Day 0

走之前抽签,感谢zyf的随机程序,一下就抽到了我,于是省选两天我就要自己住一间了。

轰炸了一波打印机遭到众人吐槽,之后就滚粗了。高铁上看了会打印的板子,之后开始休(tui)息(fei)。

一如既往地卡着试机的时限赶到了燕大,打了SA、SAM、LCT(flag++),没对拍,不过应该很稳(flag++)。

最后一次来到了燕大食堂,感觉没啥想吃的,于是瞎点了点面和zzh、srs一起吃了。

由于是自己一间,睡的比较早,晚上也很安静。

Day 1

 

Day 2

 

声明:Narcissus' Blog|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - HEOI 2018 | 九省联考 2018 题解&游记


Narcissus | HZOIer | zhuohaoyu1228@gmail.com