题解-CF1479

CF1479A Searching Local Minimum

类似二分答案的东西。维护一个满足 (a_l < a_{l - 1}, a_r < a_{r + 1}) 的区间。这里面必然有一个局部极小值。

如果我们查询 (a_{mid - 1}, a_{mid}, a_{mid + 1})，要么得出 (a_mid) 是局部极小值，要么得出一个更小的这样的区间。

aclink

CF1479B1 Painting the Array I，CF1479B2 Painting the Array II，

一模一样，放在一起说得了。

以 B1 为例。

维护一个 (dp)，(dp_{i, j}) 表示算到第 (i) 个点，(a^{(0)}) 和 (a^{(1)}) 的最后两个数是 (a_i) 和 (j)。

转移分为两类讨论，第一类是 (a_i) 覆盖了 (a_{i - 1})，第二类是 (a_i) 没有覆盖 (a_{i - 1}) 。

[dp_{i, j} = egin{cases} dp_{i - 1, j} + [a_i eq a_{i - 1}] (j eq a_{i - 1})\ \max(dp_{i - 1, k} + [k eq a_i]) (j = a_{i - 1}) end{cases} ]

aclink1，aclink2

CF1479C Continuous City

可以立马简化题意，如果 (L eq 1) 就把 (1) 号节点向 (2) 号节点连长度为 (L - 1) 的边，接下来的起点就是 (2) 号了。这样可以把转化为要求路径长度是 ([1, k]) 的情况。

首先考虑一个严格弱化问题，如果要求路径数量是 (k)？

考虑二进制拆分，第 (f_t) 个节点表示路径数量是 (2^t) 的情况。对于节点 (f_x)，只要把起点连向他，(forall t < x, f_t) 连向他即可。

对于终点，起点连向他，剩下的直接二进制拆分就好了。

这个拓展版本也就很好做了：第 (f_t) 个节点表示的是路径长度是 ([1, 2^t]) 的情况就可以轻松构造出来。

aclink

CF1479D Odd Mineral Resource

介绍两种方法。

法 1

这是一个有关树上数颜色的问题，用树上莫队。

对颜色编号进行分块，块内维护可能成为答案的颜色。

修改时，如果此颜色的出现次数是奇数，那么就认为这种颜色可能成为答案。

查询的时候，对于整块扫描可能成为答案的颜色。对于一个扫到的数 (x)，如果出现次数确实是奇数就停，否则就把 (x) 从可能成为答案的数中删除。散块暴力即可。

时间复杂度 (Theta(n sqrt m))

喜提最劣解。

aclink

法 2

出现奇数次可以用异或来处理。

如果对于每一个元素，进行随机赋值。我们查询树上 (u) 到 (v) 上，编号在 (l) 到 (r) 的权值异或和，如果是 (0) 那么我们就认为答案是 -1。

然后我们进行二分答案，查询一下 ([l, mid])，如果异或和不是 (0) 就在 ([l, mid]) 往下做，否则 ([mid + 1, r]) 的异或和一定不是 (0)，在 ([mid + 1, r]) 往下做。

这个可以主席树维护。由于主席树的优良性质，我们可以直接在主席树上二分。时间复杂度 (Theta((n + m) log n))

喜提最优解。

aclink

CF1479E School Clubs

设势能函数 (phi(A) = sumlimits_{i = 1}^n f(a_i))

设 (s = sumlimits_{i = 1}^n a_i)。

单次操作势能函数的期望变化量必然是 (-1)：

[sumlimits_{i = 1}^n frac{a_i}{s} frac{1}{2}( - f(a_i) + f(1) + f(a_i - 1) + sumlimits_{j eq i}^{n} frac{a_j}{s} ( - f(a_i) + f(a_i - 1) - f(a_j) + f(a_j + 1)) = -1 ]

[sumlimits_{i = 1}^n frac{a_i}{s} ( 2 - f(a_i) + f(1) + f(a_i - 1) + frac{s - a_i}{s} (f(a_i - 1) - f(a_i)) + frac{s - a_i}{s} (f(a_i + 1) - f(a_i))) = 0 ]

[frac{x}{s} ( 2 - f(x) + f(1) + f(x - 1) + frac{s - x}{s} (f(x - 1) - f(x)) + frac{s - x}{s} (f(x + 1) - f(x))) = 0 ]

对于 (x = 0)，那么已经满足；对于 (x eq 0 :)

[2 s + f(1) s + (f(x - 1) - f(x)) s + (s - x) (f(x - 1) - f(x)) + (s - x) (f(x + 1) - f(x)) = 0 ]

[f(x + 1) = frac{- 2 s - f(1) s - (2s - x) f(x - 1) + (3s - x) f(x)}{s - x} ]

为了方便，让 (f(1) = -2)。并且为了让最终状态下势能函数是一定的，我们令 (f(0) = 0)。于是这个东西就可以递推。

注意一个细节：我们用分数表示函数，可以避免每次都求一次逆元。