360-temp

A - A Healthy Breakfast

判断 R 是否在 M 的左边

void solve() {
    string s;cin >> s;
    auto it1 = s.find('R');
    auto it2 = s.find('M');
    if (it1 < it2) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

B - Vertical Reading

给你两个由小写英文字母组成的字符串 $S$ 和 $T$ 。

请判断是否存在一对整数 $c$ 和 $w$ ，使得 $1 \leq c \leq w < | S |$ 和下面的条件得到满足。这里， $| S |$ 表示字符串 $S$ 的长度。请注意， $w$ 必须小于 $| S |$ 。

如果从开头开始每隔 $w$ 个字符拆分 $S$ ，那么长度至少为 $c$ 的子串的 $c$ 个字符依次连接等于 $T$ 。

模拟即可。

void solve() {
    string s, t;cin >> s >> t;
    for (int c = 1;c < s.size();c++) {
        for (int w = c;w < s.size();w++) {
            vector<string> st;
            for (int i = 0;i < s.size();i += w) {
                st.push_back(s.substr(i, w));
            }
            string ss = "";
            for (auto x : st) {
                if (x.size() >= c) {
                    ss += x[c - 1];
                }
            }
            if (ss == t) {
                cout << "Yes\n";return;
            }
        }
    }
    cout << "No\n";
}

C - Move It

有 $N$ 个编号为 $1$ 至 $N$ 的箱子和 $N$ 个编号为 $1$ 至 $N$ 的物品。项目 $i$ 为 $(1 \leq i \leq N)$ 装在 $A_{i}$ 箱中，重量为 $W_{i}$ 。

您可以重复执行选择物品并将其移动到另一个盒子中的操作 0 次或更多次。如果被移动物品的重量为 $w$ ，则操作的成本为 $w$ 。

求使每个箱子正好装一件物品所需的最小总成本。

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), w(n + 1);
    map<int, vector<int>>mp;
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= n;i++) {
        int w;cin >> w;
        mp[a[i]].push_back(w);
    }
    int ans = 0;
    for (auto [x, y] : mp) {
        ans += accumulate(y.begin(), y.end(), 0) - *max_element(y.begin(), y.end());
    }
    cout << ans << '\n';
}

D - Ghost Ants

在标有 $1$ 到 $N$ 的数线上有 $N$ 只蚂蚁。蚂蚁 $i$ $(1 \leq i \leq N)$ 从坐标 $X_{i}$ 开始，朝向正方向或负方向。最初，所有蚂蚁都位于不同的坐标上。每只蚂蚁面对的方向由长度为 $N$ 的二进制字符串 $S$ 表示，如果 $S_{i}$ 为 "0"，则蚂蚁 $i$ 面对的是负方向；如果 $S_{i}$ 为 "1"，则蚂蚁 $i$ 面对的是正方向。

假设当前时间为 $0$ ，在 $(T + 0.1)$ 个单位的时间内，蚂蚁以每单位时间 $1$ 个单位的速度向各自的方向移动，直到时间 $(T + 0.1)$ 。如果有多只蚂蚁到达同一坐标，它们会互相穿过而不会改变方向或速度。经过 $(T + 0.1)$ 个单位的时间后，所有蚂蚁停止。

求 $1 \leq i < j \leq N$ 与蚂蚁 $i$ 和 $j$ 从现在起在时间 $(T + 0.1)$ 之前互相经过的蚂蚁对 $(i, j)$ 的个数。

无想法

Solution

双指针/二分

没有想到，这段时间的状态太差了，加上 zys 根本不训练，真的恶心，一想到之后队友又不训练，我是真 tm 想退役了。加训吧

注意题目中的正方向和负方向

当向右时，比它还左边的肯定要去掉，再加上到右边恰好彼此之差没有超过时间的位置，还是很好判断的

时间复杂度： $O (n)$

#define int long long
void solve() {
    int n, t;cin >> n >> t;
    string s;cin >> s;

    vector<int> x1, x2;
    for (int i = 0;i < n;i++) {
        int a;cin >> a;
        if (s[i] == '1') {
            x1.push_back(a);
        } else {
            x2.push_back(a);
        }
    }
    sort(x1.begin(), x1.end());
    sort(x2.begin(), x2.end());

    int l = 0, r = 0;
    int ans = 0;
    for (int i = 0;i < x1.size();i++) {
        while (l < x2.size() && x2[l] < x1[i])l++;
        while (r < x2.size() && x2[r] <= x1[i] + 2 * t)r++;
        ans += r - l;
    }
    cout << ans << '\n';
}

E - Random Swaps of Balls

有 $N - 1$ 个白球和一个黑球。这些 $N$ 球排列成一排，黑球最初位于最左边的位置。

高桥将执行下面的操作 $K$ 次。

在 $[1, n]$ 之间均匀随机地选择一个整数两次。设 $a$ 和 $b$ 为所选整数。如果是 $a \neq b$ ，把左边的 $a$ 和 $b$ 交换。

经过 $K$ 次操作后，让黑球位于左边第 $x$ 个位置。求 $x$ 的期望值 modulo $998244353$ .

Solution

组合数学/ 概率DP

Question

我的思维过程

设 $P_{i}$ 为最终经过 $K$ 次操作后的位置，容易知道：后面 $N - 1$ 个球都是等价的，概率 $P_{2 \sim N}$ 必然相同，只有 $P_{1}$ 可能不同

$P$ 的分母是 $N^{2 k}$ ，每次选择两次是 $N^{2}$ ，共 $k$ 轮。

若知道了 $P_{1}$ 的分子设为 $X$ ，则可以开始推导：

这时 $P_{1} = \frac{X}{N^{2 k}}, P_{2} = P_{3} = P_{4} = \dots = P_{N} = \frac{1 - P_{1}}{N - 1} = \frac{N^{2 k} - X}{N^{2 k} (N - 1)}$

$E = \sum_{i = 1}^{N} i \times P_{i} = P_{1} + P_{2} \times (2 + 3 + \dots + N) = P_{1} + \frac{(N - 1) (N + 2)}{2} \times P_{2}$

$⟹ E = \frac{(X + \frac{(N + 2) (N^{2 k} - X)}{2})}{N^{2 k}} = 1 + \frac{N}{2} - \frac{X}{2 N^{2 k - 1}}$

E = 1 + \frac{N^{2 k} - X}{2 N^{2 k - 1}} = 1 + (\frac{N}{2}) (1 - P_{1})

只需求出 $P_{1}$ 即可求出答案。然后卡住了... 组合数学得泰拉了

每次操作都有： $p = \frac{N^{2} - 2 (n - 1)}{N^{2}}$ 的概率位置不变 $(i)$ ， $q = \frac{2}{N^{2}}$ 会变为位置 $j (j \neq i)$

即在第 $k$ 次操作之前，要计算在第 $1$ 个位置的概率，要么是不动的，要么是不在位置 1 而移动到位置 1. 只有两种选择，

状态转移方程： $f_{k} = f_{k - 1} \times p + (1 - f_{k - 1}) \times q$

计算出的 $f_{k}$ 即代表进行了 $k$ 轮后仍然在位置 1 的概率，即计算出了 $P_{1}$ ，带入公式：

E = \frac{2 + N (1 - P_{1})}{2}

千万要注意 mod 的各种情况，防止犯低级错误！

void solve() {
    int n, k;cin >> n >> k;
    int p = (n * n - 2 * (n - 1)) % mod * inv(n * n % mod) % mod;
    int q = 2 * inv(n * n % mod) % mod;
    vector<int> f(k + 1);
    f[0] = 1;
    for (int i = 1;i <= k;i++) {
        f[i] = (f[i - 1] * p % mod + (1 - f[i - 1] + mod) * q % mod) % mod;
    }
    cout << (2 + n * (1 - f[k] + mod) % mod) % mod * inv(2) % mod << '\n';
}

更加容易理解的方式：
与上面的思想相同都是想办法计算出 $P_{1}$ 。

$f_{i, 0 / 1}$ 代表经过 $i$ 次操作在/不在位置 1 的概率

易得：在没有进行操作的时候 $f_{0, 0} = 1$

若经过操作在位置 1，则有两种可能：

本来就在位置 1，位置没有变化
本来不在位置 1，位置交换到了位置 1

$f_{i, 0} = f_{i - 1, 0} \times p + f_{i - 1, 1} \times q$

若经过操作不在位置 1，则有两种可能：

本来在位置 1，位置发生了改变
本来不在位置 1，位置随意，只要不交换到位置 1 即可

$f_{i, 1} = f_{i - 1, 0} \times (1 - p) + f_{i - 1, 1} \times (1 - q)$

void solve() {
    int n, k;cin >> n >> k;
    int p = (n * n - 2 * (n - 1)) % mod * inv(n * n % mod) % mod;
    int q = 2 * inv(n * n % mod) % mod;
    vector<array<int, 2>> f(k + 1);//f[i][0/1]代表经过i次操作后在/不在位置1
    f[0][0] = 1;
    for (int i = 1;i <= k;i++) {
        f[i][0] = f[i - 1][0] * p % mod + f[i - 1][1] * q % mod;
        f[i][0] %= mod;
        f[i][1] = f[i - 1][0] * (1 - p + mod) % mod + f[i - 1][1] * (1 - q + mod) % mod;
        f[i][1] %= mod;
    }
    cout << (2 + n * (1 - f[k][0] + mod) % mod) % mod * inv(2) % mod << '\n';
}

G - Suitable Edit for LIS

给你一个长度为 $N$ 的整数序列 $A$ 。高桥将执行下面的操作一次：

选定一个 $i$ ，给 $A_{i}$ 赋任意值。

求操作后 $A$ 的最长递增子序列 (LIS) 的最大可能长度。

Solution

做这个题目的前提条件： ABC354F - Useless for LIS

比较麻烦，先放着，挖坑...