SMU Autumn 2024 Team Round 3（成都）

· · 个人记录

G. Greek Casino

题意：一共有1到n，n个整数，每次你抽奖抽到i个概率是w[i]，如果当前你的位置是x,抽到的是y，令z=lcm(x,y)，如果z>n，游戏结束，否则会跳到z，然后接着抽奖，问从1开始，游戏结束的期望轮数是夺少

思路：典型的期望DP，在做这道题之前可以先了解一下这个题：

带富翁

题意：有n个奖励点，每个点会有一个分数a[i]，你从1点出发，有一个6面骰子，每次骰到x，往前走x步，如果dq+x>n，那么会重新骰，走到n就结束了，问期望分数是夺少？

思路：我们这样定义F[i]表示从i这个点出发，直至游戏结束的期望分数，显然，f[n]=a[n],答案是f[1],怎么求呢，我们发现从x出发，会跳到1……6 +x，那么如果没有超过n，设跳到y，是否f[x]=a[x]+（f[y1]+f[y2]+f[y3]+f[y4]+f[y5+f[y6]）/6，如果会跳出N，把那些去掉即可，能跳掉的点数是sum个，概率变为1/sum，然后就从后往前DP出f[1]了

#include <bits/stdc++.h>
using namespace std;
int a[105];
double dp[105];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    dp[n]=a[n];
    for(int i=n-1;i>=1;i--)
    {
        int num=min(6,n-i);
        dp[i]=a[i];
        for(int j=i+1;j<=i+6;j++)
        {
            dp[i]+=dp[j]/num;
        }
    }
    printf("%.10lf\n",dp[1]);
}

那么我们考虑本题怎么做呢？其实类似，设f[i]表示从i开始，游戏结束的期望。那么从i开始可以跳到的点是i的倍数,因为是最小公倍数、那么你可以枚举LCM为j，一定是i的倍数，然后再枚举跳到的点x，这个x一定是有一个因子是j/i的记为k，那么其他因子一定是i的因子，枚举一下，如果组成的x，x与i的lcm是我们枚举的j，那么记录答案f[i]+=p[x]*(f[j]+1)，同时记录一下这些概率和，意义是没跳出去的概率，然后再1-s2，是跳出去的概率，还剩一部分是一直停留在原地的概率，其实是这样的，你只要摇到了i的因子，必然是停留在原地嘛、s1为因子的概率、q=(1-s1)为没摇到因子的概率、那么经典的几何分布，对于一个游戏，成功的概率是q，失败了就再来一轮、问成功的期望轮数，这个我们就可以求一个级数q+2*q*p+3*p^2*q+4*p^3*q+……,这个就是期望=1/q，那么答案就显而易见了

diamond：

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    int sum = 0;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        sum += a[i];
    }

    vector<double> p(n + 1);
    for (int i = 1; i <= n; i ++) {
        p[i] = a[i] * 1.0 / sum;
    }

    vector g(n + 1, vector<int>());
    for (int i = 1; i <= n; i ++) {
        for (int j = i; j <= n; j += i) {
            g[j].emplace_back(i);
        }
    }

    vector<double> dp(n + 1);
    for (int i = n; i >= 1; i --) {
        double s1 = 0.0, s2 = 0.0;
        for (auto &u : g[i]) {
            s1 += p[u];
        }

        for (int j = 2 * i, k = 2; j <= n; j += i, k ++) {
            for (auto &u : g[i]) {
                i64 x = 1ll * u * k;
                if (lcm(x, i) == j) {
                    dp[i] += p[x] * (dp[j] + 1);
                    s2 += p[x];
                }
            }
        }

        dp[i] += 1.0 - s2;
        dp[i] /= (1 - s1);
    }

    cout << fixed << setprecision(10) << dp[1] - 1 << '\n';
    return 0;
}

F. Fair Distribution

题意：给你n栋楼，每栋楼的高度是G+R*k，G和R是定值，k任取且k>0，问你能否将n栋楼分成两组，每一组的楼的高度是上面按照公式任意取k，问你是否可以得到两组楼的高度之和相等的情况

思路：我们考虑如何求解，先考虑只有两栋楼，你要得到的是G1+R1*K1==G2+R2*K2,移项得：R1*K1-R2*K2==G2-G1,右边是常数，左边很经典就是ax+by，这个式子能组成的数字是gcd(x,y)的倍数，裴属定理证明的，然后我们可以扩展得到ax+by+cz+dp，这个可以得到的所有数字x满足x是gcd(x,y,z,p)的倍数，因此我们假设左边3个楼层为ax+w1,by+w2,cz+w3，令gc1=gcd(x,y,z),sumw=w1+w2+w3，能组成的高度和那么就是k*gc1+sumw,右边集合类似我们设为k2*gc2+sumw2，那么你要让k*gc1+sumw==k2*gc2+sumw2,移项得到k*gc1-k2*gc2==sumw2-sumw，这个左边也是ax+by，设u=gcd(gc1,gc2)，能组成的也是u的倍数，因此答案应满足(sumw2-sumw) mod. u ==0那么你会发现，对于u来说是两个集合的gcd，那不就是总gcd，因此集合的划分不会影响这个，只会影响sumw和sumw2，因为1到2e5，那么直接枚举即可，当然前提是你枚举的这个sumw必须能被凑出来，那么我们可以01背包来求解嘛，但是n是2e5，值域也是2e5，那么会tle，我们发现和最多是2e5，那么不同种类的就最多根号级别个，就可以转化为多重背包，2进制优化再变为01背包，这是你的物品数最多就是sqrt(n)*log(sqrt(n)),就可以直接01背包搞了

diamond：

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    int g = 0, s = 0;
    const int N = 2e5 + 10;

    set<int> object;
    vector<int> num(N);
    for (int i = 1; i <= n; i ++) {
        int G, R;
        cin >> G >> R;
        s += G;
        g = gcd(R, g);
        object.insert(G);
        num[G] ++;
    }

    if (n == 1) {
        cout << "N\n";
        return 0;
    }

    vector<int> dp(s + 1);

    dp[0] = 1;
    for (auto &i : object) {
        int has = num[i];
        for (int k = 1; k <= has; k <<= 1) {
            has -= k;
            i64 w = k * i;
            for (int j = s; j >= w; j --)
                dp[j] |= dp[j - w];
        }
        if (has) {
            i64 w = has * i;
            for (int j = s; j >= w; j --)
                dp[j] |= dp[j - w];
        }
    }

    i64 ans = 0, f = object.count(0);
    f ^= 1;
    for (int i = f; i <= s - f; i ++) {
        if (dp[i]) {
            if (abs(s - 2 * i) % g == 0) {
                cout << "Y\n";
                return 0;
            }
        }
    }

    cout << "N\n";

    return 0;
}