回文树

久违的学一点点东西得了。。。

简而言之

回文树是一种用来处理回文的自动机,可以处理一个字符串中的所有不同子串

指路论文:https://victorwonder.blog.uoj.ac/blog/146

Read more
2022 winter training 1-H

摆了,但是没有完全摆

CF103495H

H. Reverse the String

给定长1e5的字符串,你可以翻转其中一段连续子段,问能产生的字典序最小的字符串是啥

据说可以用SA写,我是没啥思路,题解是hash,就这样补了

Read more
鸽巢原理

内容

鸽巢原理及其一些推论,包括但不限于

  • 简单形式
  • 中国剩余定理
  • 加强形式
  • Ramesy定理
  • 呃呃
Read more
Goodbye 2021

2021年就这么结束了,不管是失败还是悲伤还是焦虑,亦或者是欢乐还是欣喜还是怀念,都已经过去了。

可能会写点文字来怀念?

不过现在应该做的事情只有一件

补题。

Read more
sam相关

学完了这阴间玩意肯定得知道这玩意怎么用吧

sam理论上可以

  • 子串endpos大小
  • 子串endpod位置
  • 在后缀link上跑dp
  • 在自动机上跑dp
  • 统计有多少个子串经过一个点
  • 二分
Read more
后缀自动机

这玩意就是SAM的原理以及基本板子了,大概,说不定再来一点套路总结吧

总的来说,这玩意拖的也太久了,一直说要学,然后狂摸不止,我 有罪

欸嘿

Read more
维护区间众数

这玩意好像方法挺多的,然后今天被一个阴间东西坑了,来说一哈

其实就是给一个数列,然后给一堆询问,问你区间众数是多少吧

Read more
hexo博客搭建教程(?

有咩有一种可能,这玩意是写来总结一下当时搭博客是有多么折磨的一件事的捏

介绍一下怎么用hexo搭建博客并部署

Read more
单调队列优化多重背包

补题补到了个树上背包,然后发现孩子不会。这次就打算把一些该学的背包都学一手?大概。

  • 我们知道,对于多重背包,有一个二进制拆分优化,可以在O(vlog(n[i]))O(vlog(\sum{n[i]}))级别的复杂度解决问题
  • 然后单调队列优化可以跑到O(nv)O(nv)
Read more
Gym103389F 地图压缩

训练的时候一看题目长的一批就根本没看,现在看看发现还是可做的啊。。

题目简述

给定一个n*n的矩阵,q次询问,每次给定一个矩形范围,问一个最小矩阵的面积,可以通过此矩阵循环覆盖给定的范围,多出的部分可以不计
例如:ababa可以通过ab循环构成

Read more