Codeforces Round 992 (Div. 2)

比赛链接

Problems	AC
A. Game of Division	○
B. Paint a Strip	○
C. Ordered Permutations	○
D. Non Prime Tree	⊕
E. Control of Randomness	⊕
F. Number of Cubes

A

Code >folded

void solve() {
    int n = read();
    int k = read();

    vector<int> a(n + 1);
    vector<vector<int>> cnt(k);
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        cnt[a[i] % k].eb(i);
    }

    for (int i = 0; i < k; i++) {
        if (cnt[i].size() == 1) {
            puts("YES");
            cout << cnt[i][0] << '\n';
            return;
        }
    }

    puts("NO");
}

B

Code >folded

void solve() {
    int n = read();

    int ans = 1;
    int now = 1;
    while (now < n) {
        ans++;
        now = (now + 1) * 2LL;
    }
    cout << ans << '\n';
}

C

Code >folded

void solve() {
    int n = read();
    int k = read() - 1;

    if (n <= 60 and k >= (1LL << (n - 1))) {
        cout << "-1\n";
        return;
    }

    vector<int> p(n);
    int l = 0, r = n - 1;
    for (int i = 1; i < n; i++) {
        if (n - 1 - i > 60 or k < (1LL << (n - 1 - i))) {
            p[l++] = i;
        } else {
            p[r--] = i;
            k -= 1LL << (n - 1 - i);
        }
    }
    p[l] = n;
    // cout << p << '\n';
    for (int i = 0; i < n; i++) {
        cout << p[i] << " \n"[i == n - 1];
    }
}

D

给定一棵有 $n$ 个顶点的树。

您需要构造一个长度为 $n$ 的数组 $a _ 1, a _ 2, \ldots, a _ n$ ，该数组由从 $1$ 到 $2 \cdot n$ 的唯一整数组成，并且对于树的每个边 $u _ i \leftrightarrow v _ i$ ，值 $|a _ {u _ i} - a _ {v _ i}|$ 都不是素数。

查找满足这些条件的任何数组，或报告不存在这样的数组。

注意到，$1$ 和 $4$ 是质数。

一种构造方法是，先选择一条主链，全部填上差值为 $1$ 的，然后对于这条链上点 $u$ 分出来的其他链，分解成类似的子问题，只需要保证链的开头和 $a_u$ 相差至少是 $4$ 即可。

还有一种方法是黑白染色，按层数放偶数。

Code

void solve() {
    int n = read();

    vector<vector<int>> g(n + 1);

    for (int i = 1; i < n; i++) {
        int u = read();
        int v = read();
        g[u].eb(v), g[v].eb(u);
    }

    vector<int> a(n + 1);

    int t = 1;

    auto dfs = [&](auto&& self, int u, int fa) -> void {
        a[u] = t;
        bool first = 1;
        for (auto v : g[u]) {
            if (v == fa) continue;

            if (first) {
                first = 0;
                t++;
                self(self, v, u);
                t++;
            } else {
                t += 2;
                self(self, v, u);
            }

        }
    };

    dfs(dfs, 1, 0);

    for (int i = 1; i <= n; i++) {
        cout << a[i] << " \n"[i == n];
    }

}

E

给你一棵有 $n$ 个顶点的树。

让我们将机器人放置在某个顶点 $v \ne 1$ 处，假设我们最初有 $p$ 枚硬币。考虑以下过程，其中在第 $i$ 步(从 $i = 1$ 开始)：

• 如果 $i$ 为奇数，机器人将移动到顶点 $1$ 方向上的相邻顶点；
• 否则， $i$ 为偶数。你可以支付一枚硬币(如果还剩下一些)，然后机器人移动到顶点 $1$ 方向上的相邻顶点，或者不支付，然后机器人移动到随机均匀选择的相邻顶点。

一旦机器人到达顶点 $1$ ，该过程就会停止。如果我们以最佳方式花费硬币，则让 $f(v, p)$ 成为上述过程中可能所需的最小步数。

回答 $q$ 个查询，其中的 $i$ 个查询必须找到 $f(v _ i, p _ i)$ 的值，模数为 $^{\text{∗}}$ $998\,244\,353$ 。

谔谔赛时降智严重，没看出来是那个网络赛就被秒了的模型，我说我柿子怎么那么混乱。

网络赛那个是手动设立一个阈值，在阈值之前免费但概率收益，在阈值之后花费金币稳定收益。

类似的，在这个题中，开始花费金币了，就会一直用金币了。

设一个点的度数为 $d$，两种选择分别可以看作：

• 花费 $1$ 金币，步数 $+2$，向上走 $2$ 格。
• 花费 $0$ 金币，那么有 $\frac{1}{d}$ 的概率向上走 $2$ 格，也就是期望 $d$ 次后向上走两个。即花费 $0$ 金币，步数 $+2d$，向上走 $2$ 格。

令 $v$ 是 $u$ 的下家，$fa$ 是 $u$ 的父亲：

$$
dp[v][p] = \min\lbrace dp[fa][p] + 2d, dp[fa][p - 1] + 2 \rbrace
$$

Code

void solve() {
    int n = read();
    int q = read();

    vector<vector<int>> g(n + 1);

    for (int i = 1; i < n; i++) {
        int u = read();
        int v = read();
        g[u].eb(v), g[v].eb(u);
    }

    vector dp(n + 1, vector(n + 1, inf));

    auto dfs = [&](auto&& self, int u, int fa) -> void {
        int d = g[u].size();
        for (auto v : g[u]) {
            if (v == fa) continue;

            if (u == 1) {
                fill(dp[v].begin(), dp[v].end(), 1);
            } else {
                for (int p = 0; p <= n; p++) {
                    dp[v][p] = dp[fa][p] + 2 * d;
                    if (p) {
                        dp[v][p] = min(dp[v][p], dp[fa][p - 1] + 2);
                    }
                }
            }

            self(self, v, u);
        }

        // cerr << dp[u] << '\n';
    };

    fill(dp[1].begin(), dp[1].end(), 0);
    dfs(dfs, 1, 0);

    while (q--) {
        int u = read();
        int k = read();
        cout << dp[u][k] << '\n';
    }

}