Codeforces Round 1046 (Div. 1)

Codeforces Round 1046 (Div. 1)

Date 2025.08.29

A	B	C	D1	D2	E1	E2	F
O	O	O	Ø	Ø

D1 - From the Unknown (Easy Version)

唉唉自己构造还是个本质彩笔，要是能想到 $(L, x)$ 这样构造就好了

翻译下题解

在第一次查询中，我们输入 $10^5$ 个 $1$。结果将等于

$$
r_1 = \left\lceil \frac{10^5}{W} \right\rceil.
$$

通过解方程

$$
\left\lceil \frac{10^5}{x} \right\rceil = r_1,
$$

我们可以得到

$$
W \in \left[ \left\lceil \tfrac{10^5}{r_1} \right\rceil, \left\lceil \tfrac{10^5}{r_1 - 1} \right\rceil - 1 \right].
$$

例如：

• 若 $r_1 = 1$，则 $W = 100,000$；
• 若 $r_1 = 2$，则 $W \in [50,000, 99,999]$；
• 若 $r_1 = 3$，则 $W \in [33,334, 49,999]$；
• …

对于上面的每个区间 $[L, R]$，总有 $2 \cdot L > R$，这是因为

$$
\Bigl\lfloor \tfrac{n}{2L} \Bigr\rfloor = \Bigl\lfloor \tfrac{\lfloor n/L \rfloor}{2} \Bigr\rfloor \neq \Bigl\lfloor \tfrac{n}{L} \Bigr\rfloor.
$$

因此，我们可以在第二次查询中输入如下内容：

$$
[\underline{L, 1}, \underline{L, 2}, \ldots, \underline{L, R-L}].
$$

对于每个下划线组 $(L, x)$：

• 如果 $L + x \le W$，则该组的两个单词会显示在同一行；
• 否则，它们会显示在不同的行。

注意：$L + x + L > 2L > R \ge W$，所以对于每个 $1 \le x \le W - L$，组 $(L, x)$ 占一行；而对于 $W - L < x \le R - L$，组 $(L, x)$ 占两行。于是查询结果为

$$
r_2 = (W - L) + 2 \cdot (R - W).
$$

因此可以推出

$$
W = 2R - L - r_2.
$$

在该查询中我们需要使用

$$
n = 2 \cdot (R - L) \le 10^5
$$

个单词。

由此，我们在至多 2 次查询 中解决了该问题，这符合 Easy 版本的限制条件。

int ask(const auto &a) {
    cout << "? " << a.size();
    for (int x : a) cout << " " << x;
    cout << endl;
    int res; cin >> res; return res;
}

void solve() {
    const int n1 = 1e5;
    int r1 = ask(vector(n1, 1));

    if (r1 == 1) {
        cout << "! 100000\n";
        return;
    }

    int L = (n1 + r1 - 1) / r1;
    int R = (n1 + r1 - 2) / (r1 - 1) - 1;

    if (L == R) {
        cout << "! " << L << '\n';
        return;
    }

    vector<int> qry;
    for (int i = 1; i <= R - L; i++) {
        qry.eb(L); qry.eb(i);
    }

    int r2 = ask(qry);

    int ans = 2 * R - L - r2;

    cout << "! " << ans << endl;
}

D2 - From the Unknown (Hard Version)

翻译下题解

我们希望减少 articles 的总长度。因此，新的第一次查询策略是：输入 $N$ 个 $B$，其中 $N$ 和 $B$ 都是尚未确定的常数。
那么，第一次查询的结果为：
$$
r_1 = \left\lceil \frac{N}{\left\lfloor \tfrac{W}{B} \right\rfloor} \right\rceil.
$$

• 如果 $W \in [1, B - 1]$，编辑器将无法显示 article，不幸的是，我们原本的第二次查询策略在这种情况下行不通。但我们仍然可以继续使用第一次查询的策略！此时我们可以查询 $B^2$ 个 $1$，并且可以很容易证明，对于每个 $W=1,2,\ldots,B-1$，得到的结果都是不同的。

  设
  $$
  f(W)=\left\lceil \frac{B^2}{W}\right\rceil,\quad W=1,2,\ldots,B-1.
  $$
  只要证明对任意相邻的 $W$ 与 $W+1$，都有 $f(W) > f(W+1)$，那么 ${f(W)}$ 自然两两不同。
  计算两项之间的“间隔”：
  $$
  \frac{B^2}{W}-\frac{B^2}{W+1}=\frac{B^2}{W(W+1)}.
  $$
  当 $1\le W\le B-1$ 时，有
  $$
  \frac{B^2}{W(W+1)} \ge \frac{B^2}{(B-1)B} = \frac{B}{B-1} > 1.
  $$
  也就是说，$\frac{B^2}{W}$ 与 $\frac{B^2}{W+1}$ 这两个实数相差严格超过 1。因此它们不可能落在同一个长度为 1 的区间 $(k-1,k]$ 内（对任意整数 $k$）。而上取整函数 $\lceil\cdot\rceil$正是把实数归入这样的单位区间对应的整数里，所以
  $$
  \left\lceil \frac{B^2}{W}\right\rceil \ge \left\lceil \frac{B^2}{W+1}\right\rceil + 1,
  $$
  特别地，$f(W) > f(W+1)$。
  由此，$W=1,2,\ldots,B-1$ 时的所有取值 $f(W)$ 严格递减，因而两两不同。这就证明了“对于 $W=1,2,\ldots,B-1$，结果值都不同”。

• 否则，如果 $W \in [B, 10^5]$，与 Easy 版本类似，我们会得到一个区间 $[L, R]$，并且总有 $2L \ge R$。接着我们可以使用 Easy 版本中第二次查询的相同策略，并用 $2\cdot (R-L)$ 次查询得到解。要计算 $L$ 和 $R$，可以直接用二分查找，或者通过推导得到：

$$
W \in \left[B \cdot \left(\left\lfloor \tfrac{N-1}{r} \right\rfloor + 1\right), B \cdot \left(\left\lfloor \tfrac{N-1}{r-1} \right\rfloor + 1\right) - 1 \right].
$$

还要注意，最右侧的区间会被 $10^5$ 这个上界截断。

我们可以使用暴力枚举来找到合适的 $N$ 和 $B$。在正式的正确解法中，选择 $N = 11343$，$B = 116$，此时最大区间长度为 $6263$。因此，articles 的总长度不会超过：

$$
11343 + \max(2 \cdot 6263, 116^2) = 24799 \le 25000.
$$

通过一些进一步优化，可以把 $116^2$ 稍微降低到 $\le 12,526$，这样总长度可以减少到 $23,869$，不过其实并不需要。

int ask(const auto &a) {
    cout << "? " << a.size();
    for (int x : a) cout << " " << x;
    cout << endl;
    int res; cin >> res; return res;
}

void solve() {
    const int N = 11343;
    const int B = 116;
    int r1 = ask(vector(N, B));

    int ans;

    if (r1 == 0) {
        int r2 = ask(vector(B * B, 1));

        ans = (B * B + r2 - 1) / r2;
    } else {
        int L = B * ((N - 1) / r1 + 1);
        int R = B * ((N - 1) / (r1 - 1) + 1) - 1;
        R = min(R, 100000LL);

        if (L == R) {
            cout << "! " << L << '\n';
            return;
        }

        vector<int> qry;
        for (int i = 1; i <= R - L; i++) {
            qry.eb(L); qry.eb(i);
        }

        int r2 = ask(qry);
        ans = 2 * R - L - r2;
    }
    
    cout << "! " << ans << endl;
}

C - By the Assignment

比较简单懒得写了，翻译下题解

首先，只考虑一个简单环，记其长度为 $l$。在环上任选两个点 $u$ 和 $v$，会得到两条不同的简单路径。对所有 $(u, v)$，这两条路径的值相等。这意味着：对于环上所有大小为 $l-2$ 的点集，它们的节点权值的按位异或结果应当等于 $0$。

因此，环上的所有节点权值必须相同。进一步，如果 $l$ 是奇数，可以验证环上节点的权值必须等于 $0$；如果 $l$ 是偶数，则权值可以是区间 $[0, V)$ 内的任意整数。

通过将图分解为 边双连通分量，就能方便地判断两个节点是否在同一个环上——只要它们属于同一个分量即可。答案在不同分量之间相互独立，所以只需把各个分量的答案相乘。

如何计算一个双边连通分量的答案？

• 首先，该分量内所有节点权值必须相等；
• 然后，如果存在奇环（可通过 二分图染色 检测），则节点权值必须为 $0$；
• 因此答案只有三种可能：$0$、$1$ 或 $V$。

综上，就可以高效地计算出原问题的答案。

时间复杂度：每个测试用例 $\mathcal{O}(n+m)$。

void solve() {
    int n = read(), m = read(), V = read();

    vector<int> a(n);
    for (auto &x : a) x = read();

    vector<pii> edges(m);
    vector<vector<pii>> g(n);
    for (int i = 0; i < m; i++) {
        auto &[u, v] = edges[i];
        u = read() - 1, v = read() - 1;
        g[u].eb(v, i), g[v].eb(u, i);
    }

    vector<int> dfn(n), low(n), isBridge(m);
    int timer = 0;
    auto dfs = [&](this auto &&dfs, int u, int las) -> void {
        dfn[u] = low[u] = ++timer;
        for (auto [v, id] : g[u]) {
            if (id == las) continue;
            if (!dfn[v]) {
                dfs(v, id);
                low[u] = min(low[u], low[v]);
                if (low[v] > dfn[u]) isBridge[id] = 1;
            } else {
                low[u] = min(low[u], dfn[v]);
            }
        }
    };
    dfs(0, -1);
    

    vector<vector<int>> G(n);
    vector<int> inG(n);
    for (int i = 0; i < m; i++) {
        if (isBridge[i]) continue;
        auto [u, v] = edges[i];
        G[u].eb(v), G[v].eb(u);
        inG[u] = inG[v] = 1;
    }

    int coef = 0;
    vector<int> vis(n, 0), color(n, -1);

    for (int s = 0; s < n; ++s) {
        if (vis[s] or !inG[s]) continue;

        queue<int> q;
        vector<int> t;

        bool flag = 1;
        vis[s] = 1, color[s] = 0;
        q.ep(s);

        while (!q.empty()) {
            int u = q.front(); q.pop();
            t.eb(u);
            for (int v : G[u]) {
                if (!vis[v]) {
                    vis[v] = 1;
                    color[v] = color[u] ^ 1;
                    q.ep(v);
                } else if (color[v] == color[u]) {
                    flag = 0;
                }
            }
        }

        if (!flag) {
            for (int v : t) {
                if (a[v] != -1 and a[v] != 0) {
                    cout << "0\n"; return;
                }
            }
        } else {
            int val = -1;

            for (int v : t) {
                if (a[v] == -1) continue;

                if (val == -1) {
                    val = a[v];
                } else if (val != a[v]) { 
                    cout << "0\n"; return;
                }
            }

            if (val == -1) {
                coef++;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        if (inG[i]) continue;
        if (a[i] == -1) coef++;
    }

    cout << power(Z(V), coef) << '\n';
}

B - For the Champion

比较简单懒得写了，翻译下题解

记 $V = 10^9$。我们先执行四次操作：$(\texttt{L}, V)$、$(\texttt{L}, V)$、$(\texttt{U}, V)$、$(\texttt{U}, V)$。由于最初 $-V \leq X, Y \leq V$，经过这四次操作后，可以保证 $X’, Y’ \leq -V$。

这样一来，从评测系统得到的当前值就是：

$$
\min_{1 \leq i \leq n}\bigl(\lvert x_i - X’\rvert + \lvert y_i - Y’\rvert\bigr)
= \min_{1 \leq i \leq n}\bigl(x_i - X’ + y_i - Y’\bigr),
$$

这进一步等于

$$
\min_{1 \leq i \leq n}(x_i + y_i) - X - Y + 4V.
$$

因此，我们得到了 $X+Y$ 的值。

同理，如果我们移动到右上角（或左下角），就能得到 $X-Y$ 的值。这只需要再执行 $4$ 步（向下或向右），而不是 $4+4$。有了 $X+Y$ 和 $X-Y$，就可以直接解出 $X$ 和 $Y$。

综上，每个测试用例我们只需使用 $8$ 次操作，就足够通过了。

void solve() {
    int n = read();
    vector<pii> a(n);
    for (auto &[x, y] : a) cin >> x >> y;

    int s = -inf, d = -inf;
    for (auto [x, y] : a) {
        s = max(s, x + y);
        d = max(d, x - y);
    }

    int B = 1e9;
    ask('R', K); ask('R', K); ask('U', K);
    int u1 = ask('U', K);

    ask('D', K); ask('D', K); ask('D', K);
    int u2 = ask('D', K);

    int u = u1 - 4 * B + s;
    int v = u2 - 4 * B + d;

    int x = (u + v) / 2;
    int y = (u - v) / 2;

    cout << "! " << x << " " << y << endl;
}

A - Against the Difference

比较简单懒得写了，翻译下题解

我们来使用动态规划（DP）。设 $dp(i)$ 表示前缀 $[a_1, a_2, \ldots, a_i]$ 的最长 整洁子序列 的长度。显然有：

$$
dp(0) \leq dp(1) \leq \ldots \leq dp(n).
$$

假设我们已经计算出了 $dp(0), dp(1), \ldots, dp(i-1)$。现在来考虑如何计算 $dp(i)$：

1. 如果 $a_i$ 没有被选入整洁子序列，那么我们直接用 $dp(i-1)$ 更新 $dp(i)$；
2. 如果 $a_i$ 被选入整洁子序列，那么该子序列必须以 $a_i$ 个值等于 $a_i$ 的元素结尾。由于 $dp$ 数组是单调的，我们应该贪心地找到在 $[a_1, \ldots, a_i]$ 中，第 $a_i$ 次出现的 $a_i$ 的下标 $x$，然后用 $dp(x-1) + a_i$ 更新 $dp(i)$。

于是，最终得到：

$$
dp(i) = \max\bigl(dp(i-1),; dp(x-1) + a_i\bigr).
$$

为了高效找到 $x$，我们可以为每个不同的数值预先存储它们出现的位置。

时间复杂度：每个测试用例 $\mathcal{O}(n)$。

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

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

    vector<vector<int>> pos(n + 1);
    vector<int> dp(n + 1);

    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1];

        int x = a[i];
        pos[x].push_back(i);

        if (pos[x].size() >= x) {
            int st = pos[x][pos[x].size() - x];
            int res = dp[st - 1] + x;
            dp[i] = max(dp[i], res);
        }
    }

    cout << dp[n] << '\n';
}