ZJOI2015 地震后的幻想乡我们其实只需要边的相对的发小关系，我们只要知道这个边是第几就可以了，因为如果知道它是第几就知道权值期望是$\frac i {m+1}$ 所以我们考虑这样一个dp，$dp[S][i]$表示加入第$i$小的边权时$S$是联通的方案数。 由于一个显然的前缀和，我们知道答案其实就是 \sum_i \frac i {m+1} \times ( \frac {dp[S][i]}{\binom i m} - \frac{dp[S][i-1]}{\binom {i - 1} m ...

[九省联考2018]一双木棋chess据说这题是可以暴力踩过去的。。 还是考虑正解吧，是一种叫 轮廓线dp 的只听过没写过的东西 不难发现，最后拿出来的棋子一定是左上角占的一块区域。发现$n + m \leq 20$我们可以状压一下这个区域右上到左下的边界。具体来说，我们存一个$2^{n + m}$以内的数，1 表示向下 0 表示向左。 是否需要再开一维状态维护当前是哪个人在下？没必要，当确定轮廓线的时候已经下的步数是确定的，所以可以知道是谁在下。为了方便实现采用记搜。 123456789101 ...

LOJ 2977 「THUSCH 2017」巧克力神仙题QaQ 做法是给每种颜色随机分配一个$1$到$k$的颜色，然后跑一次斯坦纳树，得到当前包含至少$k$种颜色的最小联通块。 我们考虑什么时候我们可以随机到答案？如果答案的$k$颜色恰好本随机分配到了不同的颜色，那么跑出来的答案肯定就是正确的。所以说，一次随机的正确率大概是$\frac{k!}{k^k}$大概是$0.3\%$。所以我们随机大概 200 次，正确率就远超 100 了。 另外考虑中位数尽量小这个限制，我们二分这个中位数，考虑怎么 c ...

CF605E Intergalaxy Trips考虑你是不知道后来的边的出现情况的，所以可以这样做：每天你都选择一些点进行观察，知道某天往这些点里面的某条边可用了，你就往这条边走。这样贪心总是对的。 我们定义一个点的权值就是这个点到$n$的期望距离。同时它就是我们要算的答案。 但是注意到一个性质，我们总是从期望较大的点走向期望较小的点（显然的）。 所以我们可以类似反过来的 dijkstra 的更新，维护当前权值的点，然后这个点当前的值就必然是最终这个点的答案。所以我们可以拿它去更新到达它的点。 ...

JSOI 2008 最小生成树计数今天的题目终于良心一点辣 一个套路+模版题。 考虑昨天讲的那几个结论，我们有当我们只保留最小生成树中权值不超过$k$的边的时候形成的联通块是一定的。 我们可以先拿 kruskal 跑一棵最小生成树，然后我们可以从小到大枚举边权，把所有除开枚举到的边权的边全部加入并且缩点。现在我们就在这个缩点后的点集进行生成树计数就好了。答案就是每种边权算出答案的积。 因为我们知道，连入$k$边权的边后对于$1$到$k - 1$的边加入后的最小生成树的影响是固定的，加入后得到的联 ...

这题为了不写线段树优化连边写单log的前缀后缀连边调死我了。。。。。 码力榨干，题解咕咕咕 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104 ...

CF 786 E ALT一个居民有两个选择：分配一只宠物，路上都有宠物 一个守卫有两种选择：分配一只宠物，不分配宠物 我们找一个原点，到每个居民都有一条边，表示是否给他宠物 从每个居民向他路上的守卫连边 守卫到汇点连边。 居民到守卫的边容量是$\infin$，所以现在达到的效果就是，要么一个居民被加边，要么一个居民连向守卫都被鸽。 一个居民连向了$O(n)$个点啊！ 怎么优化？所以我们可以类似倍增 LCA 的方法，如果向一个点的第$j$个点连边，表示它向上跳$2^k$个点那都连。最后边数是$m\ ...

数论相关算法素数的分布$[1,n]$有$\frac n {\ln n}$个素数 $\sum \frac 1 p_i = O(\log\log n)$（埃式筛复杂度） GCD$gcd(a,b) = gcd(a-b,b) = gcd(b,a\%b)$ $gcd(a,b)lcm(a,b) = ab$ 类欧几里得问题$\displaystyle \sum_{x=1}^n \lfloor \frac{ax+b}{c}\rfloor$ $a,b,c,n \leq 10^9$ 实质上是$y=\frac{ax+ ...

字符串相关算法hash & KMP & exkmpHash简单的 hash$f(S) = \sum S[i]D^{i-1} \mod P$ 代码实现很简单 一般采用双hash 尽量不用 64 位自然溢出 hash 不止可以比较字符串，矩阵也可以 KMP定义$border$是既是它前缀又是它后缀的串，$fail[i]$表示$S[1,i]$最长的border 怎么算呢，$i-1$的 border 加入一个字符就可以成为$i$的 border 加入一个$T[i]$就是跳 fail 找到 ...

后缀自动机以前学的后缀自动机 今天听了ZR 敦爷的课加上以前和zbww讨论了一下，感觉对后缀自动机和后缀数据结构有了船新认识！QWQ 后缀自动机大概分成了下面三部分： -$n^2$后缀树的构建 后缀自动机构建及基础应用 缩边并且得到$O(n)$个点的真正的后缀自动机！ 后缀树其实后缀树才是本质的后缀数据结构。 First step 后缀树构建把单词的后缀插入一棵 Trie 就可以得到后缀树，节点数是$O(n^2)$的。注意，到现在我们还是考虑$O(n^2)$的后缀树。 后缀树上的一个节点其 ...

分治与分块重制版笔记，很多地方还留了坑。。 其中穿插了重量平衡树 分治CDQ 分治本质上是考虑左边对右边的影响，问题变成了先加入再查询的问题 离线算法 处理 D 维数点时间是$O(nlog^{D-1}n)$ D 维数点用KDTree：$O(n^{\frac{D-1}{D}})$ D 维数点用Bitset：$O(\frac{Dn^2}w)$* 加点，给定$a , b$查询最大的$ax+by$ 本质上是维护动态凸壳 * 直接set维护 记录全局变量，做插入的时候按照 x 比较，做询问按照斜 ...

bzoj 4199 品酒大会开始线段树合并学傻了直接拿线段树合并莽然后80pts滚粗 其实考虑，如果我们求出了$LCP(s_1,s_2) = i$，其中$s_1,s_2$是后缀，的权值的和/最大值，做一遍后缀和/最大值就好了啊！ 这个东西是可以 dp 的！由于 parent 树本质上是前缀树，parent 树上的 LCA 实际上就是 LCP 。 由于权值在前面不好处理，可以倒过来建前缀树，也就是建后缀树，这样权值就在最后一个位置啦 对于一个点来说它作为 LCP 的长度是确定了的（$len(x)$ ...

BZOJ 4310 跳蚤不太会做，看了题解才会的。 首先要二分子串。后缀排序后，本质不同子串个数其实就是$\sum_i n + 1 - sa[i] - height[i]$，考虑排序后的后缀，本质不同的子串个数其实就是本质不同这些后缀的前缀个数。一个后缀的贡献就是这个后缀的所有前缀，减去自己和上一个后缀的 LCP 。（感性理解一下吧QAQ） 其实二分后，这个子串是可以确定的。枚举一下后缀排序后的后缀就可以得到。 假设我们当前二分到的子串是$s[L,R]$，怎么确定是否可以分成很多份，使得每一份里 ...

BZOJ 4545 DQS的Trie第一眼，这不是很裸嘛？ 直接构造广义SAM然后跑就行了啊。 动态询问 endpos 集合大小，LCT就好了嘛 （码…） 码了一半，然后发现，每次新加入一个子树啊，复杂度是假的啊？ 那这么说网上很多题解貌似都是假的。。。 （你按照dfs的顺序来加，不是就必然会被卡了嘛） 但是这个题不强制在线！ 可以先把整个树搭建好再处理询问。 考虑我们加入一个字符，其实是在让一些 SAM 上的节点 从 “没出现过” 变成 “出现过” 考虑在parent树上，可以直接跳，因为一个 ...

BZOJ 3238 差异看这个式子其实就是求任意两个后缀的$LCP$长度和。前面的$len(T_i)+len(T_j)$求和其实就是$n(n-1)(n+1)/2$，这个是很好推的。。 任意两个后缀的$LCP$长度和很容易想到构造 height 数组，然后问题就变成了所有区间的最小值的和。 这是个套路题，可以单调栈，但是其实分治也很好写！ 设我们要求的区间是$[l,r]$我们可以找出其中最小值所在的位置，这个可以ST表快速求，然后从这个位置进行分治。 这样的分治每进行一次，总有效的元素数量会减少1 ...

BZOJ 3277 串首先建立广义SAM，然后考虑SAM上一个节点是多少个串的子串。 这是一个从 bzoj 2780 学来的做法，就是建立广义SAM后对于每一个串在SAM上跑出每个前缀所在的节点，这个可以直接转移，然后从这些节点分别跳parent，直到跳到一个已经被这个串以前的点跳到过的点，并把跳到的点所属的词++。 这样看上去很$O(n^2)$但实际上它跑的跟$O(n)$似的快。 不太会证明QAQ，有会证这个下界的评论一下吧～ 现在我们可以再拿这些串跑一遍跑到的点如果拥有的词多余 k 我们就把 ...

BZOJ 3926 诸神眷顾的幻想乡开始看错题看成了每个点度数不超过20 后来翻了翻题解原来看错题的不止我一个 既然叶子数量不超过20，考虑树上的任何一条路径，以任何点为根时，如果它不是一条从上到下的路径，那么以它的任意一端的子树内的某一个叶子为根必然可以变成从上到下的。否则，以它处于下端的点的子树内的叶子为根也可以做到。 所以如果以每一个叶子为根的串建成个 Trie 并且把所有单词丢进广义SAM就做完了。 说一下广义SAM的构建： 最简单轻松的，如果只是插入一些字符串，那么插入一个后把 la ...

BZOJ 1396 识别子串昨晚拿到这道题想到了线段树做法还以为麻烦了，码了好久过了才发现网上都这么写的。。 只出现一次实际上就是 endpos 集合大小为1，就是 parent 树上siz是1。 由于我们只需要 endpos 集合大小是1的点的 endpos 集合，也没必要线段树合并求 endpos 集合了，对每个点加进去的时候记录一下 endpos 。由于我们只需要集合大小为 1 的，更新覆盖一下没关系。 然后现在拿到这些点后，假设这些点的 endpos 为$en$，这个点上最长串长度为$l ...

BZOJ 4556 [HEOI2016/TJOI2016]字符串其实题解更多是用后缀数组+数据结构的做法，貌似也不好写。 反正才学了 sam 貌似比较简单的做法。 还是得先二分，然后倍增跳到$s[c…c+mid-1]$所在的节点，然后看看有没有 endpos 在$a+mid-1…b$内就好了。 复杂度是二分和倍增的$nlog^2n$。 其实这道题因为只用求 endpos 是否存在啥的 vector + lower_bound 貌似都可以过了。。但其实启发式合并也不好写，还是写一下线段树合并吧，有 ...

后缀自动机初学建议看这个 基本上是最好的中文资料了。 字符串的SAM是一个dAg，它的边上会有一个字符，从根节点走到终止节点会构成一个后缀。它可以且只可以接受$s$的所有后缀，并且满足可以接受$s$的后缀的自动机中，SAM是节点最少的。 由于后缀自动机是个dAg，它的每个节点代表的是一些字符串（因为并不只有一条路可以到达）。 定义 : endpos 集合 对于一个$s$的非空子串$t$，endpos(t) 表示$s$中出现的所有$t$的结束位置。 定义：endpos 等价类 如果两个字串$t ...

后缀数组后缀数组，也就是后缀排序，是一个给字符串所有后缀排序的算法。 构造 直接排序我们比较的是前$n$个字符的大小关系。为了优化这个过程，后缀数组用了一种倍增的思路。比较每个字符串的第一位，再比较前 2 位，再比较前 4 位… 最后得到整个数组。这样可以合理利用已经处理的结果。在比较前$2\times k$位的时候，其实就是做了一个双关键字排序：已经求出了所有后缀前$k$位的排名，那么对于第$i$个后缀它的双关键字分别是$rnk[i] , rnk[i+k]$。其中$rnk$表示一个后缀的排名 ...

hdu 5421 Victor and String支持双端插入的回文树。 考虑维护第二个 last 表示当前整个串的最长回文前缀。 往前 append 的时候可以直接那第二个 last 来跳 fail ， 因为回文前缀和回文后缀是对称的。只有 getfail 的时候需要改一下，变成判断当前字符和前缀之后的字符是否相同。 还要注意，如果当前的前面/后面 的 last 是整个串，那么需要把另一个 last 也设置成整个串。 注意如果当前插入得到的回文串pam里面已经有了也要加上它的贡献！ 1234 ...

回文树回文树，也就是回文自动机，PAM(Palindrome automaton) 是一个处理回文串的有力工具。然而这个东西比SAM简单多了。。 （它可能比 manacher 要强得多？） 回文自动机有两个根，也就是说其实是有两个树的，一个存储长度为奇数的回文串一个存储长度为偶数的回文串。 回文自动机上的每一个节点表示一个本质不同的回文串。也就是说回文自动机上的节点个数就是本质不同的回文串个数。 一些定义-$len[p]$表示$p$节点所代表回文串长度-$fail[p]$表示$p$节点的最长回 ...

魔法咒语没有一个点到极限数据海星。。。虽然极限数据好像没法做？ 前 60% 很套路的 acam dp。$dp[i][j]$表示当前匹配到第$i$个位置，当前在 ACAM 上$j$号节点。 后 40% 的数据看起来很矩乘。(其实整个数据范围都挺矩乘的) 由于$dp[i][j]$只能从$dp[i - 1][t]$和$dp[i - 2][t]$转移到，矩阵加速一下就好了。 12345678910111213141516171819202122232425262728293031323334353637 ...

阿狸的打字机首先建立fail树，考虑离线询问。考虑怎么用ACAM处理一个串在另一个串的出现次数， 可以给询问按照主串分类，对于每一个主串分别处理所有询问。某一个串在主串中出现，主串中位于这个串最后的那个位置跳fail必然可以跳到这个串。所以可以树上差分搞一下 大概没啥问题？ 然后写了一发，就70了。 注意到对于100%的数据，没有总长度的限制啊！ 但是由于有$n$的限制，trie中的总点数是很小的。 处理方法类似 CF1207G ， 在将串加入trie的时候，可以记录一个now表示到现在为止 ...

AC 自动机做多模匹配其实就是把模式串丢到trie上，然后设置一个fail指针。 fail指针的含义是：最长的与后缀相同的前缀 明显，由于是最长的一个点的fail只会只想一个点（两个相同的前缀是一个点啊） 一个结论：如果沿着一个点一直跳fail，会得到这个串在ac自动机上的所有后缀 求出fail的过程是用bfs实现的。考虑一个节点 p 假设所有满足$len[s] < len[p]$的节点$s$的fail 指针都已经被计算出来了，它的父亲设为 f ，父亲到这个点的路径上字符是 C ，如果 f ...

斯坦纳树$dp[i][S]$表示 当前根为$i$当前生成树已经覆盖掉得关键点集合是$S$得最小代价。 转移分两种： 合并同一个根下的两种状态，$dp[i][S_1|S_2] = \min( dp[i][S_1]+dp[i][S_2] - w[i] ), S_1 \& S_2 = 0$ 通过一个点状态转移到其他点的这个状态，就是选择一个点把根置成它 $dp[j][S] = \min( dp[i][S] + w[j] )$。 转移的顺序是从小到大枚举集合，枚举所有点跑第一种转移，然后 ...

BZOJ 3514 Codechef MARCH14 GERALD07加强版看题解才会的 如果加入一条边，它对答案是否有贡献取决于它是否与当前图形成环。 所以加入一条边时，它形成的环里面的最早加入的边cut掉，并且给它赋值位这个最早加入边的编号。在查询的时候，初始答案位 n ，一个边挤出去的边的编号如果小于 L，说明它必然不会成环，于是就对答案有-1的贡献，否则说明它加进去会形成环，对答案没有贡献。 这个编号存在主席树里面，就可以强制在线了。 12345678910111213141516171 ...

lmn u 表示 u 所在splay子树最上方点距离最近的白点 rmn u 表示 u 所在splay子树最下方点距离最近的白点 开一个set维护所有虚儿子能走到的最近的白点的距离 考虑pushup， 对于它的右儿子，考虑要么从这个点走向它的虚儿子，要么通过它左子树中深度最大的点走。 对于它的左儿子要么从这个点走向它的虚儿子，要么通过它右子树的最浅点走。 123456789101112131415161718192021222324252627282930313233343536373839404 ...

[HAOI2015]按位或是一个 min-max容斥 的板子题。 min-max容斥 式子： $\displaystyle max(S) = \sum_{T\sube S} (-1)^{|T|+1} min(T)$ 并且很优秀的是，它在期望情况下成立！ 这个有什么关系呢。。 如果每一位分开考虑，如果第$i$位变成 1 的期望时间是$T(i)$ 那么求的是$E(max(T_{1\dots n}))$ 这个可以 min-max容斥 求$min$的就是某一个子集让其中某一个变成 1 的期望次数。 考虑 ...