A – The Fair Nut and the Best Path

sb 树形 DP。

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

using namespace std;

const int MAX_N = 3e5 + 200;

typedef long long ll;

const ll INF = 0x3f3f3f3f3f3f3f3f;

int n, current, head[MAX_N], wi[MAX_N];
ll dp[MAX_N], gans;

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

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

void dfs(int u, int fa)
{
    ll biggest = -1, sbiggest = -1;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
        {
            dfs(edges[i].to, u);
            ll tmp = dp[edges[i].to] - edges[i].weight;
            if (tmp > biggest)
                swap(biggest, sbiggest), biggest = tmp;
            else if (tmp > sbiggest)
                sbiggest = tmp;
        }
    dp[u] = wi[u];
    if (biggest != -1 && sbiggest != -1)
        gans = max(gans, wi[u] + biggest + sbiggest);
    if (biggest != -1)
        dp[u] += biggest;
    gans = max(gans, dp[u]);
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &wi[i]), gans = max(gans, 1LL * wi[i]);
    for (int i = 1, u, v, w; i <= n - 1; i++)
        scanf("%d%d%d", &u, &v, &w), addpath(u, v, w), addpath(v, u, w);
    dfs(1, 0), printf("%lld\n", gans);
    return 0;
}

B – The Fair Nut and Strings

可以很容易发现这东西最后等于 Trie 树的节点个数，然后我们就可以利用 01 Trie 的性质，不停地扩充节点个数即可。

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

using namespace std;

const int MAX_N = 5e5 + 200;

typedef long long ll;

int n, k;
char S[MAX_N], T[MAX_N];

int main()
{
    scanf("%d%d%s%s", &n, &k, S + 1, T + 1);
    ll gans = 0, pans = 1;
    for (int i = 1; i <= n; i++)
    {
        pans <<= 1;
        if (S[i] == 'b')
            pans--;
        if (T[i] == 'a')
            pans--;
        if (pans >= k)
        {
            gans += 1LL * k * (n - i + 1);
            break;
        }
        gans += pans;
    }
    printf("%lld\n", gans);
    return 0;
}

C – Max Mex

我们可以搞一颗线段树，关键字为 mex 值。这颗线段树需要维护每一个 mex 区间所能代表的路径。这个东西可以通过 LCA + 深度判断进行操作。询问和修改直接在线段树上做正常操作即可。

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

using namespace std;

const int MAX_N = 4e5 + 200;

int n, q, head[MAX_N], current, dep[MAX_N], st[20][MAX_N], wi[MAX_N], ptot, up[MAX_N], pos[MAX_N], log2_[MAX_N], bucket[MAX_N];

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

struct node
{
    int u, v;
} nodes[MAX_N << 2];

char nc()
{
    static char buffer[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buffer) + fread(buffer, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}

int read()
{
    int x = 0, f = 1;
    char c = nc();
    while (!isdigit(c))
        f = (c == '-' ? -1 : f), c = nc();
    while (isdigit(c))
        x = (x << 3) + (x << 1) + c - '0', c = nc();
    return x * f;
}

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

void dfs(int u)
{
    dep[u] = dep[up[u]] + 1, st[0][++ptot] = u, pos[u] = ptot;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        dfs(edges[i].to), st[0][++ptot] = u;
}

int getLCA(int x, int y)
{
    if (pos[x] > pos[y])
        swap(x, y);
    int len = pos[y] - pos[x] + 1, d = log2_[len];
    int lft = st[d][pos[x]], rig = st[d][pos[y] - (1 << d) + 1];
    return dep[lft] < dep[rig] ? lft : rig;
}

int getDist(int x, int y) { return dep[x] + dep[y] - (dep[getLCA(x, y)] << 1); }

node mergeNode(node u, int w)
{
    if (u.u == -1 || w == -1)
        return node{-1, -1};
    int d1 = getDist(u.u, u.v), d2 = getDist(u.u, w), d3 = getDist(u.v, w);
    return d1 == d2 + d3 ? u : ((d1 + d3 == d2) ? node{u.u, w} : (d1 + d2 == d3 ? node{u.v, w} : node{-1, -1}));
}

node pushup(node lson, node rson) { return mergeNode(mergeNode(lson, rson.u), rson.v); }

#define lson (p << 1)
#define rson ((p << 1) | 1)
#define mid ((l + r) >> 1)

void build(int l, int r, int p)
{
    if (l == r)
        return (void)(nodes[p] = node{bucket[l], bucket[l]});
    build(l, mid, lson), build(mid + 1, r, rson);
    nodes[p] = pushup(nodes[lson], nodes[rson]);
}

void update(int qx, int l, int r, int p)
{
    if (l == r)
        return (void)(nodes[p] = node{bucket[l], bucket[l]});
    if (qx <= mid)
        update(qx, l, mid, lson);
    else
        update(qx, mid + 1, r, rson);
    nodes[p] = pushup(nodes[lson], nodes[rson]);
}

int query(node &tmp, int l, int r, int p)
{
    if (nodes[p].u != -1)
    {
        if (tmp.u == -1)
            return tmp = nodes[p], r + 1;
        node curt = pushup(tmp, nodes[p]);
        if (curt.u != -1)
            return tmp = curt, r + 1;
    }
    if (l == r)
        return l;
    int ls = query(tmp, l, mid, lson);
    if (ls <= mid)
        return ls;
    else
        return query(tmp, mid + 1, r, rson);
}

#undef mid
#undef rson
#undef lson

int main()
{
    memset(head, -1, sizeof(head)), n = read();
    for (int i = 1; i <= n; i++)
        wi[i] = read(), bucket[wi[i]] = i;
    for (int i = 2; i <= n; i++)
        up[i] = read(), addpath(up[i], i);
    dfs(1);
    for (int i = 1; i < 20; i++)
        for (int j = 1; j + (1 << i) - 1 <= ptot; j++)
            st[i][j] = (dep[st[i - 1][j]] < dep[st[i - 1][j + (1 << (i - 1))]]) ? st[i - 1][j] : st[i - 1][j + (1 << (i - 1))];
    for (int i = 2; i <= ptot; i++)
        log2_[i] = (log2_[i >> 1] + 1);
    build(0, n - 1, 1), q = read();
    while (q--)
    {
        int opt = read(), u, v;
        if (opt == 1)
        {
            u = read(), v = read(), swap(bucket[wi[u]], bucket[wi[v]]), swap(wi[u], wi[v]);
            update(wi[u], 0, n - 1, 1), update(wi[v], 0, n - 1, 1);
        }
        else
        {
            node tmp = node{-1, -1};
            printf("%d\n", query(tmp, 0, n - 1, 1));
        }
    }
    return 0;
}

E – The Fair Nut and Rectangles

首先有性质：矩形不会互相包含。也就是意味着随着 \(x\) 增大，\(y\)是单调递减的。我们可以设计出一个很 SB 的方程：

\[ dp[i] = \max_{j \in [1, i)} \{ dp[j] + S_i – S_i \cap S_j – a_i \} \]

设计出来之后，发现 \(S_i \cap S_j\) 随着 \(j\) 的递增而增大，所以上斜率优化即可。

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

using namespace std;

const int MAX_N = 1e6 + 200;
const double eps = 1e-10;

typedef pair<int, int> pii;
typedef long long ll;

int n, q[MAX_N];
ll gans, f[MAX_N];

struct node
{
    ll x, y, cost;
    bool operator<(const node &rhs) const { return y > rhs.y; }
} nodes[MAX_N];

double X(int i) { return nodes[i].x; }

double Y(int i) { return f[i]; }

double slope(int i, int j) { return fabs(X(j) - X(i)) < eps ? 1e10 : double(Y(j) - Y(i)) / double(X(j) - X(i)); }

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld%lld", &nodes[i].x, &nodes[i].y, &nodes[i].cost);
    sort(nodes + 1, nodes + 1 + n);
    int head = 0, tail = 0;
    for (int i = 1; i <= n; i++)
    {
        while (head < tail && slope(q[head], q[head + 1]) >= nodes[i].y)
            head++;
        f[i] = 1LL * nodes[i].x * nodes[i].y - nodes[i].cost;
        if (head <= tail)
            f[i] = max(f[i], f[q[head]] + 1LL * (nodes[i].x - nodes[q[head]].x) * nodes[i].y - nodes[i].cost);
        gans = max(gans, f[i]);
        while (head < tail && slope(q[tail - 1], q[tail]) <= slope(q[tail], i))
            tail--;
        q[++tail] = i;
    }
    printf("%lld\n", gans);
    return 0;
}