「BZOJ3118」Orz The Mst
题目链接首先考虑题目描述代表了哪些限制：对于非树边 $(u,v)$ 它在树上对应了一段路径 要求这个路径上每一条边都不比他大。那么贪心的想：树边只可能减小 非树边只可能增大那么我们用 $j \text{ cover } i$ 表示$i$ 树边在 $j$ 非树边两端点在树上的路径上。用 $d_i$ 表示边的变化量。设 $T$ 表示树边集，$E$ 表示非树边集这个问题看起来是个 LP 问题 不妨...
题目链接首先考虑题目描述代表了哪些限制：对于非树边 $(u,v)$ 它在树上对应了一段路径 要求这个路径上每一条边都不比他大。那么贪心的想：树边只可能减小 非树边只可能增大那么我们用 $j \text{ cover } i$ 表示$i$ 树边在 $j$ 非树边两端点在树上的路径上。用 $d_i$ 表示边的变化量。设 $T$ 表示树边集，$E$ 表示非树边集这个问题看起来是个 LP 问题 不妨...
主要是为了学习一波 wqs 二分。首先发现这个题目等价于把树切成 k+1 块 每块内选个直径加起来，也就等价于在树上找 $k+1$ 条不相交的链使得收益最大。考虑树上每一条链都可以拆成两条深度单调的链，所以我们可以设 $f[i][j][0/1/2]$ 表示现在在 $i$ 点 已经选择了 $j$ 个链 当前 $i$ 点的状态是（没有链经过/有一条单链待匹配/有链经过），转移一下就可以了，复杂度...
作为菜鸡 OIer，本文尽量用通俗的语言去讲解后缀自动机。当然学习后缀自动机前是有一点点前置知识的，我一块给说了。有限状态自动机（DFA定义确定优先状态自动机 $\mathcal{A}$ 是由：一个非空有限的状态集合 $Q$一个输入字母表$\Sigma$ （非空有限的字符集合）一个转移函数 $\delta :Q\times \Sigma \rightarrow Q$（例如：$\delta \...
好久不更博了~~~题目大意定义一个数是好的当且仅当这个数 $x$ 满足 $l \leq x \leq r$定义一个长度为 $n$ 的字符串的价值是所有好的数在这个字符串的出现次数的和。现在给你 $l,r,n$ 让你构造出满足价值最大的情况下字典序最小的串。$1 \leq l \leq r \leq 10^{800},1 \leq n \leq 2000$题解3500的题一看我就做不来。。 首...
2019.11.05 模拟赛总结赛时开场看了 T1，发现实质上是对完全图求 $n-1$ 完备匹配，求完后就删掉。发现自己只会暴力（其实是构造题想不出来），就去看了 T2 T2 一开始感觉和树堆那个题差不多...?但是发现其实这个性质是不独立的 ，写了写代码发现了不独立之后，就只有链的分了。 由于肝 T2 花费了大量时间，没好好看 T3，写了个大众暴力 最后 30+40+30 = 100，三题...