12.19模拟赛总结

明明什么都没有搞懂就跑来写总结了...
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掉(不要问我怎么知道的),太特么坑了
------------------------------------------------------------