A - Robot Balance #

签到。

1
void solve(int cs){
2
    int a, b;
3
    cin >> a >> b;
4
    cout << max(a - b, 0ll) << endl;
5
}

B - Robot Weight #

用 map 记一下零件状态，在x上加加减减即可。

1
void solve(int cs){
2
    int x, n;
3
    cin >> x >> n;
4
    vector<int> w(n + 5);
5
    for (int i = 1; i <= n; i++) {
6
        cin >> w[i];
7
    }
8
    map<int, int> ok;
9
    int q;
10
    cin >> q;
11
    while (q--) {
12
        int id;
13
        cin >> id;
14
        if (ok[id] == 1) {
15
            ok[id] = 0;
16
            x -= w[id];
17
            cout << x << endl;
18
        }
19
        else {
20
            ok[id] = 1;
21
            x += w[id];
22
            cout << x << endl;
23
        }
24
    }
25
}

C - Robot Factory #

每个身子分配一个他能安装的最大的头，把头和身子从大到小排序后双指针扫一下计数即可。

1
void solve(int cs){
2
    int n, m, k;
3
    cin >> n >> m >> k;
4
    vector<int> h(n);
5
    vector<int> b(m);
6
    int ph = 0, pb = 0;
7
    for (int i = 0; i < n; i++) {
8
        cin >> h[i];
9
    }
10
    for (int i = 0; i < m; i++) {
11
        cin >> b[i];
12
    }
13
    sort(h.begin(), h.end(), cmp);
14
    sort(b.begin(), b.end(), cmp);
15
    int cnt = 0;
16
    while (ph < n && pb < m) {
17
        if (h[ph] <= b[pb]) {
18
            cnt++;
19
            pb++;
20
        }
21
        ph++;
22
    }
23
    cout << (cnt >= k ? "Yes" : "No") << endl;
24
}

D - Robot Customize #

假定一开始所有的零件都装在身体上，得到一个基础快乐值 $sb=\sum b_i$ ，把第 $i$ 个零件转移到头上相当于我们的基础快乐值加上 $del=h_i-b_i$ ，同时头部重量加 $w_i$ 。考虑总重量为 $sw = \sum w_i$ ，那头部的重量不能超过 $\lfloor\frac{sw}{2}\rfloor$ 。

于是我们可以把这道题转换成物品重量为 $w_i$ ，价值为 $del_i$ ，在容量 $\lfloor\frac{sw}{2}\rfloor$ 下求最大价值和的01背包问题，若最后答案为负数说明把零件放在头上没有快乐值贡献，所以需要将答案与 $0$ 取 $max$ 后和基础快乐值 $sb$ 相加。

1
void solve(int cs){
2
    int n;
3
    cin >> n;
4
    vector<int> w(n), h(n), b(n);
5
    int sw = 0, sb = 0;
6
    for (int i = 0; i < n; i++) {
7
        cin >> w[i] >> h[i] >> b[i];
8
        sw += w[i];
9
        sb += b[i];
10
    }
11
    int m = sw / 2;
12
    vector<int> dp(m + 1, -inf);
13
    dp[0] = 0;
14
    for (int i = 0; i < n; i++) {
15
        int del = h[i] - b[i];
16
        if (del <= 0) continue;
17
        int wt = w[i];
18
        for (int j = m; j >= wt; j--) {
19
            dp[j] = max(dp[j], dp[j - wt] + del);
20
        }
21
    }
22
    int ans = 0;
23
    for (int i = 0; i <= m; i++) {
24
        if (dp[i] > 0) ans = max(ans, dp[i]);
25
    }
26
    cout << ans + sb << endl;
27
}

E - Reflection on Grid #

抽象成一个 01BFS 问题，一个状态由 $x,\ y,\ f$ 三部分组成， $x,\ y$ 为当前格子， $f$ 为光的入射方向，对于到达的每一个位置，我们枚举是否需要修改，以及修改成那种类型的镜子，如果无需修改，则将光线到达的下一个格子的状态放到队头；如果需要修改，则将光线到达下一个格子的状态放到队尾，跑 BFS 即可。

1
struct Node {
2
    int x, y, f;
3
};
4

5
string dir = "ABC";
6
string s[N];
7
vector<int> d[4][N];
8

9
int dx[] = {0, 1, 0, -1};
10
int dy[] = {1, 0, -1, 0};
11

12
void nxt(int x, int y, int f, char c, int &nx, int &ny, int &nf) {
13
    if (c == 'A') nf = f;
14
    else if (c == 'B') nf = (5 - f) % 4;
15
    else nf = 3 - f;
16
    nx = x + dx[nf];
17
    ny = y + dy[nf];
18
}
19

20
void solve(int cs) {
21
    int n, m;
22
    cin >> n >> m;
23
    for (int i = 1; i <= n; i++) {
24
        cin >> s[i];
25
        s[i] = ' ' + s[i];
26
    }
27
    for (int i = 0; i <= n + 1; i++) {
28
        for (int k = 0; k <= 3; k++) {
29
            d[k][i].assign(m + 2, inf);
30
        }
31
    }
32
    d[0][1][1] = 0;
33
    deque<Node> q;
34
    q.clear();
35
    q.push_back({1, 1, 0});
36
    int ans = inf;
37
    while (q.size()) {
38
        auto [x, y, f] = q.front();
39
        q.pop_front();
40
        int nx, ny, nf, dis;
41
        for (auto c : dir) {
42
            nxt(x, y, f, c, nx, ny, nf);
43
            if (s[x][y] == c) dis = d[f][x][y];
44
            else dis = d[f][x][y] + 1;
45
            if (nx == n && ny == m + 1 && nf == 0) ans = min(ans, dis);
46
            if (nx == 0 || ny == 0 || nx > n || ny > m) continue;
47
            if (dis < d[nf][nx][ny]) {
48
                d[nf][nx][ny] = dis;
49
                if (s[x][y] == c) q.push_front({nx, ny, nf});
50
                else q.push_back({nx, ny, nf});
51
            }
52
        }
53
    }
54
    cout << ans << endl;
55
}

F - Almost Sorted 2 #

先将数组从小到大排序，我们发现任意一个小于 $a_i-d$ 的值不可能出现在 $a_i$ 之后，否则从 $a_i$ 向下到该值至少会出现一次相邻下降大于 $d$ ，因此令 $pos_i$ 为使 $a_{pos_i} \geq a_i-d$ 的最小索引，在 $1\sim i$ 的所有值中索引 $1\sim pos_i-1$ 的元素必须出现在 $a_i$ 以前。因此，当我们按升序把这 $i$ 个元素放到最终序列时， $a_i$ 在这 $i$ 个元素中的合法插入位置数为 $i-(pos_i-1)=i-pos_i+1$ 。将对所有 $i$ 的选择数相乘，就得到把排序后元素视为可区分物件的排列数。

因为原题中相同元素不可区分，所以要进行去重，如果某个值 $v$ 在原数组中出现了 $cnt_v$ 次，上面的计数把这 $cnt_v$ 个相同值当作 $cnt_v$ 个不同对象来计数（即标号化），导致重复计数 $cnt_v!$ 倍。

故最终答案为：

\left(\prod_{i=1}^N (i - l_i + 1)\right) \times \prod_{v} (cnt_v!)^{-1} \pmod{998244353}.

1
int qpow(int a, int x, int mod) {
2
    int res = 1LL;
3
    while (x) {
4
        if (x % 2)
5
            res = res * a % mod;
6
        a = a * a % mod;
7
        x /= 2;
8
    }
9
    return res;
10
}
11

12
int fac[N], invFac[N];
13
void init() {
14
    fac[0] = 1;
15
    for (int i = 1; i < N; ++i) {
16
        fac[i] = (fac[i - 1] * i) % MOD;
17
    }
18
    invFac[N - 1] = qpow(fac[N - 1], MOD - 2, MOD);
19
    for (int i = N - 2; i >= 0; --i) {
20
        invFac[i] = (invFac[i + 1] * (i + 1)) % MOD;
21
    }
22
}
23

24
void solve(int cs){
25
    init();
26
    int n, d;
27
    cin >> n >> d;
28
    vector<int> a(n);
29
    for (int i = 0; i < n; i++) {
30
        cin >> a[i];
31
    }
32
    sort(a.begin(), a.end());
33
    int ans = 1;
34
    for (int i = 0; i < n; i++) {
35
        int nd = a[i] - d;
36
        int pos = lower_bound(a.begin(), a.end(), nd) - a.begin();
37
        int pk = i - pos + 1;
38
        if (pk <= 0) {
39
            ans = 0;
40
            break;
41
        }
42
        ans = (ans * (pk % MOD)) % MOD;
43
    }
44
    int id = 0;
45
    while (id < n) {
46
        int j = id + 1;
47
        while (j < n && a[j] == a[id]) {
48
            j++;
49
        }
50
        int cnt = j - id;
51
        ans = (ans * invFac[cnt]) % MOD;
52
        id = j;
53
    }
54
    cout << ans % MOD << endl;
55
}