CF1582F

F1 是个弱智 (O(nV)) dp。

到了 F2 就有点牛逼了 (n)(V) 同时扩大了 10 倍

场上只顾着调 D 题,也没继续想。

后来自己再做的时候,开始胡了个假的结论

对一个数只需要保留最先出现的和最后出现的位置即可

然后照着这个结论还过了 80 多个点……

事实上,在 F1 中,我们是将最后一个数的大小存到对应的异或序列上来比较大小。在 F2 中可以考虑一个数会在序列中多次重复出现,而我们每次都 (O(V)) 扫一遍异或数组似乎有点亏,我们只考虑对一个数能不能直接维护都有谁可以被它异或。这只需要维护一个 vector 以及一个指针即可

F1:代码
F2:代码

原文地址:https://www.cnblogs.com/-Iris-/p/15484624.html