OceanEye's Blog

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

@OceanEye5天前

08/14
15:59
OI

BZOJ1031 [JSOI2007]字符加密Cipher

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

BZOJ1031 [JSOI2007]字符加密Cipher

@OceanEye1周前

08/9
21:10
OI

XSYOJ 1133 兔子的字符串

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

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

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

XSYOJ 1133 兔子的字符串

@OceanEye2周前

08/9
11:04
OI 模板——如果有哪里不对的请打死我

替罪羊树【复习向】

这是新坑……
同时开了KDT和LCT的坑【不知道的同学等下就知道了】

0x00

绝大多数的平衡树维持平衡是通过旋转操作
Merge_Split_Treap 是通过分裂合并维护堆的性质保持理论上的平衡
今天讲的替罪羊树是用来暴力维护子节点重量平衡的

0x01

某教程的传送门
另一个教程的传送门
这两个教程里面的说明都很有意思,可以看看

0x02

替罪羊树最神奇的地方就在于他的暴力重建
而且这个暴力重建是有时间复杂度保证的【势能分析那一套理论不是很懂,需要证明的可以去翻翻之前陈老师的论文】
保证每种平衡树的操作的时间复杂度在\(O(logN)\)的范围

替罪羊树还有一个小技巧
就是拍扁重建法
重建的时候先dfs把所有数放进一个数组,重建每一层递归都把mid拿出来当father即可
时间复杂度是O(size)的

最后讲的是替罪羊树的删除
因为这个树是没有旋转的
不能把它某个节点旋转到叶子然后把叶子节点删掉
所以用的是惰性删除
在删除的时候 打一个删除标记 表示“这个点被删除了 以后查询的时候直接跳过”
若一个子树内的惰性节点超出了某个范围【比如\(size*0.45\)】直接暴力重建

注意:
重建的时候带有删除标记的节点不能入数组
重建的两个条件
1.子树深度大于某个阈值 或 子树大小大于阈值 【实际上是等价的?】
2.子树内带有删除标记的节点大于阈值

0x03

代码
这份过了编译【就是不保证完全正确但是思路是对的】
状态好了来认真写一份……

替罪羊树【复习向】

@OceanEye2周前

08/8
21:55
OI

Link Cut Tree 学习笔记

先上一份代码……回去研究研究 @Sdchr

 

Link Cut Tree 学习笔记

@OceanEye2周前

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

@OceanEye2周前

08/7
16:03
OI

Miller_Rabin 素数判定

0x00

Miller_Rabin 素数判定
为什么要写这个……因为我把它忘掉了
于是写篇文章复习复习……

0x01

基础知识:

费马小定理

\(a^{n-1} \equiv 1\pmod n\)

伪素数

如果n是一个正整数,如果存在和n互素的正整数a满足 \( a^{n-1} \equiv 1\pmod n\),我们说n是基于a的伪素数。如果一个数是伪素数,那么它是素数的可能性很大

Miller-Rabin测试

不断选取不超过\(n-1\)的基\(b\)(\(s\)次),计算是否每次都有\( b^{n-1} \equiv 1\pmod n\),若每次都成立则n是素数,否则为合数。

快速幂

这是基础知识……

快速乘

快速乘是在模意义下的乘法
具体来说就是a*b%c超出限制的时候用的 , 用了位运算的技巧
代码如下

0x02

上面有了伪素数的定义……那么我们可以用一些朴素的方法来验证素数
比如……我们随机几个数然后跑跑

大概每次筛正确的概率是 \( frac{3}{4} \)

0x03

然后讲一个不是那么的平凡的优化
因为 \( a^{n-1} \equiv 1\pmod n\)
所以 \( a^{frac{n-1}{2}} \equiv 1 \pmod n\) 或者 \(a^{frac{n-1}{2}} \equiv 1\pmod n\)
如果使用的话可以提高该算法的效率

参考以下的代码

Miller_Rabin 素数判定

@OceanEye2周前

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的

后缀数组学习笔记

@OceanEye2周前

08/5
16:12
OI 日常

心情复杂

近来的训练暴露了很多的问题

我已经不会打暴力了

可能是OI比赛玩少了,就不会打暴力了?

但是更心寒的是我的知识点的欠缺

一下是待补的坑:

LCT

SA

数学姿势

DP优化姿势

考试的姿势……

心情复杂

 

心情复杂

@OceanEye2周前

08/4
15:27
OI 日常

8.4 小测1

题目放出来不是很好……就不放题目和代码了
稍微记录一下考试时候的一些记录
T1

dp[i][j][0/1]

pos : i
cnt : j
Connecting : 0/1

可以留意到最大字典序的子串一定包含了答案
而且一定是从开头包含
可以考虑利用这一点瞎搞
比如我们二分它这条最长串的长度,之后尝试构造?
这里的构造是我们要造出最大串是二分得到串的,且个数尽量小
可以考虑用kmp解决
kmp 匹配之后 在匹配结束的地方砍一刀
没有匹配就继续
这样子就是nlogn的

但是怎么找到最长的子串还是个问题……
我想到的是用SAM
好烦啊不想用SAM啊

T2
F(0,n) = n+1
F(m,0) = F(m-1,1)
F(m,n) = F(m-1,F(m,n-1))

打个表找找规律吧
日哦……真的烦

有点像是

F[0,n]=n+1
F[1,n]=n+2
F[2,n]=2*n+3
F[3,n]=F[2,F[3,m-1]]
F[3,0]=2+3
F[3,1]=4+3*(1+2)
F[3,2]=8+3*(1+2+4) = 29
F[3,3]=2*29+3

打完表
应该是30分
回去看T1
思路没什么错……就是代码量比较大

 

T3还剩五十分钟看出来是一个树链剖分套四tag线段树

mdzz码农题写个皮皮虾

Read More →

8.4 小测1

@OceanEye2周前

08/3
11:38
OI

BZOJ1367 [Baltic2004]sequence

 

1367: [Baltic2004]sequence

Time Limit: 20 Sec  Memory Limit: 64 MB
Submit: 1346  Solved: 550
[Submit][Status][Discuss]

Description

Input

Output

一个整数R

Sample Input

7
9
4
8
20
14
15
18

Sample Output

13

HINT

所求的Z序列为6,7,8,13,14,15,18.
R=13

Source

[Submit][Status][Discuss]
这题很神……左偏树论文题 百度文库有论文【之前我的左偏树也有挂过】
论文看不是很懂的可以去看看徐姥爷的题解
打错一个下划线wa N次,心痛一波ac率

BZOJ1367 [Baltic2004]sequence