当前位置：网站首页>[2022/6/29]考试总结

[2022/6/29]考试总结

2022-07-18 17:59:00 【迷蒙之雨】

先看T1，感觉比较可做，口胡了一个后缀树上四维莫队套线段树的做法，感觉可以冲一下。

发现T1看错题了，于是去看T2.
感觉可以二项式反演，然后预处理一些dp就有 $O(n^3)$ 了，然后再用多项式加速到 $O(n^2logn)$
这样就有60pts了。

重新回去想T1，发现只要建出后缀树然后贪心地匹配就行了，就有50pts了.

T3有个很显然的 $O (n T)$ 的dp，但是是从x出发的，所以倒着dp就行了。

这个Dp显然可以用矩阵乘法加速，但是矩阵乘法是 $O(n^3)$ 的，猜了一下感觉有值的位置不会太多，然后就开始写，写了一会觉得不对，然后就假了.

版权声明
本文为[迷蒙之雨]所创，转载请带上原文链接，感谢
https://blog.csdn.net/jwg2732/article/details/125523696