等级
TA的排名 17w+

最小回文分解NlogN算法

本文翻译自这篇论文 译者水平有限,如有错漏,还望指出 论文中有伪代码可以帮助理解 众所周知,字符串的border有和等差数列相关的一些性质(border group),可以参考2015年集训队论文集里的《浅谈字符串匹配的几种方法》一文,回文串的回文border也有类似的性质。tips: 真后缀定义类似真子集下面给出算法所用到的几个引理 引理1 令y为回文串x的后缀,y是x的bo...

2018-04-12 16:34:29

一些常用define

#define rep(a,b,c) for (int a=b;a<=c;a++)#define per(a,b,c) for (int a=b;a>=c;a--)#define go(u) for (int o=ft[u],v;v=E[o].t,o;o=E[o].n) // forEdge#define fi first#define se second // pair#d...

2018-02-15 10:21:55

STL 常数测试(粗略)

vector - 手写链表预处理log - math库logvector - 手写链表vector和手写链表的时间对比 push_back时间如下 .. 不开O2 开O2 vector 8s 6s 手写链表 4s 4s遍历一次的时间都是2s 详见代码#pragma GCC optimize(2)#in...

2018-01-25 14:21:19

Min_25筛代码

Sn=∑i=1nfiSn=∑i=1nfiS_n=\sum_{i=1}^nf_i Fn=∑i=1n[i为质数]fiFn=∑i=1n[i为质数]fiF_n=\sum_{i=1}^n[i为质数]f_i Sn,k=∑i=k∑j=1[n≤pj+1i](Snpji,i+1fpji+fpj+1i)+Fn−Fpk−1Sn,k=∑i=k∑j=1[n≤pij+1](Snpij,i+1fpij+fpij+1...

2018-01-24 18:43:21

NOIP2017总结

学文化课使我快乐O(U_U)O

2017-11-15 22:26:00

BZOJ八月月赛题解

RT

2017-10-02 00:42:23

纪中八月五号到二十五号集训总结

回到家一个人真是无聊,只能总结一波然而晚上没弄完。。

2017-08-26 14:06:49

记录一下

LCTSAMFWT2-sat tarjan缩环Matrix-TreeBurnside,Polya二次剩余Cipolla算法多项式插值求值Min_25筛kosaraju算法拟阵与贪心好用的编辑器草稿纸草稿纸^{_{_{草稿纸}}}: typora自适应辛普森积分minHash四边形不等式min25阶乘模大质数OldDriverTree(ODT)扩展BSGS...

2017-07-24 16:41:37

【JZOJ2702】探险

一道不错的最短路题?

2017-07-22 20:54:05

动态的树链剖分

UPD 18/1/25假的假的!今天突然发现漏掉了细节,暂时想不到解决方法,这个算法凉了不过用启发式合并去重构小LCT应该不用换根了,但不知道复杂度会不会出问题--------------------------------------------------这里的技巧可能没你们想的那么强大。。但我之前也没听过这样用的,觉得可以拿来说一说在各个LCT维护的题中,有些题目不需要cut操作,其实有cu...

2017-07-18 11:40:31

纪中5号~16号集训小结

啦啦啦

2017-07-17 10:33:23

SAM模板

SAM真短

2017-07-14 07:32:06

三道NOIP(?)巧题

C_SUNSHINE 出的NOIP题好妙啊

2017-07-10 19:35:51

LCT模板

LCT真难调

2017-07-09 21:54:24

GDOI2017滚粗记

滚粗记

2017-04-18 09:46:24

网络流模板(费用流/可行流/上下界)

终于来写博客了= =一般的最大流算法:dinic          博主只会这个大概就是先bfs分层,在增广的时候只走跨层边加当前弧优化好像快10倍左右,加的时候小心点,容易错应该只有我会写成暴力吧struct edge{int t,f,n;}E[M];void add(int x,int y,int f){ E[++tot]=(edge){y,f,ft

2017-04-07 15:53:05

GDKOI2017酱油记

考试过程DAY1因为监考老师不给提前碰键盘,就只能坐等比赛开始了其实我是感觉很爽的,因为我没板子可敲解压密码:zha.xi.de.le~       虽然场上还不知道什么意思但讲题的时候还是感受到了出题人的善意=w=发题后大概30分钟读完题目,出题人并没有把水题藏后面,于是从第一题开始做第一题想了一会儿,觉得从人开始宽搜炸弹就会好写些因为这种题我认为不太适合对拍

2017-02-20 19:13:22

非旋转treap模板

先挑个好讲一点的试试,原理什么的我最多一句带过就算了你问我无旋treap的原理?我只能回答你一句无可奉告我学这个东西的时候,想找别人的代码看看看到别人写得那么长,就自己写了下然后,就写成现在这样了----------------------------------------------------------------------------------#defin

2017-01-24 11:35:01

短期计划,周更

我相信我一定能完成的(ง •_•)ง2017/9/21matrix-tree 定理bzoj4126国王奇遇记bzoj八月月赛  9/92017/10/2炫酷反演魔术-VFKCM-二项式系数2017/10/21集训队作业 21/1042017/11/1支配树2017/12/7??月更的我应该还有救VP一场bzoj12月月赛复习:splay,ac自动机,后缀自动机,LCT,网络流2018/2/10点分...

2017-01-23 22:47:15

CV1873 树的点分治

题解:    什么情况点i会对点j做贡献?在i~j路径上的点中,点j最先被选中,概率是dis(i,j)+1    答案=∑{1/[dis(i,j)+1]}              i,j    点分+FFT算出距离为1~n的点对数即可    (你见过像我这样缩行的吗?)AC code#include#includeusing namespace std

2016-12-13 14:10:24

查看更多

勋章 我的勋章
    暂无奖章