1931(925div3)

A. Recovering a Small String

\(a-z\to1-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\) \(reverse(a_{i})\),去掉前导 0
Sasha 选择 \(a_{i},a_{j}\to\) \(cat(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\) \(\text{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

组合数 (隔板法)

前置小练习：

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

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

则答案 \(C(7,9)\)

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

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

答案：\(C(7,17)\)

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

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

\(\text{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\) 之间
\(\textcolor{red}{1}\textcolor{green}{333\dots3}\textcolor{red}{2}\textcolor{gray}{444\dots4}\textcolor{red}{1}\textcolor{green}{333\dots3}\textcolor{red}{2}\textcolor{gray}{444\dots4}\textcolor{red}{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);