牛客IOI周赛19-提高组
相信大家在这次比赛中获得了很愉(zi)悦(bi)的体验。
T1
题意十分明了..
考虑辐射,我们可以用一次Dijkstra找到每个点最近的基站,记录下距离dis[i],from[i]表示与这个最近基站的距离与这个基站的编号.
对于一条边(u,v,w)来说,若from[u]和from[v]不相同,那么我们就从from[u]向from[v]连一条新建的边,权值为w+dis[u]+dis[v].
然后由于要最长路径最短,可以想到最小瓶颈生成树,那么我们跑一遍kruskal,最大的边权就是所求的答案.
为什么这样连边是对的?可以考虑一个类似病毒传播或者辐射的图,对于两个没有在新图上有边的基站,它们要么存在于两个联通块,要么就是中间有中转站,很容易证明.
T2
找一个区间翻转使非空最大子段和最大
承认很多人用一种类似贪心取最大子段和的方法水过了这题,出题人在此谢罪,但是本身这题也放了80的暴力分,所以对得分梯度没有太大影响
区间翻转之后,能产生更优解当且仅当翻转之后两段拼接成了一段,所以我们找的就是环上最大子段和.
这个在序列上预处理一下前后缀的最大子段和,拼起来就可以了,因为在环上,所以也可以是总和-最小两段子段和.
T3
这题标准时间复杂度O(nw+wlogw)
当然出题人良心把O(nwlogw)也放过去了.
还是十分明了简单的,要求了两条路径不相交,容易想到必定存在一个子树满足,这个子树内有一条路径,而另一条路径在子树外,具体证明可以考虑lca较深的点必定是一个这样的子树.
我们可以把一条路径看作成两个点到根的边权异或和的异或和.那么问题就转化为了在子树内找两个点,在子树外找两个点,使异或和最大.可以考虑转化为dfs序.
问题就转化为了在两个区间内各选两个点异或和最大.这个问题可以用fwt解决,我们可以先把每一个点的fwt数组求出来,然后预处理一下前缀的fwt数组和,每次就是减一减得出两个区间的fwt数组,乘起来,平方,然后再IFWT回去,找值不为0的最大位置即可.
这样就是2nwlogw的做法,考虑到每一个点的fwt数组可以O(w)处理出来的,具体方法建议重新学一下FWT.也不用每次IFWT,把它加在一起再IFWT回去就可以,具体为什么建议重新学一下IFWT.