Codeforces Round 1045 (Div. 2)

Codeforces Round 1045 (Div. 2)

Date 2025.08.26

A	B	C	D	E	F
O	O	O	Ø	Ø

E - Power Boxes

根据题意，设 $d_i = throw(i)$，可以得到

$$
d_i = 1 + d_{i + a_i}
$$

因为 $a_i$ 要么是 $1$ 要么是 $2$，

倒着确定 $a_i$，当 $d_{i + 1} \neq d_{i + 2}$ 时，我们可以直接通过 $d_i$ 和 $d_{i + 1}$ 和 $d_{i + 2}$ 的关系确定 $a_i$。

难点在于当 $d_{i+1} = d_{i+2}$ 的情况。我们称这样的下标 $i$ 为未知，此时我们可以在不进行查询的情况下推导出 $d_i$，从而将查询机会留到后面使用。下面是一个关键的观察：

观察： 不存在两个相邻的未知下标。

证明： 如果 $i$ 是未知的，那么 $d_i = d_{i+1} + 1$，因此 $d_i \neq d_{i+1}$。所以 $i-1$ 不可能是未知的。

为了利用这一事实，我们采用如下策略：
在计算出所有的 $d_i$ 之后，对每一个未知下标 $i$（按从小到大的顺序），交换位置 $i$ 与 $i+1$ 的盒子，然后对坐标 $i+1$ 进行一次投掷查询。由于 $i+1$ 不是未知的，这样能够揭示 $a_i$。特殊情况是 $i = n$：这里我们交换 $n-1$ 与 $n$ 的盒子，然后对坐标 $n-1$ 进行一次投掷查询来获得 $a_n$。

总结一下流程：

• 从 $n$ 到 $1$ 依次：
  对坐标 $i$ 进行投掷查询。
  如果 $d_{i+1} = d_{i+2}$，则跳过对 $i$ 的查询，并将其标记为未知（但依然计算 $d_i$）；否则，直接确定 $a_i$ 和 $d_i$。
• 对于每个 $i$ 从 $1$ 到 $n-1$：
  若 $i$ 是未知的，则交换盒子 $i$ 与 $i+1$，并在坐标 $i+1$ 上进行一次投掷查询，从而获得 $a_i$。
• 最后，交换 $n-1$ 与 $n$，并在坐标 $n-1$ 上进行一次投掷查询确定 $a_n$。

对于每一个未知下标，我们需要用 2 次查询；对于已知下标，只需 1 次查询。由于不存在两个相邻的未知下标，未知下标的数量最多为 $\lceil \frac{n}{2} \rceil$。因此，总的查询次数至多为

$$
\left\lceil \frac{3n}{2} \right\rceil.
$$

int cnt = 0;
int ask(int x) {
    cnt++;
    cout << "throw " << x << endl;
    int res; cin >> res;
    return res;
};
void swap(int x) {
    cnt++;
    cout << "swap " << x << endl;
};

void solve() {
    cnt = 0;
    int n; cin >> n;

    vector<int> a(n + 3), f(n + 3);
    f[n] = 1;

    for (int i = n; i >= 1; i--) {
        if (f[i + 1] == f[i + 2]) {
            f[i] = f[i + 1] + 1;
        } else {
            f[i] = ask(i);

            if (f[i] == f[i + 1] + 1) {
                a[i] = 1;
            } else {
                a[i] = 2;
            }
        }
    }

    for (int i = 1; i + 1 <= n; i++) {
        if (a[i]) continue;

        swap(i);
        int t = ask(i + 1);
        if (t == f[i + 2] + 1) {
            a[i] = 1;
        } else {
            a[i] = 2;
        }
    }

    swap(n - 1);
    int t = ask(n - 1);
    if (t == 2) {
        a[n] = 1;
    } else {
        a[n] = 2;
    }

    cout << '!';
    for (int i = 1; i <= n; i++) cout << ' ' << a[i];
    cout << endl;

    assert(cnt <= ((3 * n + 2) / 2));
}

D - Sliding Tree

每次操作最多只能把直径 +1

最终结果是把直径变成 n

所以每次都让直径 +1 即可

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

    vector<int> deg(n + 1);
    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        g[u].eb(v); deg[u]++;
        g[v].eb(u); deg[v]++;
    }
    
    vector<int> dis(n + 1), par(n + 1);
    auto dfs = [&](this auto&& self, int u, int fa) -> void {
        dis[u] = dis[fa] + 1;
        par[u] = fa;
        for (int v : g[u]) if (v != fa) {
            dis[v] = dis[u] + 1;
            self(v, u);
        }
    };

    dfs(1, 0);
    int x = ranges::max_element(dis) - dis.begin();
    dfs(x, 0);
    int y = ranges::max_element(dis) - dis.begin();

    if (dis[y] == n) { cout << "-1\n"; return; }

    vector<int> ond(n + 1);
    for (int t = y; t; t = par[t]) ond[t] = 1;

    int a = -1, b = -1, c = -1;
    for (int u = 1; u <= n; u++) {
        for (int v : g[u]) {
            if (ond[u] and !ond[v]) {
                a = par[u];
                b = u;
                c = v;
                
                cout << a << ' ' << b << ' ' << c << "\n";
                return;
            }
        }
    }
}

C - Even Larger

保证 2 和 3 的情况即可

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

    vector<int> a(n + 5);
    for (int i = 1; i <= n; i++) a[i] = read();

    int tot = 0;
    for (int i = 1; i <= n; i++) tot += a[i];

    a[0] = a[n + 1] = inf;
    for (int i = 1; i <= n; i += 2) {
        a[i] = min({a[i - 1], a[i], a[i + 1]});
    }

    for (int i = 2; i <= n; i += 2) {
        if (i + 1 > n) break;
        if (a[i - 1] + a[i + 1] <= a[i]) continue;

        a[i + 1] = a[i] - a[i - 1];
    }

    for (int i = 1; i <= n; i++) tot -= a[i];

    cout << tot << '\n';
}

B - Add 0 or K

在 mod (k + 1) 的意义下， +k 相当于 -1

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

    vector<int> a(n);
    for (auto &x : a) x = read();
    for (auto &x : a) x += (x % (k + 1)) * k;

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

A - Painting With Two Colors

判断下奇偶性和相对大小即可

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

    if (n % 2 == b % 2 and b >= a) {
        cout << "YES\n";
        return;
    } else if (n % 2 == b % 2 and n % 2 == a % 2) {
        cout << "YES\n";
        return;
    }
    cout << "NO\n";
}