A – 照片

这道题是一道很考察思维的题目，我在这里介绍 DP 的做法。

我们考虑 DP。大概的方程可以写成：

\[ dp[i] = max\{ dp[j], j \in S_i \} + 1 \]

其中，\(dp[i]\)代表\([1, i]\)之间最多的斑点奶牛数量，然后\(S_i\)就是我们可以转移来的区间。我们可以提前处理好每一个点对应的\(lft_{S_i}, rig_{S_i}\)，也就是每一个点集合的左右端点。这个区间满足一个根本的条件：这个区间是点\(i\)左边最近的、不包含\(i\)的集合。我们肯定可以从这一段区间搞出最大的答案。预处理的时候先默认\(rgt[i] = i – 1\)，最后做个小 DP 更新数据即可。

现在考虑优化这个 DP，毕竟求出了 \(S_i\) 的范围也只是常数上的优化，我们现在来卡指数。发现连续的\(\dots, S_{i-1}, S_i, S_{i+1}, \dots\)之间一般（存在无解的情况）也是连续的，所以我们在用单调队列的时候也可以连续的来维护，注意队头的下标距离和队尾的斜率处理。

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

using namespace std;

const int MAX_N = 201000;

int dp[MAX_N], lft[MAX_N], rig[MAX_N], n, m, q[MAX_N << 1];

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n + 1; i++)
        rig[i] = i - 1;

    for (int i = 1, l, r; i <= m; i++)
        scanf("%d%d", &l, &r), rig[r] = min(rig[r], l - 1), lft[r + 1] = max(lft[r + 1], l);
    for (int i = n; i >= 1; i--)
        rig[i] = min(rig[i], rig[i + 1]);
    for (int i = 2; i <= n + 1; i++)
        lft[i] = max(lft[i], lft[i - 1]);
    int l = 1, r = 1, j = 1;
    q[1] = 0;
    for (int i = 1; i <= n + 1; i++)
    {
        while (j <= min(rig[i], n))
        {
            if (dp[j] == -1)
            {
                j++;
                continue;
            }
            while (l <= r && dp[j] > dp[q[r]])
                r--;
            q[++r] = j, j++;
        }
        while (l <= r && q[l] < lft[i])
            l++;
        if (l <= r)
            dp[i] = dp[q[l]] + ((i != n + 1) ? 1 : 0);
        else
            dp[i] = -1;
    }
    printf("%d", dp[n + 1]);
    return 0;
}

B – 阴阳

这道题我在考场上看出来了是 sb 点分治模版题，但是打挂了，说明还是不够熟练，需要多加练习。

考虑点分治的时候，从根出发的链会提供两种信息：链权和与有无零点。题目要求我们记录路径的时候判断是否有零点。所以，记录答案的时候一个是要特判链权和为零的情况，且要记录链权的同时要记录有无原点。搞清楚了这两件事情，点分治即可。

// B.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 101000;

int head[MAX_N], current, siz[MAX_N], n, dep[MAX_N], dist[MAX_N], mxdep;
int root_val, root, current_stat[MAX_N];
ll f[MAX_N << 1][2], g[MAX_N << 1][2], answer;
bool tag[MAX_N];

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

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

void __find_root(int u, int fa, int capacity)
{
    int mx_val = 0;
    siz[u] = 1;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa && !tag[edges[i].to])
            __find_root(edges[i].to, u, capacity), siz[u] += siz[edges[i].to], mx_val = max(mx_val, siz[edges[i].to]);
    mx_val = max(mx_val, capacity - siz[u]);
    if (mx_val < root_val)
        root_val = mx_val, root = u;
}

int find_root(int u, int capacity)
{
    root_val = capacity, root = 0;
    __find_root(u, 0, capacity);
    return root;
}

void dfs1(int u, int fa, int dep, int way)
{
    mxdep = max(mxdep, dep);
    if (current_stat[way] > 0)
        f[way][1]++;
    else
        f[way][0]++;
    current_stat[way]++;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa && !tag[edges[i].to])
            dfs1(edges[i].to, u, dep + 1, way + edges[i].weight);
    current_stat[way]--;
}

void dq(int u, int capacity)
{
    int mx = 0;
    tag[u] = true, g[MAX_N][0] = 1;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (!tag[edges[i].to])
        {
            mxdep = 1;
            dfs1(edges[i].to, u, 1, MAX_N + edges[i].weight);
            mx = max(mx, mxdep);
            answer += (g[MAX_N][0] - 1) * f[MAX_N][0];
            for (int d = -mxdep; d <= mxdep; d++)
                answer += (g[MAX_N - d][1] * f[MAX_N + d][1]) + (g[MAX_N - d][0] * f[MAX_N + d][1]) + (g[MAX_N - d][1] * f[MAX_N + d][0]);
            for (int d = MAX_N - mxdep; d <= MAX_N + mxdep; d++)
            {
                g[d][0] += f[d][0];
                g[d][1] += f[d][1];
                f[d][0] = f[d][1] = 0;
            }
        }
    for (int d = MAX_N - mx; d <= MAX_N + mx; d++)
        g[d][0] = g[d][1] = 0;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (!tag[edges[i].to])
        {
            int capacity_ = siz[edges[i].to];
            dq(find_root(edges[i].to, capacity_), capacity_);
        }
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 1, u, v, len; i <= n - 1; i++)
        scanf("%d%d%d", &u, &v, &len), addpath(u, v, len == 0 ? -1 : 1), addpath(v, u, len == 0 ? -1 : 1);
    dq(find_root(1, n), n);
    printf("%lld", answer);
    return 0;
}

C – 数字八

这道题就是一道 DP 题。懒得讲了，