斜率优化
斜率优化其实不是很难，可以理解为在平面上的一些点作为决策点，而你现在有一条斜率为 \(k\) 的直线，你需要使其经过一个合适的点，使得这条线的截距最大/最小化。这个显然可以使这些点组成一个上/下凸包、然后二分找到斜率相近的那条线段进行转移。
Continue reading →斜率优化其实不是很难，可以理解为在平面上的一些点作为决策点，而你现在有一条斜率为 \(k\) 的直线，你需要使其经过一个合适的点，使得这条线的截距最大/最小化。这个显然可以使这些点组成一个上/下凸包、然后二分找到斜率相近的那条线段进行转移。
Continue reading →先差分，然后再来做这个不相交子串匹配的问题。
我们可以考虑用线段树来维护 endpos 集合，然后用启发式合并的方式来计算一个后缀点与当前点集之间产生的贡献。有两种情况：
啊，又是无根树 DP。首先讨论奇偶性，如果是奇数的话可以直接 DP；如果不是，则需要容斥一波。
设置状态 \(dp[scale][maxPart][degree]\)，意为大小为 \(scale\)、最大子树大小为 \(maxPart\) 且根度数为 \(degree\) 的方案树。转移其实很好想，看代码吧。
Continue reading →这个题很神仙啊。首先考虑这个函数是一个单峰函数，且最后多个点所构成的代价函数一定形如 \(y = ax^{\frac{3}{2}} + b\)，显然这个函数也是单峰的。所以，当树的形态为一条链时，我们可以尝试二分。如果进化成一颗树，我们可以考虑进行点分治，考虑当前与根连接的子树里，只有一个以下的子树是更优的。
Continue reading →首先看到这个题可以考虑树套树，然后就做完了。
我们考虑用二维树状数组进行差分。当然，如果按正常的想法差分的话，我们只能想到用前缀和维护单点值，而不是维护区间异或和。我们设差分后的结果：
\[ d_{i, j} = a_{i, j} \oplus a_{i – 1, j} \oplus a_{i, j – 1} \oplus a_{i – 1, j – 1} \]
Continue reading →