12.19模拟赛总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
明明什么都没有搞懂就跑来写总结了...
SDOI2015 R2D2
------------------------------------------------------------
T1:
M(i)表示i-1
P(i)表示i+1
用线段树维护一下F[aM(i)±1],F[aP(i)±1],F[ai±1]和两两的乘积什么的,初始值可以矩乘求出来
然后每次都是修改可以把这些都求出来的，然后下放标记是O(标记数)的（其实我觉得这里可以用矩乘做到O(lg标记数)）
据说卡常数..
------------------------------------------------------------
T2:
我写了个爆搜..
然后，标算是分类讨论
把k=2~7的情况都分别讨论出来
------------------------------------------------------------
T3:
哈希~
又是一道卡常题
首先，如果lens=lent,就随便怎么搞一搞
如果lens<lent，就把字符串翻转，然后交换s和t,就变成lens>lent的情况了
好，然后是lens>lent的情况
首先把t都哈希了丢到哈希表里面
然后把s分成两节l和r，分界线是mid=(lens+lent)/2
令len=(lens+lent)/2
可以预处理出l中以每个位置开头，长度为len，循环的哈希值（倍长一下就好）
然后把r哈希了
然后去枚举l中每个位置，看以这个位置开头，长度为len，循环的字符串是不是以r为前缀，如果是的话，就去掉这个前缀，把剩下的部分拿到哈希表里面去询问，统计次数，累加就行了。
另外由于数据太水了，某看错题的同学表示旋转视为可以旋转任意前缀也可以A，另外数据全是lens=lent的情况，按这个写可以300+b A掉（不要问我怎么知道的），太特么坑了
------------------------------------------------------------
评论 (0)
