最近文章

451 Articles

OI

P5161:WD与数列 – 题解

Posted by kal0rona on

主要思路

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

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

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

「Codeforces 566C」Logistical Questions – 题解

Posted by kal0rona on

主要思路

这个题很神仙啊。首先考虑这个函数是一个单峰函数,且最后多个点所构成的代价函数一定形如 \(y = ax^{\frac{3}{2}} + b\),显然这个函数也是单峰的。所以,当树的形态为一条链时,我们可以尝试二分。如果进化成一颗树,我们可以考虑进行点分治,考虑当前与根连接的子树里,只有一个以下的子树是更优的。

OI

「Codeforces 341D」Iahub and Xors – 题解

Posted by kal0rona on

主要思路

首先看到这个题可以考虑树套树,然后就做完了。

我们考虑用二维树状数组进行差分。当然,如果按正常的想法差分的话,我们只能想到用前缀和维护单点值,而不是维护区间异或和。我们设差分后的结果:

\[ d_{i, j} = a_{i, j} \oplus a_{i – 1, j} \oplus a_{i, j – 1} \oplus a_{i – 1, j – 1} \]