NOI2015湖南集训

7
2
2015

day1

被虐傻。

A根本没往回文自动机上想，学了还不想真是有些结论还是不敢大胆的猜QAQ

B根本没往LCT上想，好吧我的锅。显然如果与LCT联想起来的话就是道傻逼题。~~就是不知道考场上能不能写出LCT~~

C出的有点儿慢。刚开始一直在想二分什么的，然后又在想能不能搞出一个二维的前缀权值线段树。事实证明我想多了

后来才注意到k这么小一定有鬼，那就是和超级钢琴差不多的做法了，然而。。。。用优先队列和setT掉了20分。还能不能和$STL$愉快的玩耍了啊

UPD：A的话首先需要注意到其实只要求出所有的回文串最少需要多少次能得到就能得到最后的ans,然后所有的回文串又很容易联想到回文自动机。然后再dpdpdp上午脑袋是不是进翔了只需要求回文串的答案者很显然是正确的但是如果没有往这方面想也是做不出来

晚上和TKD看了一晚上红枣切片机感觉节奏不对啊

day2

看到A题就想肯定是回文自动机，昨天刚考今天又考

想的是先用PAM求出所有本质不同的回文子串，然后来个~~马拉车~~manacher，因为中心是确定的，然后给最外层的那个字符串打个标记然后一路沿着fa上传上去即可。然后发现找到最长的回文串在PAM中对应的节点不太好搞。先开始写了个fail树上的倍增，发现会T心一狠换成暴力。结果快的飞起当然这样复杂度是没保证的，并不能均摊。后来讲题的时候忽然发现我们直接hash就好了

B题感觉好困难的说，5000W的数据std居然带个log仿佛在刻意逗我笑。我看到这个数据范围就虚的不行，感觉带个log根本不行，也就没有想O（logn）的转移，一直想怎么搞到O（1）。然而无果无奈直接选附近的100个点更新dp值！下来居然有60

C题看完题目弃疗。好难啊。讲题的时候发现如果是棵树的话我做过这题啊当然是转化之后的。。。

day3

CJ出题这么照抄原题真的好么？

A题CF#300E

B题傻逼KD-tree或者树套树跪树爷

C题逗比之星初赛第二场租最后一题

下午好像是停课以来第一次运动

妈蛋暑假减肥~~8月10号开学你还有暑假么~~

day4

今天真是跪惨了

A题强行把两道题凑到一起，第一题平衡树随便做，比较新奇的是RHL大神的线段树做法，时光倒流即可。有的时候能写线段树就写线段树，因为线段树写的最多不容易出错。第二题的话其实就是个凸包，然而因为插入是单调的所以直接插就行了我比较二写了个CDQ，下来发现被艹成傻逼。幸好评测机跑得飞快，本机3s一点儿也不虚。

B题一直yy了半天的分块结果无果，因为求一个前缀和都是求不出来的。。。妈蛋居然是找规律题。把$S（n，m）$的值打出来发现是个乘法表应该往这方面想的，答案一定不会复杂，因为这个范围也就求个n和m的欧拉函数QAQ 推导的过程其实也值得思考，感觉数学题还是不太知道该从哪里下手TATAQQQ。这题就是把一个复杂的式子变成了一个暴力的求和然后就是喜闻乐见的套公式什么的了。以后一定要打表！