随机薅羊毛

idea, std from xuanyiming data, solution from hehezhou

算法一

我会 $n=2$！

设从 $1$ 号机开始的期望为 $x_1$，$2$ 号机开始的期望为 $x_2$。

如果 $1$ 号机抽奖失败，则接下来的过程就是从 $2$ 号机开始抽奖，反之同理。

因此 $x_1=(1-p_1)x_2+1, x_2=(1-p_2)x_1+1$。

解得 $x_1=\frac{2-p_1}{p_1+p_2-p_1p_2},x_2=\frac{2-p_2}{p_1+p_2-p_1p_2}$。

算法二

上面的方程组在 $n$ 更大的情况同样可以被列出来！

具体的，设从 $i$ 号机开始抽奖的期望是 $x_i$，那么有：

$$x_i=\frac{(1-p_i)\sum_{j\neq i}x_j}{n-1}+1$$

列出系数高消即可，时间复杂度 $O(n^3)$，期望得分 $40$。

算法三

令 $s=\sum_{i=1}^n x_i$，答案即为 $\frac{s}{n}$，那么上述方程可简化为：

$$x_i=\frac{(1-p_i)(s-x_i)}{n-1}+1$$

简单变形后化为：

$$x_i=\frac{(1-p_i)s+n-1}{n-p_i}$$

将 $n$ 个方程求和，整理得：

$$s=s\sum_{i=1}^n\frac{1-p_i}{n-p_i}+(n-1)\sum_{i=1}^n\frac{1}{n-p_i}$$

这是一个一元一次方程，简单求出系数即可。

时间复杂度 $O(n)$，期望得分 $100$ 分。

重构元宇宙

idea, std1, solution1 from vfleaking data, std2, solution2 from hehezhou

算法一

我会 $k=1$！

先确定 $0$ 号点的坐标为 $0$，找一个与 $0$ 号点距离非 $0$ 的点，不妨设为 $1$ 号点，令其坐标为 $d(0,1)$。

对于其他点，求出与这两个点的距离，即可简单分讨出坐标。

算法二

我会 $n=3$！

同样先确定两个点的坐标，简单解出第三点坐标即可。

算法三

考虑逐个点加入，同样令 $0$ 号点坐标均为 $0$，维护出当前这些点可以嵌入空间的最小维数 $k$ 以及一组坐标，同时维护一组含 $0$ 号点的大小为 $k+1$ 的点集 $\{x_i\}_{i=0}^k$，使得这个点集可以嵌入空间的最小维数同样为 $k$。

设当前加入点为 $x'$，考虑列出方程：

$$\sum_{i=0}^k(x_{t,i}-x'_i)^2=d^2(x',x_t)~~(t\in[1,k])$$

注意到 $d^2(0,x)=\sum x_i^2$，因此：

$$\sum_{i=0}^{k-1} x_{t,i} \cdot x'_i=-\frac{d^2(x',x_i)-d^2(0,x)-d^2(0,x_t)}{2}~~(t\in[1,k])$$

由于这个点集的性质，这 $k$ 个方程线性无关，可以使用高消唯一确定 $x'$ 的前 $k$ 维坐标。如果此时 $\sum_{i=0}^{k-1}x_i^{'2}\lt d^2(0,x')$，则说明空间的维数需要增加 $1$，简单的将 $x'_k$ 设为左右差的平方根，并将 $x'$ 加入点集即可。

时间复杂度 $O(n^4)$，交互次数不超过 $n(k+1)$，期望得分 $70$。

算法四

考虑维护出矩阵的逆，高消可以认为是将向量乘上逆矩阵。

每次计算出加入点集的新点后，相当于在原矩阵的下方增加了一行。新的逆矩阵可以在旧逆矩阵的基础上，以 $O(n^2)$ 的开销计算得到。

时间复杂度 $O(n^3)$，期望得分 $100$。

算法五

vfk 咕咕咕。

UPD: 更新了 https://vfleaking.blog.uoj.ac/blog/7612

磁球与磁棍

idea, solution from jacder, std, data from djq_cpp

算法一

暴力枚举删哪些边然后判。时间复杂度 $\tilde O(2^n)$，期望得分 $10$ 分。

算法二

考虑 DP。

令 $f[i][j][k][l]$ 表示子树 $i$ 被切成 $j$ 块，结点 $i$ 所在的连通块叶子深度均为 $k$，$i$ 和其父结点的连边情况是 $l$ 是否为合法的状态，转移可以直接树上背包。

时间复杂度 $O(n^2)$，期望得分 $40$ 分。

算法三

为了达到线性复杂度，我们需要将 $j$ 这一维优化掉。

对于原问题，容易发现当 $k < n$ 时，若存在切成 $k$ 个连通块的方案，则一定存在切成 $k+1$ 或 $k+2$ 个连通块的方案：称一个点是自由的当且仅当它的颜色与它所在连通块的叶子颜色不同，则此时必然存在一个自由的点；若它的度为 $2$，则可删两条边构造出 $k+2$ 的方案，否则可删一条边构造出 $k+1$ 的方案。

进一步地，若 $k \not= n - 3$，则要么有度数为 $2$ 的自由点，要么有至少两个度数大于等于 $3$ 的或一个度数大于等于 $4$ 的自由点。这些情况均可构造出 $k+2$ 的方案。而 $k = n - 1$ 必然无解。

这意味着可以直接令 $dp[i][j][k][l]$ 表示子树 $i$，子树内连通块数模 $2$ 余 $j$，根所在连通块叶子颜色为 $k$ 根和父结点连边状况为 $l$ 时子树内的最小连通块数，容易做到 $O(1)$ 转移。

std 中还原方案采用的方式是构造出最小值对应的方案再用上述的调整算法调整。直接用 dp 值自顶向下还原应该也是可行的，但需要一些讨论。