26.5.18 考试小记

发布于 2018-05-27  1.63k 次阅读


OI赛制,部分分给的档次比较多。

T1

给定一个长为n(<=1e6)的序列,每次可以修改一个元素,求每次修改后,给每个数xor上一个数x,使得整个序列单调不减的最小的x。

考场上写的n^2logn的60分暴力,其实还是每个数位进行贪心。

正解是将序列拆成n-1个限制,限制相邻两个数最高的不相同的二进制位,且这些限制都必须满足,这样只要维护一个数组就好了,复杂度O(nlogn),好像可以通过位运算优化到线性。

 

T2

给定一张n个点的有向图,有m条车线经过这些点,每条车线经过相邻的点都有不同代价,求在满足1~n的距离最短的同时的最大的权值的平方和。权值定义为在一条连续的车线上的花费之和。

考场上写了个最短路DAG上的暴力DP,具体就是先把边反向,之后跑最短路,然后从1开始DFS,按照拓扑逆序搞,先算完后继然后更新当前点,即可保证运算顺序,之后暴力枚举所在的链,复杂度O(n+s^2),期望60,但是SPFA的vis标记忘了清空,于是挂了10分(这居然还能有50分)。

正解就是通过利用斜率优化去掉一个s,具体就是:设f[i]表示从1~i走最短路的最大权值,\(f[i]=max{f[j]+(dis_{i}-dis{j})^2}\),可以将新的f[i]看作截距,将只和j有关的看作y,剩下的看作斜率k,那么我们计算时,横坐标单调递增,于是可以维护一个上凸壳,按照拓扑正序计算,每次用当前点更新能更新到的后继节点,同时把对应的栈继承过去。由于一条车线上可能有多条连续的链满足要求,我们在每个点时,如果发现某一条车线没有栈那么就新建一个就好了,具体可以看代码。

 

T3

给定一个长为m(<=3e5)的01串,以及n(<=3e5)个01串,n个串的长度和<=3e5,后n个串每个串有不同的权值,求将序列划分为任意段,其中每一段要求是n个串中某一个的前缀或者后缀的最小权值。

考场上写了数据分治,对于n比较大的测试点,每个串长度一定很小,于是放进哈希表里,转移的时候查询最小权值同时查不到就退出。如果n比较小每个串都比较长,那么就用线段树优化DP。注意由于前后缀的连续的性质不太相同,所以要分开处理。这样总共获得了70分。

正解其实就是这个,只不过是把长的串用线段树转移,短串放进哈希表或者trie树(后者常数小很多),然后就可以通过了。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974