A 小红的类型转换

知识点：类型转换、浮点数

输入的小数部分全部为 $0$，直接读入后转换为整数即可。由于 $x\le 10^9<2^{53}$，整数部分可被浮点数类型精确表示。

时间复杂度 $\mathcal{O}(1)$。

void solve() {
    double x;
    cin >> x;
    cout << (int)x << endl;
}

B 小红的矩阵构造

知识点：构造、绝对值和、最值证明

每一对相同数字的纵坐标差至多为 $1$，因此纵向贡献总和至多为 $n$。把所有 $2n$ 个列坐标排序为 $z_1\le z_2\le\dots\le z_{2n}$，任意配对的横向距离和满足：

$$\sum |\Delta c|\le\sum_{i=n+1}^{2n}z_i-\sum_{i=1}^{n}z_i.$$

也就是说，横向距离和在“最小的 $n$ 个坐标”和“最大的 $n$ 个坐标”配对时取得最大值。第一行递增、第二行递减恰好实现该配对，同时每个数字都跨越两行，纵向贡献也达到上界。

时间复杂度 $\mathcal{O}(n)$。

void solve() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i) {
        cout << i << " \n"[i == n];
    }
    for (int i = n; i >= 1; --i) {
        cout << i << " \n"[i == 1];
    }
}

C 小红的序列删除

知识点：贪心、曼哈顿距离、子序列

令保留长度为 $m=n-k$。终点曼哈顿距离可以视为：分别为横轴、纵轴选定正方向后，保留一个顺方向字符记为 $+1$，反方向字符记为 $-1$。

横轴应选出现次数更多的 $\texttt{L}$ 或 $\texttt{R}$，纵轴同理选出现次数更多的 $\texttt{U}$ 或 $\texttt{D}$。设这两个有利方向字符总数为 $F$，则最多保留 $\min(m,F)$ 个有利字符，最优值为：

$$2\min(m,F)-m.$$

若 $F\ge m$，只保留任意 $m$ 个有利字符；否则保留全部有利字符，再补足任意无利字符。从左到右扫描原串即可保证结果仍为原串的子序列。

时间复杂度 $\mathcal{O}(n)$。

void solve() {
    int n, k;
    string s;
    cin >> n >> k >> s;

    array<int, 256> cnt{};
    for (char c : s) ++cnt[c];

    char a = cnt['R'] >= cnt['L'] ? 'R' : 'L';
    char b = cnt['U'] >= cnt['D'] ? 'U' : 'D';

    int m = n - k;
    int x = min(m, cnt[a] + cnt[b]);
    int y = m - x;

    for (char c : s) {
        if ((c == a || c == b) && x) {
            cout << c;
            --x;
        } else if (c != a && c != b && y) {
            cout << c;
            --y;
        }
    }
    cout << endl;
}

D 小红的01串

知识点：环、边界贡献、模拟

令：

$$e_i=[s_i\ne s_{(i+1)\bmod n}].$$

反置一段连续环形区间后，区间内部的边两端同时反置，区间外部的边两端都不变，因此它们是否不同不会改变。只有两条边界 $e_{l-1}$ 与 $e_r$ 恰有一个端点被反置，状态会取反。

维护所有 $e_i$ 的和。每次操作只需翻转这两个边界，并同步更新答案；若两条边重合，连续处理两次会自然抵消。

时间复杂度 $\mathcal{O}(n+q)$。

void solve() {
    int n, q;
    string s;
    cin >> n >> q >> s;

    vector<int> a(n);
    for (int i = 0; i < n - 1; ++i) {
        a[i] = s[i] != s[i + 1];
    }
    a[n - 1] = s[n - 1] != s[0];

    int ans = accumulate(a.begin(), a.end(), 0LL);
    auto idx = [&](int x) {
        return (x + n) % n;
    };

    while (q--) {
        int l, r;
        cin >> l >> r;

        ans += a[idx(l - 1)] ? -1 : 1;
        a[idx(l - 1)] ^= 1;

        ans += a[idx(r)] ? -1 : 1;
        a[idx(r)] ^= 1;

        cout << ans << endl;
    }
}

E 小红的子数组删除

知识点：滑动窗口、对顶多重集合、中位数

删除长度为 $k$ 的子数组后，剩余元素数量为 $m=n-k$。维护剩余元素中的两个有序多重集合：$L$ 存较小的 $\lceil m/2\rceil$ 个元素，$R$ 存其余元素。

当 $m$ 为奇数时，中位数为 $\max L$；当 $m$ 为偶数时，中位数为：

$$\frac{\max L+\min R}{2}.$$

初始删除区间为 $[0,k-1]$。窗口右移时，原本删除的 $a_l$ 回到集合，同时新进入删除区间的 $a_{l+k}$ 从集合移除。每次平衡两个集合后即可判断当前删除方案是否合法。若 $m=0$，只有删除整个数组这一种方案，中位数为 $0$。

时间复杂度 $\mathcal{O}(n\log n)$。

void solve() {
    int n, k, x;
    cin >> n >> k >> x;

    vector<int> a(n);
    for (auto &v : a) cin >> v;

    int m = n - k;
    if (m == 0) {
        return cout << (x == 0) << endl, void();
    }

    multiset<int> L, R;
    int needL = (m + 1) / 2;

    auto balance = [&]() {
        while (L.size() > needL) {
            auto it = prev(L.end());
            R.insert(*it);
            L.erase(it);
        }
        while (L.size() < needL && !R.empty()) {
            auto it = R.begin();
            L.insert(*it);
            R.erase(it);
        }
    };

    auto add = [&](int v) {
        if (L.empty() || v <= *L.rbegin()) L.insert(v);
        else R.insert(v);
        balance();
    };

    auto erase = [&](int v) {
        auto it = L.find(v);
        if (it != L.end()) {
            L.erase(it);
        } else {
            R.erase(R.find(v));
        }
        balance();
    };

    for (int i = k; i < n; ++i) add(a[i]);

    int ans = 0;
    for (int l = 0; l + k <= n; ++l) {
        if (m & 1) {
            ans += *L.rbegin() == x;
        } else {
            ans += *L.rbegin() + *R.begin() == 2 * x;
        }

        if (l + k < n) {
            erase(a[l + k]);
            add(a[l]);
        }
    }

    cout << ans << endl;
}

F 艾雅法拉的点燃

知识点：线性动态规划、局部影响、滚动数组

令 $b_i$ 表示对第 $i$ 名敌人使用“点燃”的次数，并补上边界 $b_0=b_{n+1}=0$。第 $i$ 名敌人受到的点燃伤害为：

$$b_{i-1}+2b_i+b_{i+1}.$$

固定所有点燃次数后，普通攻击只需补足未覆盖的生命值。因此当已知 $b_{i-2}=p$、$b_{i-1}=q$、$b_i=r$ 时，第 $i-1$ 名敌人需要的普通攻击次数为：

$$\max(0,a_{i-1}-p-2q-r).$$

设 $dp[p][q]$ 表示处理到当前位置前，最近两名敌人的点燃次数分别为 $p,q$ 时的最小法力。枚举当前 $r$ 后，第 $i-1$ 名敌人的总伤害已经确定，可以立刻结算其普通攻击费用，并转移至 $dp[q][r]$。最后额外处理一个生命值为 $0$ 的哨兵位置，保证第 $n$ 名敌人也被结算。

时间复杂度 $\mathcal{O}(nA^3)$，其中 $A=\max a_i\le50$；空间复杂度 $\mathcal{O}(A^2)$。

constexpr int inf = 2e18 + 9;

void solve() {
    int n, x, y;
    cin >> n >> x >> y;

    vector<int> a(n + 2);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    array<array<int, 51>, 51> dp, ndp;
    for (int i = 0; i <= 50; ++i) dp[i].fill(inf);
    dp[0][0] = 0;

    for (int i = 1; i <= n + 1; ++i) {
        for (auto &v : ndp) fill(v.begin(), v.end(), inf);

        for (int p = 0; p <= 50; ++p) {
            for (int q = 0; q <= 50; ++q) {
                if (dp[p][q] == inf) continue;

                for (int r = 0; r <= a[i]; ++r) {
                    int need = max(0LL, a[i - 1] - p - 2 * q - r);
                    ndp[q][r] = min(ndp[q][r], dp[p][q] + need * x + r * y);
                }
            }
        }

        dp.swap(ndp);
    }

    int ans = inf;
    for (int i = 0; i <= 50; ++i) {
        ans = min(ans, dp[i][0]);
    }
    cout << ans << endl;
}

约定

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii array<int, 2>
#define endl "\n"

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed << setprecision(20);

    int t = 1;
    // cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
    return 0;
}