ZJOI2017 R2总结

和上次一样先上了两天的课

这次的座位貌似不够。。实际上比上次的少不知道多少。。搬了好多凳子进去

听说座位还是安排过的?233

不过好的一点是有wifi。。速度还不慢。。可以方便参与ZJOI群互动看番

题目解压出来先翻了一下大样例。。嗯这次没少东西

T1汉诺塔?送的\(10\)分先拿上。。好像\(K=2\)也能搞?

似乎按照普通汉诺塔的思想从下往上搞,每次移过去两个就行了。每次分两种情况讨论一下。

那\(K=3\)是不是也差不多啊。。分\(6\)种情况讨论一下?

手推了半天写出了六种情况,然后发现暴力甚至跑不过某个\(n=2\)的数据

想起来好像有大样例啊?赶快测一发

\(K=2\)的对了,\(K=3\)的WA烂

检查了半天好像没有写错。。大概\(K=3\)不能这么做吧。。

两个半小时过去了。。赶紧搞后面的题

T2又来个线段树?好像暴力挺好写的?先写个\(20\)分

后面两个部分分好像都可做?想了想并不蛮会

T3字符串?\(nm\)暴力似乎有\(30\)分?

怎么\(O(n)\)求最小后缀?后缀数组肯定T飞了。。最小表示法?

写写写。。然后突然意识到对于\(121212\)这种数据会挂。。

想了想这似乎是鏼的字符串理论。。好像是最后我唯一听懂的某个simple算法可以求的。。(查证了一下叫Duval算法

好像后面有一档\(50\)还是\(60\)部分分就是给的鏼字符串理论?然而border的那一套理论根本不会呀。。

努力回忆了一下。。似乎是要把字符串剖分成若干叫Lyndon串的东西。。满足每个串的最小后缀都是它自己

并且每一个都不小于后面那个

那么这样好像最小后缀就是最后一个Lyndon串?

努力YY了很久的实现。。记得大概是拿\(3\)个指针跑一遍

YY了很久三个指针表示什么。。最后十几分钟终于得到了一个感觉很靠谱的算法

赶快写写写 测了一发大样例 跑了几秒钟跑出来了 然后对了233

自信提交(反正也没时间了

 

最后貌似T3搞到了60分?

伦切了T2太劲了 全场rk1

看了一发成绩 大概ZJ有\(5\)个比我高的 省外有\(2\)个

考得还算不错吧。。再接再厉

说点什么

您将是第一位评论人!

提醒
wpDiscuz