Tag Archives

397 Articles

OI

「GDOI2020模拟02.05」生成树 – 题解

Posted by kal0rona on

主要思路

有意思。之前做过一题是用矩阵树+高斯消元插值求本题的一维情况,本打算用继续这么做,后面发现 Lagrange 插值能做到 \(\Theta(n^5)\),就学了一点新的东西。

首先,要认识到本题矩阵树出来之后可以得到一个二元多项式:

\[ \sum_{i = 0}^{n – 1} \sum_{j = 0}^{n – 1} a_{i, j} x^i y^j \]

OI

NOI 复习专题 – DP

Posted by kal0rona on

斜率优化

斜率优化其实不是很难,可以理解为在平面上的一些点作为决策点,而你现在有一条斜率为 \(k\) 的直线,你需要使其经过一个合适的点,使得这条线的截距最大/最小化。这个显然可以使这些点组成一个上/下凸包、然后二分找到斜率相近的那条线段进行转移。

OI

P5161:WD与数列 – 题解

Posted by kal0rona on

主要思路

先差分,然后再来做这个不相交子串匹配的问题。

我们可以考虑用线段树来维护 endpos 集合,然后用启发式合并的方式来计算一个后缀点与当前点集之间产生的贡献。有两种情况:

  • 当前为 endpos 的最长长度、与当前位置 \(x\) 不相交的子串。这个可以直接暴力线段树上查个数。
  • 长度小于 \(maxdep\),以 \(endpos\) 在左边的情况为例:答案的贡献就是 \(x – endpos – 1\)。