UOJ Easy Round 10

A. 随机薅羊毛

记 $f _ i$ 表示选择了第 $i$ 个抽奖机期望的次数，在这个抽奖机抽奖后，有 $1 - p _ i$ 的概率不中，在剩下 $n - 1$ 个抽奖机继续抽。即
$$
f _ i = 1 + (1 - p _ i) \frac {\displaystyle \sum _ {j \neq i} f _ j} {n - 1}
$$
记 $s _ f = \displaystyle \sum _ {i = 1} ^ n f _ i$ ，那么式子写作：
$$
f _ i = 1 + (1 - p _ i) \frac {s _ f - f _ i} {n - 1}
$$
整理为 $f _ i$ 关于 $s _ f$ 的式子：
$$
f _ i = \frac {(1 - p _ i) s _ f + n - 1} {n - p _ i}
$$
将所有 $f _ i$ 加起来：
$$
\displaystyle \sum _ {i = 1} ^ n f _ i = s _ f = \sum _ {i = 1} ^ n\frac {(1 - p _ i) s _ f + n - 1} {n - p _ i}
$$
整理为 $s _ f$ 关于 $p _ i$ 的式子：
$$
(1 - \sum _ {i = 1} ^ n \frac {1 - p _ i} {n - p _ i}) s _ f = \sum _ {i = 1} ^ n \frac {n - 1} {n - p _ i}
$$
最开始在 $n$ 个中选择一个，故答案为 $\bar f = \frac {s _ f} n$ 。

精度被叉了？使用 Kahan 计算和。

查看代码

#include <cstdio>
#include <vector>
using namespace std;
const int N = 1e6 + 10;
int n;
double kahanSum(vector<double> &nums)
{
    double sum = 0, c = 0;
    for (double x : nums)
    {
        double y = x + c, t = sum + y;
        c = y - (t - sum);
        sum = t;
    }
    return sum;
}
int main ()
{
    scanf("%d", &n);
    vector <double> nums;
    for (int i = 1, p; i <= n; i++)
    {
        scanf("%d", &p);
        nums.push_back((1e6 - p) / (1e6 * n - p));
    }
    double res = kahanSum(nums);
    printf("%.15lf", (n - res) / (1 - res) / n);
    return 0;
}

B. 重构元宇宙

首先考虑一个点到两个点，只用考虑在一维数轴上特定距离的点即可；考虑两个点到三个点，只用考虑在二维平面上两个圆的交点即可。对于第 $i$ 个点（从 $0$ 开始），只需考虑 $i - 1$ 维。对于维数 $k$ ，只要确定了 $k + 1$ 个点，就可以如球形空间产生器的做法解得一个 $k$ 维坐标。

考虑如何考虑前 $k + 1$ 个点，每个点都在前一个点上增加了一维，可以写作 $(x _ 0, x _ 1, \ldots, x _ {i - 2}, h)$ 。同样和球形空间产生器一样，$h$ 可以消完。

交互次数为 $\frac {(1 + k) k} 2 + (k + 1)(n - k - 1) < n (k + 1)$ ，时间复杂度为 $O(k ^ 3 n) $ ，期望分数 $70pts$ 。

更进一步的做法是优化高斯消元的过程，不会，先咕了。