「题解」Codeforces Round 1090 (Div. 4)

有一说一这是我时隔一万年以来再一次写题解的重要时刻。鉴于此我先写一场 D4 的题解来检验一下风水。

比赛链接

A.

给定 $x$ ($-67 \le x \le 67$)，求 $y$ 满足 $-67 \le y \le 67$ 使得 $\min(x, y)$ 最大。

显然直接输出 $67$ 就可以了。

B.

给定 $7$ 个整数 $a_1, a_2, \cdots, a_7$，你需要将其中的六个整数乘以 $-1$，求这些整数和的最大值。

直接写就可以了。

void solve() {
    array<int, 7> a;
    int cur = 0;
    for (auto &x : a) {
        cin >> x;
        cur -= x;
    }
    int ans = -1e18;
    for (auto x : a) {
        ans = max(ans, cur + 2 * x);
    }
    cout << ans << "\n";
}

C.

构造长度为 $3n$ 的排列使得 $\displaystyle\sum_{i=0}^{n-1}\operatorname{median}(a_{3i+1}, a_{3i+2}, a_{3i+3})$ 最大。

我们手玩几个样例就不难发现结论。证明略。

void solve() {
    int n;
    cin >> n;
    vector<int> a(3 * n);
    int p = 1;
    for (int i = 0; i < n; i++) {
        a[i * 3] = p++;
    }
    for (int i = 0; i < 3 * n; i++) {
        if (!a[i])
            a[i] = p++;
        cout << a[i] << " ";
    }
    cout << "\n";
}

D.

构造长度为 $n$ ($2 \le n \le 10^4$) 的数列 $a$ 使得 $\gcd(a_i, a_{i+1})$ 两两不同。

注意到 $2\times10^5$ 范围内肯定有 $10^4$ 个素数，我们就令相邻 $\gcd$ 为素数即可。然后运用经典的构造方法：当前值会等于与前一个元素的 $\gcd$ 和与后一个元素的 $\gcd$ 的最小公倍数。这里因为都是素数所以直接乘起来就可以了。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    cout << pri[0] << " ";
    for (int i = 1; i < n; i++)
        cout << pri[i - 1] * pri[i] << " ";
    cout << "\n";
}

E.

给定一个长度为 $n$ 的数列 $a$，执行 $n-1$ 次选择一个 $i$ ($1 \le i \le |a|$)，然后对于所有 $1 \le j \le |a|$ 有 $a_j \gets a_j \oplus a_i$，然后删除 $a_i$，问最后剩余的元素的最大值。

不难考虑：假设我们有元素 $[x, y, z]$，我们第一步选了 $x$，那么数组变成 $[y\oplus x, z \oplus x]$，然后第二步选 $y\oplus x$，数组就变成 $[z\oplus y \oplus x \oplus x]=[z\oplus y]$。总之就是根据异或的特性我们先前选的值是可以抵消的，所以等效于找两个 $x, y$ 使得 $x\oplus y$ 最大。鉴于 $n \approx 3\times10^3$ 我们直接 $O(n^2)$ 做就可以了。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++)
            ans = max(ans, a[i] ^ a[j]);
    }
    cout << ans << "\n";
}

F.

构造一个有 $x+y$ 个节点的以 $1$ 为根节点的树，使得其有 $x$ 节点子树大小为偶数，$y$ 个节点子树大小为奇数。

观察发现：

1. 没有孤立的偶节点，所有的偶节点必然有一个奇子树；
2. 偶子树加到任意的父节点都不会改变父节点的奇偶性；
3. 那么我们可以只考虑奇节点作为子节点的情况：若有偶数个奇节点，那么父亲是奇节点，否则是偶节点。

于是我们立即得出：

1. 若 $x>y$ 则无解；
2. 若 $x=0$，只有 $y$ 是奇数才有解（$1$ 连其他的节点），否则根据 3，不存在这样的情况；
3. 再令 $y \gets y - x$，此时讨论 $y$ 的奇偶性：若为奇数那么我们令 $1$ 为奇节点，然后剩余节点全连 $1$ 就可以了；若为偶数那么我们随便加到某个偶节点的下面。

具体见代码：

void solve() {
    int x, y;
    cin >> x >> y;
    if (x > y) {
        cout << "NO\n";
        return;
    }
    if (x == 0) {
        if (y % 2 == 0) {
            cout << "NO\n";
            return;
        }
        cout << "YES\n";
        for (int i = 2; i <= x + y; i++) {
            cout << "1 " << i << "\n";
        }
        return;
    }
    y -= x;
    int p = x;
    cout << "YES\n";
    if (y % 2 == 0) {
        for (int i = 1; i <= x; i++) {
            cout << i << " " << ++p << "\n";
        }
        for (int i = 2; i <= x; i++)
            cout << 1 << " " << i << "\n";
        for (int i = 0; i < y; i++)
            cout << 1 << " " << ++p << "\n";
    } else {
        p++;
        for (int i = 2; i <= x + 1; i++)
            cout << i << " " << ++p << "\n";
        for (int i = 2; i <= x + 1; i++)
            cout << 1 << " " << i << "\n";
        for (int i = 1; i < y; i++)
            cout << 1 << " " << ++p << "\n";
    }
}

G.

求满足条件的长度为 $n$ 的 $a$ 数组的方案数量。条件为：

给定最后坐下的时刻 $b$。

1. 若 $a_i=0$，则第 $i$ 个人在 $0$ 时刻坐下；
2. 若 $a_i>0$，则第 $i$ 个人会在 $a_i$ 时刻坐下，当且仅当「在 $t$ 时刻之前坐下的人不少于 $a_i$」并且「在 $t$ 时刻之前至少有一个相邻位置的人坐下」。

根据乘法原理我们只需要把每一种 $a_i$ 的可能乘起来就好了。接下来我们对满足 $b_i$ 的条件进行分讨：

设 $C_t$ 为时刻 $t$ 之前已经坐下的人数。对于当前位置 $i$，记 $b_i=t$。若 $t=0$，显然只能有 $a_i=0$，贡献为 $1$。下面只考虑 $t>0$ 的情况。设 $d$ 为相邻位置中最早坐下的时刻，则相邻位置这一条件最早会在 $r=d+1$ 时成立，因为要求相邻位置的人必须在严格更早的时刻已经坐下。于是分三种情况：

• 若 $r>t$，说明到时刻 $t$ 还没有相邻位置的人提前坐下，显然无解，贡献为 $0$；
• 若 $r=t$，说明相邻位置条件恰好在时刻 $t$ 第一次满足，此前不可能提前坐下，因此只需人数条件成立即可，即 $1\le a_i\le C_t$，贡献为 $C_t$；
• 若 $r<t$，说明相邻位置条件更早就已经满足。为了保证不会提前坐下，人数条件必须恰好在时刻 $t$ 才第一次满足，即 $C_{t-1}<a_i\le C_t$，贡献为 $C_t-C_{t-1}$。

最后把所有位置的贡献乘起来即可。

#include <bits/stdc++.h>
using namespace std;

#define int long long

constexpr int MOD = 676767677;

int T{0};
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> b(n), cnt(m);
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        cnt[b[i]]++;
    }
    vector<int> C(m + 1);
    for (int i = 1; i <= m; i++) {
        C[i] = C[i - 1] + cnt[i - 1];
    }
    int ans = 1;
    for (int i = 0; i < n; i++) {
        int t = b[i];
        if (t == 0)
            continue;
        int d = 1e18;
        if (i > 0)
            d = min(d, b[i - 1]);
        if (i < n - 1)
            d = min(d, b[i + 1]);
        int r = d + 1;
        int w = 0;
        if (r > t)
            w = 0;
        else if (r == t)
            w = C[t];
        else
            w = C[t] - C[t - 1];
        ans = ans * w % MOD;
    }
    cout << ans % MOD << "\n";
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    if (!T)
        cin >> T;
    while (T--)
        solve();
}