Category Archives

418 Articles

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} \]