wxyww

未归档

精品(28) 题解(65)

/ 注册

全部文章 / 未归档（共302篇）

bzoj1030 文本生成器

题目链接题意给出\(n\)个字符串，要构造一个长度为\(m\)的字符串\(S\)，使得给出的\(n\)个字符串中至少有一个是\(S\)的子串。问方案数。思路 \(AC\)自动机+\(DP\) 考虑至少有一个是S的子串不好考虑。考虑用全部情况减去其中不包含任何一个字符串的情况。全部情况...

AC自动机动态规划dp

2019-02-01

0 564

bzoj2434 阿狸的打字机

题目链接思路可以发现，其实题目中所描述的操作，就是在\(AC\)自动机上走的过程。输出就是打上标记。删除就是返回父亲节点。然后看询问。每次询问字符串\(x\)在字符串中\(y\)出现的次数。其实也就是问在\(AC\)自动机上的\(y\)这个字符串上，有多少位置的\(fail\)指针指向\(...

树状数组 AC自动机

2019-02-01

1 530

bzoj2553 禁忌

题目链接题意给出一个\(n\)个字符串的字典。对于一个字符串，他的贡献是这个字符串中最多的在字典中出现的不重叠子串的数量。然后问一个长度为\(len\)的，字符集为前\(alphabet\)个字符的字符串的贡献期望是多少。思路首先想如果这个长度为\(len\)的字符串已经给出了。应...

AC自动机

2019-01-31

0 688

bzoj3238 差异

题目链接思路观察题目中的式子，可以发现前两项是定值。所以只需要求出最后一项就行了。然后题目就转化为了求字符串中所有后缀的\(lcp\)长度之和。可以想到用后缀数组。在后缀数组上两个后缀的\(lcp\)长度表现为两个后缀排名之间的\(height\)的最小值。所以现在问题就又转化为了在\...

后缀数组单调栈

2019-01-30

0 448

luogu2643 聪聪可可

题目链接题意其实转化之后的题意就是求出树上有多少条路径长度是3的倍数。求答案的时候只要将这个数字除以总路径数量就行了。思路考虑点分治。对于当前子树，分别求出出树中每个点到根的路径长度对\(3\)取余后为\(0，1，2\)的个数。然后就可以通过\(0-0，1-2\)组合的方式，统计出答...

2019-01-30

0 450

点分治

思想点分治的思想其实就是在树上进行分治。从而降低复杂度。每次找到一个点，对其进行处理，然后删除这个点，对剩下的子树进行递归处理。因为重心的每个儿子的大小不超过\(\frac{n}{2}\)，所以如果这个点是重心的话，就可保证递归层数最多为log层。实现在弄懂点分治思想的情况下，点分治...

树的重心

2019-01-30

0 543

luogu4211 LCA

题目链接思路我们换一种求\(dep[lca(i,j)]\)的方法。将从根到\(i\)的路径上所有点的权值加\(1\)，然后求从根节点到j路径上点的权值和。就是\(i\)和\(j\)的\(lca\)的深度。以此类推，对于求\(\sum\limits_{i=l}^rdep[lca(i,z)]...

最近公共祖先线段树树链剖分

2019-01-29

0 522

树的直径

定义树的直径就是指树上的最长路径。一棵树可能有多个直径，并且这些直径一定两两相交。性质性质1 从树上的任何一个点为起点，所找到的最长路径的的终点一定是直径的一个端点。证明: 考虑反证法。 ①假设直径与最长路径没有交集用\(dist(x,y)\)表示从\(x\)到\(y\)...

树的直径学习笔记

2019-01-29

0 627

树的重心

定义树的重心是指树上的某个节点，满足删除当前点之后，生成的树的大小的最大值最小。性质性质1 以树的重心为根，那么根节点的每棵子树的大小都小于等于\(\frac{n}{2}\)。性质2 每棵子树的大小都小于等于\(\frac{n}{2}\)的点一定是这棵树的重心。即性质\(1\)的...

树的重心学习笔记

2019-01-29

0 602

树的重心

定义树的重心是指树上的某个节点，满足删除当前点之后，生成的树的大小的最大值最小。性质性质1 以树的重心为根，那么根节点的每棵子树的大小都小于等于\(\frac{n}{2}\)。性质2 每棵子树的大小都小于等于\(\frac{n}{2}\)的点一定是这棵树的重心。即性质\(1\)的...

树的重心学习笔记

2019-01-29

0 485