2024杭电多校第9场

9

1001 树异或价值 （hdu7529）

对价值定义式进行转化，\((a_i\oplus a_j)\times lca(a_i, a_j)\) 可视为 \(a_i,a_j\) 的所有祖先下 \(\sum a_i\oplus a_j\)，数组 \(a\) 总价值即各节点子树中任意两个子节点的异或之和。由按位异或的性质，不同二进制位之间答案互不影响，可简化考虑最低位即 \(a_i\in \{0, 1\}\)，计算出此时的 \(ans'\)，有 \(ans = (ans')^k\).

\(a_i\in \{0, 1\}\) 时，为了使异或之和尽可能大，即各节点子树内 \((\sum [a=0])\times (\sum [a=1])\) 最大，应使 \(a = 0\) 与 \(a = 1\) 子节点数量尽可能平均；实际上通过构造可实现所有节点下 \(\mid\sum[a = 0] - \sum[a = 1])\mid\space \leq 1\). 设 \(dp_x\) 为 \(a_x = 0\) 时子树符合条件的答案数，\(y\in subtree(x)\)，\(se_x,so_x\)分别代表大小为偶数/奇数的 \(y\) 数量，则有：

\(dp_x =\prod dp_y \times 2^{se_x}\times (\dbinom{so_x}{\lfloor\frac{so_x}{2}\rfloor} + \dbinom{so_x}{\frac{so_x}{2} - 1}\times [2|so_x])\).

最终答案即 \((2\times dp_1)^k\). 组合数学的逻辑多少有点抽象，建个模理解一下式子就好，至少代码不难写。

void pre(int i) {
    sz[i] = 1;
    s0[i] = s1[i] = 0;
    for(int j = 0; j < v[i].size(); j++) {
        int t = v[i][j];
        pre(t);
        sz[i] += sz[t];
        if(sz[t] & 1) s1[i]++;
        else s0[i]++;
    }
}
void cal(int i) {
    dp[i] = 1;
    for(int j = 0; j < v[i].size(); j++) {
        int t = v[i][j];
        cal(t);
        dp[i] *= dp[t];
        dp[i] %= mo;
    }
    dp[i] *= fp(2, s0[i]);
    dp[i] %= mo;
    dp[i] *= (c(s1[i], s1[i] / 2) + ((s1[i] & 1) == 0) * c(s1[i], s1[i] / 2 - 1)) % mo;
    dp[i] %= mo;
}

1003 黑洞合并 （hdu7531）

真抽象啊，这个《规律》是赛时我发现了都不敢提出来的程度。把它写这里纯粹是为了纪念我写过这么一道抽象的题目（）

1006 融合矿石 （hdu7534）

非常巧妙的dp. 数据保证随着金辉石占比的增加，矿石价值单调不减，且矿石的数量无限，因此用完全背包预处理出所有可能的融合情况下、一定质量矿石的最大金辉石含量，将结果看作 \(m\) 种不同的新矿石，再用一次完全背包计算即可。

    for(int i = 1; i <= n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        for(int j = a; j <= m; j++) {
            f[j] = max(f[j], f[j - a] + b);
        }
    }
    for(int i = 1; i <= m; i++) {
        if(!f[i]) continue;
        int x = (f[i] * 10 - 1) / i + 1;
        f[i] = v[x] * i;
    }
    for(int i = 1; i <= m; i++) {
        for(int j = i; j <= m; j++) {
            g[j] = max(g[j], g[j - i] + f[i]);
        }
    }
    printf("%lld\n", g[m]);