wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共395篇）

bzoj3894 文理分科

题目链接思路先将题目转化为求最小割。也就是要找出一些贡献不选，使得这些贡献的和最小。对于单个点的贡献。显然我们可以从\(S\)到这个点连一条容量为选文收益的边。从这个点到\(T\)连一条容量为选理收益的边。然后考虑哪些额外的贡献。只要相邻的这\(5\)个点中有任何一个不选文，那么这个集合...

2019-02-07

0 588

luogu3731 新型城市化

题目链接思路这道题对于题意的转化很关键。题目要求的是添上一条边，使得图中最大团的大小变大。给出的边是原图的补集，这就给我们了提示。因为题目中说，原图中最多有两个团。所以给出的边一定形成了一个二分图。那么最大团就是新图中的最大独立集。那么问题就转化成了，在新图中删除一条边，使得新图中的...

二分图 tarjan

2019-02-07

0 458

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