OceanEye's Blog

是时候表演真正的技术了!

@OceanEye6月前

08/14
15:59
OI

BZOJ1031 [JSOI2007]字符加密Cipher

嗯这题不是权限题 很友好
SA裸题
把原串复制一遍接在最后面,跑一遍SA
只需要把SA中在[1,len]范围内的放入答案数组就好了
写得比较直接……就比较丑,各位见谅

BZOJ1031 [JSOI2007]字符加密Cipher

@OceanEye7月前

08/9
21:10
OI

XSYOJ 1133 兔子的字符串

题面大意是:
给一个长度为N的串
\( N \leq 100000 \)
最多分割k次
问若干分割方法中
字典序最大的子串最小是什么

问了一下ZJT大佬……
原来是建出SA之后
先二分后缀
后二分长度

有一些细节要注意,除此之外就很simple了

XSYOJ 1133 兔子的字符串

@OceanEye7月前

08/8
11:12
OI

BZOJ4278

4278: [ONTAK2015]Tasowanie

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 434  Solved: 203
[Submit][Status][Discuss]

Description

给定两个数字串A和B,通过将A和B进行二路归并得到一个新的数字串T,请找到字典序最小的T。

Input

第一行包含一个正整数n(1<=n<=200000),表示A串的长度。
第二行包含n个正整数,其中第i个数表示A[i](1<=A[i]<=1000)。
第三行包含一个正整数m(1<=m<=200000),表示B串的长度。
第四行包含m个正整数,其中第i个数表示B[i](1<=B[i]<=1000)。

Output

输出一行,包含n+m个正整数,即字典序最小的T串。

Sample Input

6
1 2 3 1 2 4
7
1 2 2 1 3 4 3

Sample Output

1 1 2 2 1 2 3 1 2 3 4 3 4

HINT

Source

[Submit][Status][Discuss]
 

把两个串前后拼在一起 然后用SA处理出rank数组跑归并

中间插一个大大的分隔符就好

听说有姿势奇怪的贪心?【难道是某种神奇的哈希……】

现在不是很想理……

代码

 

BZOJ4278

@OceanEye7月前

08/6
21:44
OI

后缀数组学习笔记

学习地址的传送门
当然要看我的也是资瓷哒qwq

0x00

前置知识
SA是所有的后缀的排名
\(sa[i] = the i^{th} suffix’s position \)
rank是某后缀对应在SA中的位置
\(rank[i]= find_pos(sa.begin(),sa.end(),i) \)
height是求完SA之后 相邻排名的后缀 最长公共前缀的长度
\(height[i]= lcp( suffix[i] , suffix[sa[rank[i]-1]]) \)

个人认为最难理解的就是双关键字的桶排序……【其实还算好理解?】
menci大佬的实现是先把第二关键字整理成有序的
\( tmp[len- –buc[sec[i]]] = i \)
操作之后tmp就是按照第二关键字排序的一个数组
接下来把第一关键字占的位数存进桶里面
再用tmp这个第二关键字的有序队列 【这个队列是倒着的 是倒着的 是倒着的】
结合第一关键字的桶 可以推出新的SA
最后用SA数组来推出新的rank数组
\(
if(last==empty) rank[sa[i]]=1
\)
如果是第一个那么rank必定为1
\(
if(last->fir==i->fir /and last->sec==i->sec) rank[sa[i]]=rank[last]
\)
如果第一第二关键字都相同那么排名相同
\(
rank[sa[i]]=rank[last]+1
\)
否则依照SA顺序名次+1
//更新last

建议看第二个模板
模板没有注释
需要完整的解释……请跳转至menci的博客【传送门在上面】

没有height只有sa和rank的

 

这个是有height,sa和rank的

后缀数组学习笔记