sa – Tgotp-Blog

4199: [Noi2015]品酒大会

竟然一遍ac了...万万没想到...

容易想到先求出SA,在hight数组上乱搞即可。。。

那么算某一个r就是区间min>=r的连续一段的组合之和。

考虑算多个r,因为大r肯定包含小r,那么算出了大r最后加到小r即可。

考虑这样怎么算,用单调栈维护一下即可,但是要注意在[......]

Read more

4652: [Noi2016]循环之美

https://www.cnblogs.com/clrs97/p/5731321.html

c++代码如下:

 

3676: [Apio2014]回文串

卡着时限过的…
时间大概是垫底一般的存在把…
容易想到马拉车处理回文串(不过这题大佬都是回文自动机啥的。。。
然后考虑相同的串一定是sa上h数组连续的一段,那么二分左右端点即可.
然后扫一遍就求出了答案
c++代码如下:

[......]

Read more

1692: [Usaco2007 Dec]队列变换

双倍经验题,还有个1640

裸的sa,把字符串倒着再存一次,然后比较每次的后缀与前缀哪一个rk靠前,直接输出即可。

c++代码如下:

 

Infinite Fraction Path

将原本后缀数组的+1看作跳到i*i +1 %n就好了

求的是sa[n -1 ]

注意该题不能向前调到2^k-1必须先处理一次第二关键字。

c++代码如下:

 

3238: [Ahoi2013]差异

辣鸡错误毁我时间。。。

ac与wa的区别。。。

用sa求出height即可,答案即为所有子区间最小值 之和,维护一个单调递增的单调栈。

c++代码如下:

 

Life Forms

思路不难想,求出sa以后二分随便搞搞,和上一题比较像。细节卡死人。。。

注意是大于一半。。。一开始以为是至少一半疯狂wa。。。

然后现在还把用来对拍的程序卡掉了。。。

c++代码如下:

数据生成代码:
[cra[......]

Read more

PHRASES - Relevant Phrases of Annihilation

有点难度的sa,把所有的字符串串在一起,然后分段保证段上有长为x的两个子串

首先求出sa,然后再求出height 数组,然后二分答案,对于每段就枚举height差值不超过二分值得段。

然后记录在每一段出现最早与最晚得值(判断有无两个串),然后判断。

搞定。

c++代码如下:[......]

Read more

1031: [JSOI2007]字符加密Cipher

事实上就是把原本直接填到最前面的[len - k,len - 1]段重新进行比较,发现这一段的第二关键字其实就是[rank[0],rank[k-1]]这一段,找sa的时候判断一下就好了,另外下面离散化的时候也要把x赋值一下。。

搞定。

c++代码如下:
[crayon-5bcea05a[......]

Read more

#35. 后缀排序

sa模板

推荐文章:https://zhuanlan.zhihu.com/p/21283102

先学会基数排序,然后倍增sa就是将倍增的两段分别作为第一关键字第二关键字排序,搞定。

c++代码如下:

 [......]

Read more