24.5.18 考试小记

发布于 2018-05-24  3.02k 次阅读


IOI赛制。

T1

裸的三维偏序,但n<=2e6,且三个权值均不重复。

CDQ+BIT可以获得60分,但是正解必定是一个log的复杂度。

考虑容斥,若只考虑两维限制,加起来就是满足要求的数对贡献了三次,其他的贡献了一次,所以减一下即可。

 

T2

码农题,给出一个字符串,支持从前后插入字符,每次查询一个串变成另一个串过程中出现的所有回文串在序列中出现的总长度之和。

看到这里一定是要写回文自动机,每个点的贡献就是right集合大小乘上自身的长度。如果不用支持插入,那么每次只要先定位到两个串在自动机上对应的节点,之后两点路径上的信息和就是答案,如果在到达LCA之前就可以相等那么不能加LCA的信息。

考虑支持加入操作,我们可以先离线把整个串建出来PAM,之后对于反串,其PAM的形态一定和正串的相等,于是我们可以把反串拿上去匹配,找到对应位置,也可以直接利用插入操作,因为每次都会定位到之前的节点而不是去新增转移。然后,对于每一次加入,只需要考虑一个端点在加入的位置,另一个端点尽可能长的串就好了,同样利用点定位求出来,然后就做完了。

时间复杂度\(O(nlog^{2}(n))\),试着换了下代码风格,感觉空格多了看着清晰一点,但是写的时候好费劲。

 


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