C

一定需要 $n$ 次1操作来将 $t$ 变为 $n$ 长度
$t$ 的下标小的位置得到的 2操作一定比下标大的位置更多

把一轮称为某位置执行10次1操作后重新从0开始累加。因此，如果有 $s[i]<s[i+1]$，则必然是 $s[i]$ 增加10之后的新一轮

统计最少需要经过多少轮即可

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    string s;
    cin >> s;
    int n = s.size();
    i64 ans = 0;
    for (int i = n - 2; i >= 0; i--) {
        if (s[i] < s[i + 1]) {
            ans += 10;
        }
    }
    cout << ans + n + s[0] - '0' << "\n";
    return 0;
}

D

搜索题

对于每个位置 $pos$，如果已经被占用，则移动到下一个位置，否则查看能否在当前位置横放或者竖放，使用一个 $st$ 进行状态压缩，遍历所有位置即可

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    std::vector<std::vector<i64>> g(n, std::vector<i64>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> g[i][j];
        }
    }
    i64 ans = 0;
    auto dfs = [&](auto && dfs, int pos, int st, i64 xorsum = 0) {
        if (pos == n * m) {
            ans = std::max(ans, xorsum);
            return;
        }
        int row = pos / m, col = pos % m;
        if (st >> pos & 1) {
            dfs(dfs, pos + 1, st, xorsum);
        } else {
            dfs(dfs, pos + 1, st, xorsum ^ g[row][col]);
            if (row + 1 < n && !(st >> (pos + m) & 1)) {
                dfs(dfs, pos + 1, st | (1 << pos) | (1 << (pos + m)), xorsum);
            }
            if (col + 1 < m && !(st >> (pos + 1) & 1)) {
                dfs(dfs, pos + 1, st | (1 << pos) | (1 << (pos + 1)), xorsum);
            }
        }
        
    };
    dfs(dfs, 0, 0);
    cout << ans << "\n";
    return 0;
}

E

反悔贪心

什么是合法的括号序列？对于任意位置 $i$，对于它的前缀，)的数量 $\le$ (的数量，那么它就是一个合法的括号序列

将问题转化一下，也就是求位置)之和 $sum$ 的最小值，再用总和减去这个最小值

我们枚举位置 $i$，并假设将它加入)之中，$sum$ 加上当前位置的值，如果)计数大于 $\lfloor\frac{i}{2}\rfloor$，则表明当前括号序列不合法，从 $i$ 之前位置弹出一个最大数，用 $sum$ 减去这个最大数，表示将这个最大数位置变为(，这样一直枚举到位置 $n$，则可得到最小的)位置数字之和并且保证之前所有位置的括号序列均合法。

使用优先队列寻找最大值

void solve() {
    int n;
    cin >> n;
    std::vector<i64> a(n * 2);
    for (auto &x : a) {
        cin >> x;
    }
    std::priority_queue<i64> pq;
    i64 sum = 0;
    int siz = 0;
    for (int i = 0; i < n * 2; i++) {
        pq.push(a[i]);
        sum += a[i];
        siz++;
        if (siz > (i + 1) / 2) {
            sum -= pq.top();
            pq.pop();
            siz--;
        }
    }
    cout << std::accumulate(a.begin(), a.end(), 0ll) - sum << "\n";
}

F

使用单调栈计算 $a[i]$ 能成为长度为 $len$ 的序列的最大值的次数，累加其贡献，主要分为以下三种情况：

假设 $i$ 位置左侧第一个比 $a[i]$ 大的位置为 $l[i]$，同理 $r[i]$，$mx$ 为 $max(l[i],r[i])$，同理 $mn$：

对于 $len=1,2,…,mn-1$，$a[i]$ 对 $len$ 的贡献次数$=len$
对于 $len=mn,mn+1,…,mx-1$，$a[i]$ 对 $len$ 的贡献次数为 $mn\cdot len$
对于 $len=mx,mx+1,…,r[i]+l[i]-1$，$a[i]$ 对 $len$ 的贡献次数为 $mn\cdot a[i],(mn-1)\cdot a[i],(mn-2)\cdot a[i]…$

使用二阶差分即可

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    cin >> n;
    std::vector<int> a(n);
    for (int &x : a) {
        cin >> x;
    }
    std::stack<int> stk;
    std::vector<int> l(n), r(n);
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && a[stk.top()] < a[i]) {
            stk.pop();
        }
        l[i] = stk.empty() ? -1 : stk.top();
        stk.push(i);
    }
    while (!stk.empty()) {
        stk.pop();
    }
    for (int i = n - 1; i >= 0; i--) {
        while (!stk.empty() && a[stk.top()] <= a[i]) {
            stk.pop();
        }
        r[i] = stk.empty() ? n : stk.top();
        stk.push(i);
    }
    std::vector<i64> b(n + 3);
    auto add = [&](int h, int t, i64 k, i64 d) -> void {
        if (t < h) return;
        b[h] += k;
        b[h + 1] += d - k;
        b[t + 1] -= k + (t - h + 1) * d;
        b[t + 2] += k + (t - h) * d;
    };
    for (int i = 0; i < n; i++) {
        int le = i - l[i], ri = r[i] - i;
        int mn = std::min(le, ri), mx = std::max(le, ri), len = ri + le - 1;
        add(1, mn - 1, a[i], a[i]);
        add(mn, mx - 1, 1ll * mn * a[i], 0);
        add(mx, len, 1ll * mn * a[i], -a[i]);
    }
    for (int i = 1; i <= n; i++) {
        b[i] += b[i - 1];
    }
    for (int i = 1; i <= n; i++) {
        b[i] += b[i - 1];
        cout << b[i] << "\n";
    }
    return 0;
}