CODEPLAY0314

今天上数学课时比较清闲（主要是感觉逻辑用语没什么好学的），于是缓缓打开了大白书… 本来想看矩阵的…发现前面的内容就只有置换没看了，一时兴起就把置换解决掉… 定义 简单来说，置换是一个在正整数[1,n]到正整数[1,n]上的一一映射，将1,2,3…n变为a1,a2,a3…an，记为 (123...na1a2a3...an)\begin{pmatrix} 1 & 2 & 3 & ... & n \\ a_1 & a_2 & a_3 & ... & a_n \end{pmatrix} (1a1​​2a2​​3a3​​......​nan​​) 也可用函数表示，记为f={a1,a2,a3,…,an}f=\{a_1,a_2,a_3,…,a_n\}f={a1​,a2​,a3​,…,an​} 为了表示方便，常常将一个置换表示成几个循环乘积的形式。循环即为几个元素交替，例如(1,3,2)表示1→3,3→2,2→1.下面是一个用循环分解置换的例子。 (1234535142)=(13)(25)(4)\begin{pmatrix} 1 &am ...

坑什么的随便就挖好了。 Trie - 字典树 概述 也叫前缀树，用来保存字符串集合。从根到每一个单词结点的路径就是一个单词。 模板见ACAM. Trie还可以改进，可以将后缀相同的单词收束，学有余力来过来看。 例1 [LA3942] Remember the Word [Description] 给定最多4000个长度不超过100的单词，将一个长度不超过300000的字符串拆解成单词有多少成拆发。 [Solution] DP+Trie.先预处理哪些区间[i,j]是单词（枚举+判断需O(n2)O(n^2)O(n2)，我们可以直接从Trie下手），再线性转移。 例2 [UVa11732] "strcmp()"Anyone? [Description] 给定不超过4000个长度不超过1000的字符串，求他们两两公共前缀总和。 [Solution] 在Trie上操作。 MP - 最小表示法 概述 大半年前看过一遍然后完全不记得了啊，再看的时候傻逼得吓人qwq 字符串什么的就是容易忘… 一种判循环同构的工具。 [Code] 1234567891011121314con ...

树的重心与直径 树的直径 定义 树的直径指树的简单最长路 求法 两遍DFS，第一遍任取一点，找一个与这个点距离最远的点，可以证明这个点一定是直径的一个端点；第二遍从这个端点出发，找到离这个端点距离最远的点，这个点即为直径的另外一个端点。 例题1 [Description] 给定一棵树，在树上任意放置三个点ABC，求路径A-B-C的最大值。 [Solution] 可以看出，A-B或B-C一定有一条是树的直径（不然可以调整到更优），所以找出树的直径后，枚举另外一个点的位置即可，3遍DFS解决。 例题2 [BZOJ1912] APIO2010patrol [Description] 求边权为1的树的最长链和不为最长链子链的次长链。 [Solution] 最长链就是树的直径咯，求出直径后，把直径上边的权值变为-1，即对答案的贡献为-1，再求一遍直径即可。 树的重心 定义 使得去掉这个点后最大联通分块最小的点。 意义 删掉后子树尽量平衡，在树分治的时候避免极端退化情况。 性质 以重心为根，所有子树的大小不超过树的大小的一半 树中所有点到某个点的距离和中，重心为最小（默认边权为1） 用一 ...

Trip tp Sanya: 2015/08/02 ~ 2015/08/05

来自朱全民组合数学八题

这篇主要是自己记记玩玩的，可能只有我一个人看的懂…

Hash算法虽然被称为算法，但实际上它更像是一种思想。Hash算法没有一个固定的公式，只要符合散列思想的算法都可以被称为是Hash算法

（KMP算法并不很好理解，请读者在阅读过程中集中精力并有自己的思考）