T1

模拟

• 按题意模拟

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

int main() {
    int n;
    scanf("%d", &n);
    string s(n, 0), t(n, 0);
    scanf("%s%s", s.data(), t.data());
    for (int i = 0; i < n; ++i)
        if (s[i] == t[i]) s[i] = toupper(s[i]);
        else s[i] = max(s[i], t[i]);
    printf("%s\n", s.data());
    return 0;
}

T2

给定 ，还原排列 。

• 贪心：如果 ，则 为当前的最大值，否则为当前的最小值。记录两个值模拟即可。

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

int main() {
    cin.sync_with_stdio(0), cin.tie(0);
    string s;
    cin >> s;
    int n = s.size() + 1, mn = 1, mx = n;
    vector<int> a(n);
    for (int i = 0; i < n - 1; ++i) {
        if (s[i] == '0') a[i] = mx--;
        else a[i] = mn++;
    }
    a.back() = mx;
    for (auto x : a) printf("%d ", x);
    puts("");
    return 0;
}

T3

求 且 的 数对数量。

• ；
• 即统计 和 的 数对数量；
• 非正数统计顺序对，非负数统计逆序对，然后减去重复计算的 的数对数量。

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

int main() {
    int n, m;
    scanf("%d", &n);
    vector<int> a(n), c;
    auto add = [&](int i, int w = 1) {
        for (; i <= m; i += i & -i) c[i] += w;
    };
    auto qry = [&] (int i, int w = 0) {
        for (; i; i -= i & -i) w += c[i];
        return w;
    };
    for (auto &x : a) scanf("%d", &x);
    auto b = a;
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    m = b.size();
    c.assign(m + 1, 0);
    long long ans = 0, c0 = 0;
    for (auto x : a) {
        c0 += x == 0;
        if (x < 0) continue;
        int y = lower_bound(b.begin(), b.end(), x) - b.begin() + 1;
        ans += qry(m - y + 1);
        add(m - y + 1);
    }
    c.assign(m + 1, 0);
    for (auto x : a) {
        if (x > 0) continue;
        int y = lower_bound(b.begin(), b.end(), x) - b.begin() + 1;
        ans += qry(y);
        add(y);
    }
    ans -= c0 * (c0 - 1) / 2;
    printf("%lld\n", ans);
    return 0;
}