- 博客(112)
- 收藏
- 关注
RSS订阅
原创 [成长] 你好，世界
Hello World!为何写博客？ 一千个写博客的人，就有一千个哈姆雷特。每个人写博客都有着不尽相同的目的。 至于我开始写下这些文字，是源于以下几点 积累 每天将自己的所学、所感记录下来，让它在时间的浸润下慢慢沉淀。也许当某日回首，蓦然发现自己已经经历了很多，很多… 分享 还记得自己是一个小小白的时候，来到CSDN，这样一个充满着大神的地方...
2017-08-06 15:12:42
859
4
原创 HIHOCODER 1465 后缀自动机五·重复旋律8 后缀自动机
更好的阅读体验 Press HereProblem传送门 ＞ω＜题目大意：给定模式串 sss ， nnn 个匹配串 stristr_istri求每个匹配串的循环同构能够匹配的子串总数Solution求循环同构的匹配，首先第一步应该是将匹配串倍长，再进行匹配，这样就能得到匹配串所有循环同构但是发现一个匹配串的循环同构可能会相同，而不能计算重复的匹配如何实现？对于每个匹配串的每个...
2018-09-18 14:35:59
334
原创 HIHOCODER 1457 后缀自动机四·重复旋律7 SAM
更好的阅读体验：Press HereProblem传送门 ＞ω＜题目大意： 给定 nnn 个由 0−90−90-9 组成的数字串，问本质不同串的总和是多少Solution含有一个串设 cnt[x]cnt[x]cnt[x] 为 xxx 状态包含的子串数量 若状态 x,yx,yx,y 有转移 ch[x][c]=ych[x][c]=ych[x][c] = y ，则 s...
2018-09-14 21:23:41
346
原创 SPOJ LCS2 Longest Common Substring II SAM
更好的阅读体验：Press HereProbelm传送门 ＞ω＜题目大意： 给定 nnn 个字符串 ，求其最长公共子串的长度1≤n≤101≤n≤101\leq n \leq 10 1≤lenth(s)≤1000001≤lenth(s)≤1000001 \leq lenth(s) \leq 100000Solution看起来很难，实际上非常暴力的题设最长公共子串长...
2018-09-14 13:17:44
212
原创 SPOJ LCS Longest Common Substring SAM
更好的阅读体验：Press HereProbelm传送门 ＞ω＜题目大意： 给定两个字符串 sss , ttt ，求其最长公共子串的长度1≤lenth(a),lenth(b)≤2500001≤lenth(a),lenth(b)≤2500001 \leq lenth(a) , lenth(b) \leq 250000Solution既然要求最长公共子串，能够保留所有子串...
2018-09-14 13:15:36
181
原创 BZOJ 2726 [SDOI2012] 任务安排
更好的阅读体验 【Press Here】Problem传送门 ＞ω＜题目大意： 按顺序给定 nnn 个子任务，每个任务用时 titit_i ，费用系数 fifif_i 连续的多个（一个）子任务合成为大任务，大任务的用时和费用系数为所有子任务之和，启动一个大任务需要时间 SSS ，每次进行一个大任务，其费用为 结束时间 * 费用系数 ，问最小费用为多少（大任务也要按照先后顺序进行）...
2018-09-14 12:59:11
262
原创 BZOJ 2434 [NOI 2011] 阿狸的打字机
更好的阅读体验 Press Here AC自动机 可食用最佳练手题题意有三种操作 * 在字符串的末尾加入小写字母 * 删除字符串末尾的字符 * 将当前字符串输出（不删除）问第 xxx 个输出的字符串 在第 yyy 个输出的字符串中出现了几次Solution当然直接暴力是没有问题的 存下第 xxx 个输出的字符串 然后用 KMP 优化匹配 时间复杂度可以达...
2018-09-14 12:57:05
119
原创 BZOJ 2035 [2009国家集训队]数据读取问题
更好的阅读体验 Press Here 忽然没有了改题的欲望，我已经是一条咸鱼了单链将其转化为图论模型对于位置为xxx的点，向 x−1x−1x - 1 ， x+1x+1x + 1 连边，表示能到达 xxx 的点能够花费 111 的代价通过 +1/−1+1/−1+1 / -1 而转移到 x−1x−1x - 1 ， x+1x+1x + 1 同时向 x+a[x]+1x+a[x]+1...
2018-09-14 12:55:25
212
原创 51NOD 1601 完全图的最小生成树计数 Trie
更好的浏览体验 Press HereProblem传送门 ＞ω＜题目大意： 有 nnn 个点，每个点权值为 a[i]a[i]a[i] ，两个点连边费用为 a[i] xor a[j]a[i] xor a[j]a[i]\ \ xor\ \ a[j] ，问 最小生成树的边权和 andandand 方案数...
2018-09-14 12:53:04
234
原创 KMP算法详解
直接进入正题定义 nxt[i]nxt[i]nxt[i] 为 t[0]−−t[i−1]t[0]−−t[i−1]t[0] -- t[i - 1] 中前后缀匹配最长长度，即，有最大长度为 nxt[i]nxt[i]nxt[i] 的相同前缀后缀， t[0]−−t[nxt[i]−1]t[0]−−t[nxt[i]−1]t[0] -- t[nxt[i] - 1] 分别和 t[i−nxt[i]]−−t[i−1]...
2018-09-04 16:26:43
218
原创 动态树杂谈
摘要 动态树，一类用来维护森林连通性的数据结构，主要使用Splay来维护偏爱点/边(Preferred child/edge)，并且通过点在不同Splay中的移动提取路径，或者是修改父子关系以连接或断开树边动态树的构建动态树由于其需要动态的修改点/边关系，所以需要动态的维护点/边，从而选择偏爱点/边而不是像树链剖分中使用轻重点/边，同时需要Spaly维护每个Splay中保...
2018-08-29 11:46:58
177
原创 树链剖分简单介绍
树剖想必各位大佬早已经烂熟于心 此篇博客大部分将 灌水 写写自己在学习树链剖分时对于各部分的理解树链剖分是一种将树转化为链进行维护的数据结构 也可以说是将点按一定的顺序放在序列中，使得修改两个点之间的路径时将一段非连续序列转化为 多个连续区间，用线段树分别进行修改如何进行排列？一般来说，最有可能同时修改的点我们尽量将其放在一起 对于每个点定义其子节点中子树大小最大的为其 重儿子 ...
2018-08-28 21:17:00
146
原创 SPOJ 104 HIGH - Highways 矩阵树定理
题意ttt组询问nnn个点，mmm条边分别连接ai,biai,bia_i , b_i求有多少种生成树的方案Solution矩阵树定理裸题Matrix Tree TheoremWikipedia为了不爆精度行列式的guessguessguess使用辗转相减法代码如下：#include <bits/stdc++.h>using namespac...
2018-08-28 11:01:05
208
原创 生成函数 从出生到凉凉
普通型生成函数(Ordinary Generation Function)对于一个无穷数列f0,f1,f2,⋯f0,f1,f2,⋯f_0 , f_1 , f_2 , \cdots将其看做一个无穷维向量，写出其形式幂级数：f(x)=∑∞i=0fixif(x)=∑i=0∞fixif(x) = \sum_{i = 0}^{\infty} f_i x^i例：数列1,1,1,⋯1,1,1,⋯...
2018-08-23 08:31:13
235
原创 多项式除法
已知f,g,degf=n,degg=m(m≤n)f,g,degf=n,degg=m(m≤n)f,g,\deg f = n,\deg g = m (m \leq n)求唯一的q,rq,rq,r，使得f=q×g+rf=q×g+rf = q \times g + r，其中degr<mdegr<m\deg r < m例：f(x)=x4+x3+2x2+4x+2,g(x)=x2+x+...
2018-08-22 20:24:37
2185
原创 多项式求逆
对于fff，若有ggg，使得f×g(x)=1f×g(x)=1f\times g(x) = 1，称ggg为fff的逆给fff，求ggg的前nnn项，即求1f(x)1f(x)\frac{1}{f(x)}的麦克劳林级数的前nnn项系数例：f(x)=1−xf(x)=1−xf(x) = 1 - xg(x)=11−x=∑∞i=0xig(x)=11−x=∑i=0∞xig(x) = \frac{1}{...
2018-08-22 20:21:48
881
原创 BZOJ 3456 城市规划 生成函数 NTT
题意求nnn个有标号点的无向联通图个数Solution发现直接求解很复杂，将其用别的函数表示出来设f(x)f(x)f(x)为包含111号节点的节点数为xxx 无向连通图 个数，g(x)g(x)g(x)为节点数为xxx的 无向图 个数这两个函数有以下关系：g(n)=∑i=1nCi−1n−1f(i)g(n−i)g(n)=∑i=1nCn−1i−1f(i)g(n−i)g(n...
2018-08-22 20:16:12
254
原创 BZOJ 3771 Triple 生成函数 NTT 容斥
题意有nnn件物品，每件物品有一个权值aiaia_i，可以用1,2,31,2,31,2,3个价值不同的物品组合出一个总价值，问每种总价值有多少种组成方案Solution既然每种价值的物品只能选一个，那么不用管每种价值有多少个，只用关心有没有就好了。作为一个组合问题，使用普通型生成函数考虑到直接算答案比较麻烦，利用容斥进行计算A(i)A(i)A(i)表示选择一件物品的生成函数...
2018-08-22 09:26:43
235
原创 修改文章标题啦
经过实践论证表明，如果在文章标题前面加上一些奇怪的东西可能会影响收录当然更有可能的是本蒟实在是太弱了所以今后的文章标题会发生一些变化去除【总结】【题解】【考试】【解题报告】等标签然后在后面会加上每个题目解决所需要的用法，方便广大OIer查找希望大家能够继续资瓷我的小小博客你们的认可就是对我最大的鼓励QwQ...
2018-08-16 20:53:11
353
原创 NTT从入门到精通
本片博客中有很多前置知识，请一定要保证自己看懂，这样后面的学习会非常的轻松！！！剩余系剩余系指对于某一个特定的正整数nnn，一个整数集中的数模nnn所得的余数域 如果一个剩余系中包含了这个正整数所有可能的余数，那么称之为模nnn的完全剩余系简化剩余系是nnn的完全剩余系中与nnn互素的数构成的子集群群的阶数定义为集合GGG元素的个数，记作|G||G||G|如果GG...
2018-08-16 20:46:20
2678
原创 一份非常详尽的FFT教学向博客
作为一个蒟蒻，在发现自己的FFTFFTFFT理解貌似有很多坑之后，我决定重写一篇 非常 非常 非常 详尽的FFTFFTFFT博客 这篇博客从000喀什讲解，面向和我一样的ruoruoruo，所以，DalaoDalaoDalao退散 QwQ在此特感谢function2 深入浅出的讲解，本文出自其讲义多项式的数域对于数域FFF,若a0,a1,a2,⋯,an∈Fa0,a1,a2,⋯,an...
2018-08-13 22:00:10
417
原创 网络流初步 Dinic的优化
网络流是什么?简要介绍：移步 litble的博客关于Dinic算法在E-K算法中,我们利用BFSorDFS中的一种来寻找增广路经 而在Dinic算法中,需要将两者结合起来使用定义一个名词：层次 第iii层代表距离源点的最短距离为iii的点集利用BFS将所有点的层次计算出来,再使用DFS进行增广路的寻找,修改后再进行BFS…以此类推显然的,每次增广路径必然要经过每一层...
2018-08-09 10:00:34
191
原创 无旋Treap 从狂转到不转
在学习平衡树部分时,旁边的某位C姓dalao对Treap情有独钟,而我却为Splay的优美而深深着迷.这导致了对Treap的不屑一顾 这东西有什么用,那么多操作都不资瓷,low如今繁华落尽,每次遇到需要使用平衡树的题时,不禁流下了悔恨的泪(汗)水 Splay真xx**难打!所以,今天,就让我们来讲讲无旋Treap无旋Treap无旋Treap最大的优势就是编码简单...
2018-07-27 15:13:50
1102
1
原创 BZOJ 3132 上帝造题的七分钟 （树状数组）
Description “第一分钟，X说，要有矩阵，于是便有了一个里面写满了000的n∗mn∗mn*m矩阵。 第二分钟，L说，要能修改，于是便有了将左上角为(a,b)(a,b)(a,b)，右下角为(c,d)(c,d)(c,d)的一个矩形区域内的全部数字加上一个值的操作。 第三分钟，k说，要能查询，于是便有了求给定矩形区域内的全部数字和的操作。 第四分钟，彩虹喵说，要基于二叉树的数据结构，于...
2018-07-24 11:52:35
230
原创 树状数组 之扩展
在上一篇博客中,讲解了一些关于树状数组基础的部分以及其最简单的用法:区间查询,单点修改,还没有看过的请戳这里细心的童鞋可能已经发现树状数组的查询是前缀和的查询,于是可以利用这个形式扩展出很多其他的用法 比如说单点查询,区间修改其查询前缀和的性质,直接用树状数组维护一个差分数组,那么每次查询得到差分和前nnn项,即a[n]a[n]a[n]区间修改[l,r][l,r][l,r]时只改...
2018-07-24 09:16:00
390
原创 树状数组 为何你如此优秀
想必大家对树状数组都并不陌生 近年来,许多OI赛事中都出现了它的身影.由于其编码难度较小，速度较快，受到广大Oier的喜爱(划掉)让我们聊一聊这个神通广大的数据结构-树状数组吧!树状数组是啥?树状数组是一个用来维护序列的数据结构 没有啦(划水树状数组到底是啥?假设有这样一段序列 现在需要你支持区间查询,你会怎么做? 前缀和不就完了么 –dalao说但...
2018-07-22 21:03:43
407
原创 BZOJ 1500 [NOI2005]维修数列 （Splay）
Description Input 输入的第111行包含两个数NNN和MMM(M≤2∗104)(M≤2∗104)(M\leq2*10^4),NNN表示初始时数列中数的个数,MMM表示要进行的操作数目. 第222行包含NNN个数字,描述初始时的数列. 以下MMM行,每行一条命令,格式参见问题描述中的表格. 任何时刻数列中最多含有5∗1055∗1055*10^5个数,数列中任何一个数字均...
2018-07-19 11:34:23
167
原创 BZOJ 2124 等差子序列（线段树）
Description 给一个111到NNN的排列AiAi{A_i},询问是否存在1≤p1&amp;lt;p2&amp;lt;p3&amp;lt;p4&amp;lt;p5&amp;lt;⋯&amp;lt;pLen≤qN1≤p1&amp;lt;p2&amp;lt;p3&amp;lt;p4&amp;lt;p5&amp;lt;⋯&
2018-07-17 09:33:12
361
原创 BZOJ 3039 玉蟾宫（单调栈）
题目描述 Description 有一天,小猫rainbow和freda来到了湘西张家界的天门山玉蟾宫,玉蟾宫宫主蓝兔盛情地款待了它们,并赐予它们一片土地 这片土地被分成N∗MN∗MN*M个格子,每个格子里写着’R’或者’F’,R代表这块土地被赐予了rainbow,F代表这块土地被赐予了freda 现在freda要在这里卖萌…它要找一块矩形土地,要求这片土地都标着’F’并且面积最大 但是r...
2018-07-16 08:15:10
272
原创 BZOJ 1367 [Baltic2004] sequence（左偏树）
ProblemProblem 1367. – [Baltic2004]sequenceSolution这个题目在2005国家集训队论文 黄源河 左偏树的特点及其应用稍微修改后作为例题出现,具体证明可见论文集[左偏树的应用]首先,为了便于分析,我们将题目转化 将t1,t2,⋯,tnt1,t2,⋯,tnt_1,t_2,\cdots,t_n变为t1−1,t2−2,⋯,tn−nt1−...
2018-06-28 21:17:47
176
原创 BZOJ 4003 [JLOI2005] 城池攻占（左偏树）
Solution朴素做法: 直接模拟每个士兵的行进路线 时间复杂度O(nm)O(nm)O(nm),显然是会挂掉的优化: 在朴素做法中,每个士兵的路线显然是有很多交的 若对于交上的任意一点,我们每次只需要比较该点大小和能到达该点的所有权值最小士兵 每个点的比较次数=在该点阵亡的次数+1能到达点iii的士兵即能通过任意fa[x]=ifa[x]=ifa[x]=i的点的士兵+开始就在...
2018-06-27 20:00:28
167
原创 左偏树小结
1 左偏树的定义和性质左偏树是一种优先队列,它除了支持优先队列的三个操作:插入,取得最小(最大)节点,删除最小(最大)节点之外,还支持一个额外的操作:合并操作左偏树是一种可并堆,它以一棵二叉树的形式存在.二叉树中每一个节点保存有左右儿子(lc,rc)(lc,rc)(lc,rc),值(key)(key)(key),距离(dis)(dis)(dis) 在这里的节点iii的距离指的是节点iii...
2018-06-26 16:56:19
230
原创 并查集的二三事
并查集是一个维护集合的数据结构 它能够方便的进行元素集合的合并,并且查询每个元素属于哪个集合 并查集更多的在于关系的传递性,集合与集合之间常常因为一个元素的“搭桥”而合并成为同一个集合 只要1,2,3,A题很简单并查集(simple)在使用并查集时,我们一般通过维护父子关系来完成对集合的控制 若两个点的最老祖先相同,则在同一个集合内,否则,不在同一个集合内 若要进行合并集...
2018-06-25 21:40:00
190
原创 BZOJ 1854 [SCOI2010] 游戏 并查集
BZOJ 1854 [SCOI2010] 游戏题目描述 Description lxhgww最近迷上了一款游戏,在游戏里,他拥有很多的装备，每种装备都有2个属性,这些属性的值用[1,10000]之间的数表示.当他使用某种装备时,他只能使用该装备的某一个属性.并且每种装备最多只能使用一次. 游戏进行到最后,lxhgww遇到了终极boss,这个终极boss很奇怪,攻击他的装备所使用的属性值必须...
2018-06-21 22:18:38
233
原创 仙人NTT的入门
仙人NTT的入门在快速傅里叶变换中,我们利用wnwnw_n单位复数根实现了消去引理和折半引理 但是由于复数运算的关系,导致精度问题,使人十分捉鸡 那么,有没有什么整数也满足消去引理和折半引理来代替wnwnw_n单位复数根呢? 这就是所谓的原根那么什么是原根呢? 定义ppp的原根为满足gϕ(p)≡1(modp)gϕ(p)≡1(modp)g^{\phi (p)}\equiv 1 \pm...
2018-06-20 21:46:41
286
原创 BZOJ 4503 两个串 FFT
BZOJ 4503 两个串Solution题目要求: 给定两个串,问第二个串在第一个串的哪些位置出现过 第二个串中有通配符’?’乍一眼看上去是一个KMP? 但是因为通配符的存在使得nxtnxtnxt数组直接报废当然,DPDPDP也是可以的 但是自己感受那令人绝望的时间复杂度吧考虑将其转化为数字串做减法 设第一个串为aaa,第二个串为bbb,长度分别为la,lbla...
2018-06-12 09:29:27
172
原创 坑逼FFT的入门
简单的预备知识系数表达用多项式每一项的系数表示多项式点值表达用nnn个横坐标各不相同的点(x,y)(x,y)(x,y)来表示一个次数界为nnn的多项式求值系数表达=&amp;amp;amp;amp;gt;=&amp;amp;amp;amp;gt;=&amp;amp;amp;gt;点值表达 O(n2)O(n2)O(n^2)霍纳法则插值点值表达=&amp;amp;amp;amp;gt;=&amp;a
2018-06-11 19:26:16
387
2
原创 BZOJ 3930 [CQOI2015]选数 分块+前缀和+玄
BZOJ 3930 [CQOI2015]选数Solution题目要求: ∑a1=LR∑a2=LR⋯∑aN=LR[gcd(a1,a2,⋯,aN)=K]∑a1=LR∑a2=LR⋯∑aN=LR[gcd(a1,a2,⋯,aN)=K]\sum_{a_1=L}^{R}\sum_{a_2=L}^{R}\cdots\sum_{a_N=L}^{R}[gcd(a_1,a_2,\cdots,a_N)=K]...
2018-06-10 16:08:26
313
原创 BZOJ 2693 jzptab 莫比乌斯反演
BZOJ 2693 jzptabSolution题目要求: ∑i=1n∑j=1mLCM(i,j)∑i=1n∑j=1mLCM(i,j)\sum_{i=1}^{n}\sum_{j=1}^{m}LCM(i,j) 多组询问和BZOJ 2154的唯一区别就是加了多组询问 但是没有发现BZOJ 2154 的询问是n−−√n\sqrt n的么 所以直接control+c control+...
2018-06-10 09:15:59
199
原创 BZOJ 2301 [HAOI2011] Priblem b 莫比乌斯反演
BZOJ 2301 [HAOI2011] Priblem bSolution题目要求: ∑x=ab∑y=cd[gcd(x,y)=d]∑x=ab∑y=cd[gcd(x,y)=d]\sum_{x=a}^{b}\sum_{y=c}^{d}[gcd(x,y)=d]就是BZOJ 1101 Zap套一个容斥就好了代码如下:#include &amp;lt;bits/stdc++.h&amp;gt...
2018-06-10 08:58:58
272
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人