C - Move It

题目链接：C - Move It

题目大意：有 \(N\) 个盒子和 \(N\) 个物品编号为 \(1-N\)，物品 \(i\) 在盒子 \(A_i\) 中，重量为 \(W_i\)，你可以进行一种操作将盒子中的一件物品移动到其他任意盒子中，代价为 \(W_i\)，求使得所有盒子中只存在一件物品的最小操作代价。

题解：贪心，可以发现如果盒子中的物品数量大于1件，只需要保留该盒子中物品重量最大的物品（将物品质量更小的物品优先移走更优），因此只需要维护每个盒子中物品，求出除最大重量以外的其他物品的重量和即为该盒子需要的最小代价，对所有盒子遍历一遍进行操作即可得到答案。维护盒子中的物品可以采用小根堆，也可以用其他方法来维护。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], w[N];
map<int, priority_queue<int, vector<int>, greater<int>>> m;
int n;

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
    }
    
    for (int i = 1; i <= n; i ++) {
        cin >> w[i];
        m[a[i]].push(w[i]);
    }
    
    int res = 0;
    for (auto heap : m) {
        while(heap.second.size() > 1) {
            res += heap.second.top();
            heap.second.pop();
        }
    }
    
    cout << res << endl;
}

int main() {
    ios::sync_with_stdio();
    cin.tie(0);
    cout.tie(0);
    solve();
}

D - Ghost Ants

题目链接：D - Ghost Ants

题目大意：在数轴上有 \(N\) 只蚂蚁，蚂蚁 \(i\) 从坐标 \(X_i\) 开始，面向正方向或负方向，起初所有蚂蚁都在不同的坐标上，每只蚂蚁面向的方向由一个长度为 \(N\) 的二进制字符串 \(S\) 表示，如果 \(S_i\) 为0则面向负方向，为1则面向正方向。设当前时间为0，所有蚂蚁以每单位时间1单位的速度沿着各自面向的方向移动 \(T+0.1\) 单位时间，如果多只蚂蚁到达同一坐标，它们会互相穿过而不会改变方向或速度，在 \(T+0.1\) 单位时间后，所有蚂蚁都会停止移动，求出在这之前相互穿过的蚂蚁对 \((i,j)\) 的数量，满足 \(1 \leq i < j \leq N\)

题解：双指针，将所有蚂蚁按照正负方向分为两部分，设正方向蚂蚁为 \(x_1\)，负方向蚂蚁为 \(x_2\)，将 \(x_1\) 与 \(x_2\) 进行升序排序，之后判断两个方向的蚂蚁在何种情况会相互穿过，需要同时满足以下两个条件：

• \(x_1\) 的起点小于等于 \(x_2\) 的起点
• \(x_1\) 的起点与 \(x_2\) 的起点的距离小于等于 \(2*T\)
  满足上述条件后，定义左右指针l，r，由于前面已经将数组 \(x_1\)， \(x_2\) 进行升序排序，因此只需遍历 \(x_1\)，将 \(r - l\) 的值累加即为答案。

AC代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
int x1[N], x2[N];

void solve() {
    int n, t;
    string s;
    cin >> n >> t >> s;
    s = "_" + s;
    int idx1 = 0, idx2 = 0;
    for (int i = 1; i <= n; i ++) {
        int t;
        cin >> t;
        if(s[i] == '1') x1[++ idx1] = t;
        else x2[++ idx2] = t;
    }
    
    sort(x1 + 1, x1 + idx1 + 1);
    sort(x2 + 1, x2 + idx2 + 1);
    int l = 1, r = 1;
    ll res = 0;
    for (int i = 1; i <= idx1; i ++) {
        while(l <= idx2 && x2[l] < x1[i])   l ++;
        while(r <= idx2 && x2[r] <= x1[i] + t * 2)   r ++;
        
        res += r - l;
    }
    
    cout << res << endl;
    
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

E - Random Swaps of Balls

题目链接：E - Random Swaps of Balls

题目大意：有 \(N - 1\) 个白球和一个黑球在一条线上排列，初始黑球在最左侧，现在可以进行 \(K\) 次操作，每次操作会随机选择两个球 \(a,b\)，若 \(a \neq b\)，则交换两个球的位置，求 \(K\) 次操作后，黑球距离最左侧的位置的期望值，对 \(998244353\) 取模

题解：概率dp，设 \(dp[i]\) 为进行 \(i\) 次操作后黑球在最左侧的概率，显然初始状态时球在最左侧，有 \(dp[0] = 1\) ，向下一个状态转移时，则需要考虑两种情况：

• 黑球在最左侧，经过一次操作后黑球不在最左侧的概率
• 黑球不在最左侧，经过一次操作后黑球回到最左侧的概率

由此得到递推公式：

其中 \(p = \frac{2(n+1)}{n^2}\) ，\(q = \frac{2}{n^2}\)

AC代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const long long N = 1e5 + 10, mod = 998244353;
ll dp[N];

ll qmi(ll a, ll k, ll p) {
    ll res = 1;
    while(k)
    {
        if(k & 1)   res = res * a % p;
        k >>= 1;
        a = a * a % p;
    }
    return res;
}

void solve() {
    dp[0] = 1;
    ll n, k;
    cin >> n >> k;
    ll p = 2 * (n - 1) % mod * qmi(n * n % mod, mod - 2, mod) % mod; 
    p = (p + mod) % mod;
    ll q = 2 * qmi(n * n % mod, mod - 2, mod) % mod;
    q = (q + mod) % mod;
    for (int i = 1; i <= k; i ++) {
        dp[i] = (((1 - p + mod) % mod * dp[i - 1] % mod) + q * (1 - dp[i - 1] + mod) % mod) % mod;
    }
    
    ll ans = ((((n + 2) * (mod + 1) / 2) % mod) * (1 + mod - dp[k]) + dp[k]) % mod;
    
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}