7.15 ZROI-DAY2 模拟赛

比赛历程

早上起的比较晚，于是拿了两个蛋挞随手塞了一个蛋糕就进去了。

开题之后感觉有些难。实际上每次模拟赛遇到难题，如果不是休息非常充足，思考的过程中就会犯困，见简单的来说放弃了思考。

然后我就困了，想着延续上一场的策略，想了好久的T1，想了点假做法，实现时发现其实根本不会，感觉有点完蛋，T2看上去是字符串，还子串子串的，肯定是SAM！然后我就敲了个SAM板子上去，然后我就呆滞了，想暴力也想不到，菜。下边去看T3，发现题目非常的绕，由于被前两道题搞得神志不清，所以有些抵触。这个时候是两个多小时，旁边ztw已经过了小数据了，那看来T3还是可做的？于是徘徊了好久终于还是开始写T3，写了会儿发现这个模拟还是OK的。最后一小时猜想有没有循环节，然后尝试实现了一把，最后还是没有调出来，感觉有点糟糕。结果上期望得分只有30....

赛后发现

最后抱玲了。

下午代老师的讲课果然也没听懂。但是看题解的感觉是，没有什么陌生的算法的样子，每道题都有自己的搞法。当然T2也是个数据结构，后缀树其实没写过。

技术总结

T1

正解写的挺，妙的。。但我还没懂。

T2

建好后缀树上之后在后缀树上处理一些东西。也没懂。

T3

我非常想说我懂了，不过感觉没有领会到精髓，这种思维模型转化题就没会做过。想象一条线，每次经过一个横线就上翻，每次经过一共竖线就右翻，假设a>b,那么每次至少右翻(leftlfloordfrac{a}{b} ight floor)次，然后上翻一次。那么可以把他们结合在一起，类似欧几里得算法的，每次处理这么多右翻和一次上翻，类似矩阵的快速幂，这个也可以快速幂，就是方向指针和指针上的cnt多做几次这样子，然后让a%=b，缩小数据规模，这个时候一定是b大，那么先上翻再右翻即可，最后剩下来的那个没有变成1的，比如说gcd(a,b)做下来，b!=1,那么就做(b-1)次up操作让他下来，复杂度就是欧几里得算法的复杂度再乘一个log。