1931(925div3)

A. Recovering a Small String

$a - z \to 1 - 26$ 给出 3 个字母的和，求字典序最小的 3 个字母

void solve() {
    int n;cin >> n;
    for (int i = 'a';i <= 'z';i++) {
        for (int j = 'a';j <= 'z';j++) {
            for (int k = 'a';k <= 'z';k++) {
                if (i + j + k - 'a' * 3 + 3 == n) {
                    cout << char(i) << char(j) << char(k) << '\n';return;
                }
            }
        }
    }
}

B. Make Equal

给出一个数组，其之和一定是 $n$ 的倍数，可选择 $i, j (i < j)$ 让 $a_{i} - = x, a_{j} + = x$ ，问是否存在每个数都相等的情况

void solve() {
    int n, sum = 0; cin >> n;
    vector<int> a(n);
    for (auto& i : a)cin >> i, sum += i;
    int eq = sum / n,cnt = 0;
    bool ok = true;
    for (int i = 0;i < n;i++) {
        if (a[i] >= eq) {
            cnt += a[i] - eq;
        } else {
            cnt -= eq - a[i];
            if (cnt < 0)ok = false;
        }
    }
    if (ok) {
        cout << "yes\n";
    } else {
        cout << "no\n";
    }
}

C. Make Equal Again

只能执行一次操作，给定区间加上任意值，求最少的区间长度

就看两边的就行

void solve() {
    int n;cin >> n;vector<int> a(n);
    for (auto& i : a)cin >> i;
    int cnt1 = 1, cnt2 = 1;
    for (int i = 1;i < n;i++) {
        if (a[i] == a[i - 1]) {
            cnt1++;
        } else break;
    }
    for (int i = n - 1;i >= 0;i--) {
        if (a[i] == a[i - 1]) {
            cnt2++;
        } else break;
    }
    if (cnt1 == cnt2 && cnt1 == n) {
        cout << 0 << '\n';return;
    }
    if (a[0] == a[n - 1]) {
        cout << n - (cnt1 + cnt2) << '\n';
    } else {
        cout << n - max(cnt1, cnt2) << '\n';
    }
}

D. Divisible Pairs

给出一个数组 $a$ ，求满足 $(a_{i} + a_{j}) % x = 0 \cap (a_{i} - a_{j}) % y = 0 (i < j)$ 的个数。

Solution

易得：

$(a_{i} % x + a_{j} % x) % x = 0, (a_{i} % y - a_{j} % y) % y = 0$
$\to a_{i} % x + a_{j} % x = x, a_{i} % y - a_{j} % y = 0$

存下 $a_{i} % x, a_{i} % y$ ,满足 $(x - a_{i} % x) % x \cap a_{i} % y$ 即为对应的条件

void solve() {
    int n, x, y;cin >> n >> x >> y;
    vector<int> a(n);
    for (auto& i : a)cin >> i;
    ll cnt = 0;
    map<pair<int, int>, int> mod;
    for (int i = 0;i < n;i++) {
        cnt += mod[{(x - a[i] % x) % x, a[i] % y}];
        mod[{a[i] % x, a[i] % y}]++;
    }
    cout << cnt << '\n';
}

或

void solve() {
    int n, x, y;cin >> n >> x >> y;
    vector<int> a(n);
    for (auto& i : a)cin >> i;
    ll cnt = 0;
    map<pair<int, int>, int> mod;
    for (int i = 0;i < n;i++) {
        mod[{a[i] % x, a[i] % y}]++;
    }
    for (int i = 0;i < n;i++) {
        --mod[{a[i] % x, a[i] % y}];
        cnt += mod[{(x - a[i] % x) % x, a[i] % y}];
        ++mod[{a[i] % x, a[i] % y}];
    }
    cout << cnt / 2 << '\n';
}

E. Anna and the Valentine's Day Gift

给出一个长度为 $n$ 的数组 $a$ ，Anna 先手

Anna 选择一个 $a_{i} \to$ $r e v e r s e (a_{i})$ ,去掉前导 0
Sasha 选择 $a_{i}, a_{j} \to$ $c a t (a_{i}, a_{j})$

当 Anna 下完棋且数组中只剩下一个元素的时候，游戏结束，如果剩下的数字 $\geq 10^{m}$ ,Sasha 获胜，反之，Anna 获胜。

双方都以最佳方式玩游戏，输出获胜方。

Solution

博弈论

容易发现，Anna 每次优先翻转 后导 0 最多的数，Sasha 每次优先以 有最多后导 0 的数 作为 $a_{i}$ 。

以 $a = {10, 10, 10, 10} . m = 5$ 为例执行流程：

Anna： $1, 10, 10, 10 \to$ Sasha： $1, 1010, 10$
Anna： $1, 1010, 1 \to$ Sasha： $1, 10101$
Anna： $1, 10101 \to$ Sasha： $110101$
Anna： $101011 \to$ $Game-Over$ ， $101011 \geq 10^{5} \to$ Sasha WIN

即每次 Anna 删除一个最多的，Sasha 保留一个第二多的，以此类推。

比较简单。

void solve() {
    int n, m;cin >> n >> m;
    vector<pair<int, int>> a(n);for (auto& [i, j] : a)cin >> j;
    int sum = 0;
    for (int i = 0;i < n;i++) {
        string num = to_string(a[i].second);
        sum += num.size();
        int cnt = 0;
        for (int i = num.size() - 1;i >= 0;i--) {
            if (num[i] == '0')cnt++;
            else break;
        }
        a[i].first = cnt;
    }
    sort(a.begin(), a.end());
    for (int i = n - 1;i >= 0;i -= 2) {
        sum -= a[i].first;
    }
    if (sum - 1 >= m)cout << "Sasha\n";
    else cout << "Anna\n";
}

F. Chat Screenshots

编程竞赛聊天室有 $n$ 人。聊天参与者按活动排序，但每个人都把自己排在最前面。

例如，有 $4$ 人参加聊天，他们的顺序是 $[2, 3, 1, 4]$ 。那么

$1$ st 看到的顺序是 $[1, 2, 3, 4]$ 。
$2$ nd 用户看到的订单是 $[2, 3, 1, 4]$ 。
$3$ rd 用户看到的顺序是 $[3, 2, 1, 4]$ 。
$4$ th 用户看到订单 $[4, 2, 3, 1]$ 。

$k$ 人在聊天中发布了截图，显示了该用户看到的参与者顺序。这些截图是在很短的时间内截取的，参与者的顺序并没有改变。

你的任务是确定所有截图是否都有一定的顺序。

Solution

拓扑排序

按照题意：每个人截图后的 $2 - n$ 的相对顺序是一定的。所以只需要将每个人的 $2 - n$ 的相对顺序建图，如果没有出现环则一定存在，有环则出现矛盾，一定不存在。

void solve() {
    int n, k;cin >> n >> k;
    vector<int> g[n + 1], du(n + 1, 0);
    for (int i = 0;i < k;i++) {
        vector<int> a(n);
        for (int j = 0;j < n;j++) {
            cin >> a[j];
        }
        for (int j = 1;j < n - 1;j++) {
            g[a[j]].push_back(a[j + 1]);
            du[a[j + 1]]++;
        }
    }

    queue<int> q;
    for (int i = 1;i <= n;i++) {
        if (!du[i])q.push(i);
    }
    while (q.size()) {
        int t = q.front();q.pop();
        for (auto i : g[t])
            if (!--du[i])q.push(i);
    }
    for (int i = 1;i <= n;i++) {
        if (du[i]) {
            cout << "NO\n";return;
        }
    }
    cout << "YES\n";
}

G. One-Dimensional Puzzle

每种类型包含 $a, b, c, d$ 个元素。如果成功地将所有元素组合成一条长链，就算完成了。求有多少种方法(不能翻转)。

Solution

组合数 (隔板法)

Codeforces Round 925 (Div. 3) A-G 比赛录屏+讲解（60分钟开始）_哔哩哔哩_bilibili

注意：本题写的 $C (x, y)$ 写为了 $C (y, x)$ (写反了 $\dots$ )

前置小练习：

$eg1:$ 将 10 个相同的小球放入 8 个盒子里(每个盒子至少有一个小球)，有多少种放法？

插空法：10 个小球有 9 个空可以插，有 7 个隔板, (即两块板之间不能相邻且第一块板左侧与最后一块板右侧必须有球)。

则答案 $C (7, 9)$

$eg2:$ 将 10 个相同的小球放入 8 个盒子里 (盒子可以为空)，有多少种放法？

隔板法：10 个小球和 7 个隔板，可以组成一个由 17 个物件的排列，从中选择 7 个位置放置隔板，这样就可以把小球分配到 8 个盒子中

答案： $C (7, 17)$

$eg3:$ 求 $x_{1} + x_{2} + x_{3} + x_{4} = 10$ 有多少个正整数解？

即在 $1, 1, 1, \dots, 1 (10 个 1)$ 中选择 3 个空插入，答案： $C (3, 9)$

$eg4:$ 求 $x_{1} + x_{2} + x_{3} + x_{4} = 10$ 有多少个非负整数解？

法一：可以变换一下思路：这时的 $x_{i} \geq 0$ ,将等式两边同时加上 4，则 $x_{i} \geq 1$ 求 $x_{1} + x_{2} + x_{3} + x_{4} = 14$ 的正整数解

法二：将 3 个隔板和 10 组成一个 13 件物品的排列，选择 3 个位置放置隔板

答案： $C (3, 13)$

则可以抽象：

求 $x_{1} + x_{2} + x_{3} + \dots + x_{r} = n$ 的非负整数解个数以及正整数解个数。

$(1) :$ $C (r - 1, r + n - 1)$

$(2) : C (r - 1, n - 1)$

将 $n$ 个相同的小球放入 $r$ 个盒子里, (盒子可以为空和至少一个)各有多少种放法？

$(1) : C (r - 1, n + r - 1)$

$(2) : C (r - 1, n - 1)$

可以在 $1, 2$ 之间插入 $3$ ,在 $2, 1$ 之间插入 $4$

$121212$
$212121$
$333333$ 放在 $1$ 和 $2$ 之间
$444444$ 放在 $2$ 和 $1$ 之间
$1 333 \dots 3 2 444 \dots 4 1 333 \dots 3 2 444 \dots 4 1$

本题目插入的意思 ,设空位个数为 $m$

将 $c | d 个 3 | 4$ 放到 $m$ 个空位空位中 (可以为空)的方法个数
$x_{1} + x_{2} + x_{3} + \dots + x_{m} = c | d$ 非负整数解个数

下面的个数为 $C (m - 1, m + c | d - 1)$ ,由于插入 $3 | 4$ 不冲突，所以直接相乘。

当 $a = b$

$12121212$ 空位： $3 : a, 4 : a + 1$
$21212121$ 空位： $3 : a + 1, 4 : a$

方案数： $C (a - 1, a + c - 1) \times C (a, a + d) + C (a, a + c) \times C (a - 1, a + d - 1)$

当 $a = b - 1$

$2121212$ 空位： $3 : a + 1, 4 : a + 1$

方案数： $C (a, a + c) \times C (a, a + d)$

当 $a = b + 1$

$1212121$ 空位： $3 : a, 4 : a$

方案数： $C (a - 1, a + c - 1) \times C (a - 1, a + d - 1)$

然后就是预处理与逆元(本处为线性递推，快速幂也可)的计算。(待更 $\dots$ )

const int mod = 998244353, N = 2e6 + 10;
ll fac[N], jv[N], inv[N];
void init(int n) {
    jv[0] = fac[0] = 1;
    for (int i = 1;i <= n;i++) {
        inv[i] = i == 1 ? 1 : (mod - mod / i) * inv[mod % i] % mod;
        fac[i] = fac[i - 1] * i % mod;
        jv[i] = jv[i - 1] * inv[i] % mod;
    }
}
ll C(int m, int n) {
    if (n < m || m < 0) return 0;
    return fac[n] * jv[n - m] % mod * jv[m] % mod;
}
void solve() {
    int a, b, c, d;cin >> a >> b >> c >> d;
    if (abs(a - b) >= 2) {
        cout << 0 << '\n';return;
    }
    ll ans = 0;
    if (!a && !b)ans = c == 0 || d == 0;
    else if (a == b) {
        ans = (C(a - 1, a + c - 1) * C(a, a + d) % mod + C(a, a + c) * C(a - 1, a + d - 1) % mod) % mod;
    } else if (a == b - 1) {
        ans = C(a, a + c) * C(a, a + d) % mod;
    } else if (a == b + 1) {
        ans = C(a - 1, a + c - 1) * C(a - 1, a + d - 1) % mod;
    }
    cout << ans << '\n';
}
main::init(2e6);