WC 赛前训练日志 3

Nagisa

二维平面，给出三个$n$个点的凸多边形，有$q$次询问，每次给出一个点，问是否存在一个三个顶点分别在凸多边形里的三角形，使得三角形的重心是这个点。

$n,q\le 10^6$。

计算几何 凸包 闵可夫斯基和

这题的重点是，我凸包求错了。有两个问题：

• 分类讨论的时候没有讨论全，被 assert 打爆了。
• 求凸包的时候如果按照$(x,y)$排序，求上凸包是对的，求下凸包就不对了。虽然我也不懂为啥。

最好的策略似乎是只求上凸包，然后翻转一下再做一次。

Tomoya

给出一个$n$个点$m$条边有向有自环有重边无非自环的环的图，即一个 DAG 加上若干个自环。每条边有一个实数边权。要求你从$S$走到$T$。你每走到一个点（包括最开始的$S$），这个点的出边（自环也算出边）的边权就会被等概率随机打乱，而你可以看到打乱后的结果，并决定走哪条边。你的目标是走过的边权和最小。

问最优策略的期望边权和，输出实数。

$n, m\le 1000$。

期望

期望题的套路：设$E(u)$表示$u$走到$T$的期望。

没有自环

记$u$的后继分别是$v_1, \ldots, v_k$。记$u$的出边边权分别为$w_1,\ldots,w_k$。

如果$u$没有自环，那么你会选择$E(v)+w$最小的走。对于$w$的每个排列，我们要算$E(v_i) + w_i$的最小值。

由于$E(v) + w$只有$O(k^2)$个不同的值。考虑枚举这个最小值$x$，那么我们要求剩下$k-1$个的值都大于等于$x$。那么把$w$和$v$分别从小到大排序，相当于每个$v_i$能选的$w_j$是一段后缀。方案数是乘积的形式。

那么我们从小到大枚举$E(v) + w$的值，发现每次对乘积的影响是$O(1)$的。也就是说只有$O(1)$个数能选的范围发生改变。这样就可以$O(k^2\log_2k)$计算期望。

有自环

如果$u$有自环，那么我们就多了一个决策：走自环到$u$。决策涉及到了自身，就不能简单地建立无后效性的转移关系，因此考虑建立等式。也就是说$E(u) = p(c_1 + E(v)) + (1-p)c_2$，意思是说我们以$p$的概率走自环，代价为$c_1$，然后再走这个期望，或者我们直接走出去，代价是$c_2$。

然而本题难点在于，该等式的系数表达难以得到。也就是说我们不知道这个等式长啥样。

考虑执行一个结果收敛的迭代过程。假设我已经求出了$E(u) = x_0$，那么我们可以建立怎样的等式？

这时一个精妙的思路来了：因为$E(u)$在逻辑上被视为常量，那么自环就可以变成普通边了！

如果$u$有$t$个自环，那么我就把这$t$个自环删掉，给$u$新增$t$个后继，新增后继的期望都设为$E(u)$。那么这就转化为没有自环的情况了。因此我们就可以用$x_0$求出$u$的期望$E'(u)$了。

如果$x_0$是$E(u)$的精确值，那么用$x_0$求出的$E'(u)$就应该满足$E'(u) = x_0$。否则，$E'(u)$就与$x_0$有误差。而这个误差是收敛的。也就是说我们不断地令$x_0 = E'(u)$然后再用$x_0$求出新的$E'(u)$，无限次后就可以得到$E(u)$的精确值。

直接迭代太慢。改成二分就行。

时间复杂度$O(nm\log_2W)$。

Battle Lemmings

有一个长度为$n$的 01 序列$s$。每次你可以把一个$1$和与它相邻的$0$交换位置。定义一个序列的价值是满足以下条件的区间$[l,r]$的个数：

• $s_l = s_r = 0$。
• 存在$l<i<r$使得$s_i=1$。

现在对于$k = 0,1,\ldots, \frac{n(n-1)}{2}$，要求你求出在执行至多$k$次操作的情况下，序列的价值的最大值。

$1\le n\le 80$。

将求最大价值转化为求最小代价。设由$0$构成的极长连续段的长度的集合是$L$，那么序列$s$的代价可以描述为

$$\sum_{l \in L(s)} \binom{l}{2}$$

$f(i,j,k)$表示考虑前$i$个$1$，第$i$个$1$的位置是$j$，一共动了$k$步的最小代价。

考虑转移，$f(i,j,k) = \min_{p<j} f(i-1,p,k-|a_i-j|) + \binom{j-p-1}{2}$。

不妨分类讨论。

Case 1

对于$a_i\ge j$的情况，$f(i,j,k) = \min_{p<j} f(i-1,p,k-a_i+j) + \binom{j-p-1}{2}$。

固定$x = k - a_i + j$，固定$i$，那么

$f(i,j,x+a_i - j) = \min_{p<j}f(i-1,p,x) + \binom{j-p-1}{2}$。

右边是一个只与$j$和$p$有关的式子，那么

$2f(i,j,x+a_i-j) - j^2 + 3j = - 2jp + (2f(i-1,p,x) + p^2 + 3p + 2)$.

不妨设左边的是$b_j$，与$p$有关的部分是$y_p$，设$k_j = 2j$，那么

$b_j = -k_jp + y_p$。这是让一条斜率为$k_j$的直线过$(p,y_p)$这个点，并最小化截距$b_j$的问题。

注意到$k_j$和$p$都是单调的，可以直接斜率优化。

计算的时候按照$j$从小到大的顺序。固定$i$，将 DP 状态$f(i,j,k)$按照$j+k$的值分类（可以发现是一条一条斜线）。这样我们可以用单调队列维护凸壳，计算完同一类的 DP 状态。

Case 2

对于$a_i < j$的情况，$f(i,j,k) = \min_{p<j} f(i-1,p,k+a_i-j) + \binom{j-p-1}{2}$。

固定$x = k + a_i - j$，固定$i$，那么

$f(i,j,x - a_i + j) = \min_{p<j} f(i-1,p,x) + \binom{j-p-1}{2}$.

$2f(i,j,x - a_i + j) - j^2 + 3j = -2jp + (2f(i-1,p,x) + p^2 + 3p + 2)$.

不妨设左边的是$b_j$，与$p$有关的部分是$y_p$，设$k_j = 2j$，那么

$b_j = -k_jp + y_p$。

同样的方法，按照$j-k$对状态分类即可。

代码