C – Attention

前缀和后缀搞一搞即可。

// ARC098A.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3e5 + 200;

int pre[2][MAX_N], n;
char str[MAX_N];

int main()
{
    scanf("%d%s", &n, str + 1);
    for (int i = 1; i <= n; i++)
        pre[str[i] == 'E'][i]++, pre[0][i] += pre[0][i - 1], pre[1][i] += pre[1][i - 1];
    int ans = 1e9;
    for (int i = 1; i <= n; i++)
        ans = min(pre[0][i - 1] + pre[1][n] - pre[1][i], ans);
    printf("%d\n", ans);
    return 0;
}

D – Xor Sum 2

考虑一个性质，只有在 \(a \& b=0\) 时，才能满足 \(a \oplus b = a + b\)。二分或者是 two-pointers 即可。

// ARC098B.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5 + 200;

int n, ai[MAX_N], bits[20][MAX_N];
long long ans;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]);
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 20; j++)
            bits[j][i] = bits[j][i - 1] + ((ai[i] >> j) & 1);
    for (int i = 1; i <= n; i++)
    {
        int l = 1, r = i, res;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            bool flag = true;
            for (int j = 0; j < 20; j++)
                flag &= bits[j][i] - bits[j][mid - 1] <= 1;
            if (flag)
                r = mid - 1, res = mid;
            else
                l = mid + 1;
        }
        ans += i - res + 1;
    }
    printf("%lld\n", ans);
    return 0;
}

E – Range Minimum Queries

枚举最小值 \(x\)，然后把整个线段分割成多个最小值大于等于 \(x\) 的段。把每个段里面前 \(len – k + 1\) 大的数拿出来，再进行排序，取 \(Q\) 大的数即可验证。

// ARC098C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2020;

typedef pair<int, int> pii;

int n, k, q, ai[MAX_N], ans = 1e9;

int check(int minimum_val)
{
    vector<int> block, pool;
    for (int i = 1; i <= n + 1; i++)
        if (ai[i] >= minimum_val)
            block.push_back(ai[i]);
        else
        {
            if (block.size() >= k)
            {
                sort(block.begin(), block.end());
                int len = block.size();
                for (int i = 0; i <= len - k; i++)
                    pool.push_back(block[i]);
            }
            block.clear();
        }
    sort(pool.begin(), pool.end());
    if (pool.size() < q)
        return 1e9;
    return pool[q - 1] - minimum_val;
}

int main()
{
    scanf("%d%d%d", &n, &k, &q);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]);
    for (int i = 1; i <= n; i++)
        ans = min(ans, check(ai[i]));
    printf("%d\n", ans);
    return 0;
}

F – Donation

刚开始思考的时候，大概能了解到这个东西最后会转换为树上问题。考虑每一次金额的变动，都会导致一些点的消失，那么就会产生割点，同时最后的形状也一定是树。加上一个性质：捐款只会发生在最后一次经过，我们可以确定最后的形状一定是树。

考虑定义 \(\max(a_i – b_i, 0)\) 作为每个点所需的额外金额，最后树的形状一定是随着深度的增加、\(c_i\) 变大。我们可以用并查集来建出这棵树，然后用 DP 来算最大的准备金。

// ARC098F.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200;

typedef long long ll;

int n, m, head[MAX_N], current, ai[MAX_N], bi[MAX_N], ci[MAX_N], id[MAX_N], rk[MAX_N], mem[MAX_N];
ll dp[MAX_N], tot[MAX_N];
vector<int> G[MAX_N];

struct edge
{
    int to, nxt;
} edges[MAX_N << 1];

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

int find(int x) { return mem[x] == x ? x : mem[x] = find(mem[x]); }

void dfs(int u, int fa)
{
    tot[u] = bi[u];
    for (auto son : G[u])
        dfs(son, u), tot[u] += tot[son];
}

void calc(int u, int fa)
{
    if (G[u].empty())
        return (void)(dp[u] = bi[u] + ci[u]);
    dp[u] = 1e18;
    for (auto v : G[u])
        calc(v, u), dp[u] = min(dp[u], tot[u] - tot[v] + max(1LL * ci[u], dp[v]));
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &ai[i], &bi[i]), ci[i] = max(ai[i] - bi[i], 0), id[i] = i, mem[i] = i;
    sort(id + 1, id + 1 + n, [](const int &rhs1, const int &rhs2) { return ci[rhs1] < ci[rhs2]; });
    for (int i = 1; i <= n; i++)
        rk[id[i]] = i;
    for (int i = 1, u, v; i <= m; i++)
        scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
    for (int idx = 1; idx <= n; idx++)
    {
        int u = id[idx];
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (u != find(edges[i].to) && rk[u] > rk[find(edges[i].to)])
                G[u].push_back(find(edges[i].to)), mem[find(edges[i].to)] = u;
    }
    dfs(id[n], 0), calc(id[n], 0), printf("%lld\n", dp[id[n]]);
    return 0;
}