前言：这套题的 B,D 来自 zhyh 学长此前的模拟赛。A,C 来自牛客多校的第一场（其实是感觉水了，所以想加这两道来平衡一下）结果发现 AB 和 CD 之间 gap 还是太大了（，所以抱歉捏

但是感觉大家都不太想写暴力？OI 赛制下暴力还是很重要的。特别是如果水平没有碾压性的高的时候，这个时候就是比谁在场上打得稳，打的高分暴力。所以大家平时还是要多进行训练，以免场上打不出来。

另外关于对拍，个人建议是永远要对拍。本次特意塞了两道多测题（才不是我懒得改数据呢哼）就是为了再看一下大家的记性。考场上例如 C 题这种题很容易给你一个全是坑的大样例，因此如果写出来了自己多构造下特殊情况，极限情况，再看看能不能跑过去。

在这里补题喵：作业详情 - HydroOJ

A

定位为阅读理解题。题目名 neta 了 chatGPT.

由于建筑和建筑之间、建筑和电站之间的连接方式是一样的，可以把电站也当作建筑处理。

显然，当若干个建筑有重叠覆盖区域，那么在这个重叠区上的电塔(可以不止一个）已经和它们每一个相连，即连接他们不需要消耗电线。

反之，如果建筑之间的覆盖区间有间隔，必须在两者之间建立至少两个电塔，并用电线连接电塔。

显然，既然电塔的位置是任意的，那么把电塔布局在区间边界，可以使得连接它们的电线最短。 以样例为例：

也就是电线的总长是各个覆盖区间所不能覆盖的地方。 那么，到这步这题就变成了区间合并问题！

如果你记得区间合并求并集长度的模板之类的，稍微改写一下这题就结束啦！

不太了解那么继续↓

我们观察一个合并了的独立区间例如样例中的后三个区间：

为了方便，用括号代表区间左右端点。

(())()

既然这段区间是若干个区间合并在一起的，那么它的左右端点数量一定一致。知道最左的左端点和最右的右端点坐标，也就知道了这段区间的长度。

反过来看，从头开始读取区间节点，当读到相等数量的左右节点，由于区间的左右端点一定是成对出现的，那么这一定是一段连续区间。

（在例子中直接这样截取会把这段区间认为是两个区间，但它们的总长度和整个区间的长度一致，故而在长度处理中不用特殊考虑）

那么把每个节点按坐标排列好，就可以按顺序读取它们，并得到合并后的区间的长度了。用左右两个极端得到的距离减去总长，就能得到空缺的长度，这就是我们要的答案。

当然，在处理的时候也可以直接把空缺的区间加和：读取到完整的独立区间（左右节点个数相同）后，把答案加上下一个节点到这个节点的距离即可。

时间复杂度 $\mathcal{O}(n\log n)$

std:

#include <cstdio>
#include <algorithm>
 
using namespace std;
 
const int N = 2e5 + 5;
 
int n;
long long x[N], r[N];
long long ans, pr;
int p[N];
 
bool cmp(int a, int b)
{
	return x[a] - r[a] < x[b] - r[b];
}
 
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld%lld", &x[i], &r[i]);
		p[i] = i;
	}
	sort(p + 1, p + n + 1, cmp);
	pr = x[p[1]] - r[p[1]];
	for (int i = 1; i <= n; i++)
	{
		if (pr < x[p[i]] - r[p[i]])
			ans += x[p[i]] - r[p[i]] - pr;
		pr = max(pr, x[p[i]] + r[p[i]]);
	}
	printf("%lld\n", ans);
	return 0;
}

B

定位为签到题。

我们直接考虑 DP。发现这个东西很好划分成一段段的形式，我们定义 $f_{l,r}$ 表示 $[l,r]$ 这段变为相对应的 $a_{l,r}$ 的次数。

那么实际上我们讨论一下端点的情况：

• 若 $a_l = a_r$，这俩如果要一起染色，那么我们可以先推平一次，然后转而考虑 $[l + 1,r - 1]$ 的情况，或者我们可以分开来考虑 $[l,r-1]$ 以及 $[l + 1,r]$ 的情况
• 若 $a_l \not = a_r$，那么就枚举一个中间点 $k$，相当于分别考虑 $[i,k],[k + 1,j]$ 的区间。

综上写出转移方程：

$$f_{l,r} = \min(f_{l + 1,r - 1} + 1,f_{l,r - 1},f_{l + 1,r}) a_l = a_r \\ f_{l,r} = \min\limits_{l \leq k < r}(f_{l,k} + f_{k + 1,r}) a_l \not = a_r \\ $$

直接转移，时间复杂度 $\mathcal{O}(n^3)$

std:

/*
Are we falling like snow at the beach
Weird but fucking beautiful
Flying in a dream, stars by the pocketful
You wanting me, tonight feels impossible
But it's coming down no sound it's all round
*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define mp make_pair

char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
	int v = getchar();T f = 1;t = 0;
	while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
	while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
	t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
	read(t);read(args...);
}

const ll mod = 998244353;
const double eps = 1e-10;
const int N = 510;

ll f[N][N],n,a[N];

signed main() {
	read(n);
    for (int i = 1;i <= n;++i) read(a[i]);
    memset(f,0x3f,sizeof f);
    for (int i = 1;i <= n;++i) f[i][i] = 1;
    for (int len = 2;len <= n;++len) {
        for (int l = 1;l + len - 1 <= n;++l) {
            int r = l + len - 1;
            if (a[l] == a[r]) {
                f[l][r] = min(f[l+1][r-1] + 1,min(f[l][r-1],f[l+1][r]));
            } else {
                for (int k = l;k < r;++k) {
                    f[l][r] = min(f[l][r],f[l][k] + f[k + 1][r]);
                }
            }
        }
    }
    printf("%lld\n",f[1][n]);
	return 0;
}

C

定位为好玩的题。

简化题意：

有一张 $n$ 个点 $m$ 条边的无重边无自环的有向图，初始时可以选择一个点染黑，其余点均为白点

若某个点所有入边的起点均为黑点，则该点可以被染黑。最大化图中黑点数量。

$1 ≤ ∑n ≤ 2 × 10^5 , 1 ≤ ∑m ≤ 5 × 10^5$

首先可以观察出，若两个点的答案集合有交集，则这两个集合一定是包含关系，因此我们可以尝试将每个点的后继合并到这个点，最后输出最大的集合大小。

包含关系的证明：

暴力合并的复杂度显然是无法接受的，因此考虑如下技巧：

若该后继的某个前驱已经在当前点的答案集合，则将该前驱直接从后继的前驱集合中删去。否则说明当前点无法被合并，直接退出循环。最后将当前点插入后继的前驱集合。这样可以避免无意义查询，使得点 $i$ 的遍历次数是 $O(k_i)$ 的。

但是合并后继时貌似有点问题：我们会将后继的后继当成新的后继，若我们构造一个链套菊花图，使得菊花图部分的点都无法被合并但链部分的点都能被合并，则菊花图部分的点会被加入链长次，这样时间复杂度就被卡到了 $O(n^2)$。

解决方案当然是有的，若我们从链顶开始做，就能避免这一情况，因此我们判断若当前点有唯一前驱且前驱编号比自己大（避免在出现环时出错），则不处理当前点，等到处理前驱时再考虑。就可以把复杂度变为 $\mathcal{O}((n+\sum k) \log n)$ 的了。

还有一个随机化做法，我当时不是很懂，现在也没理解，附在下方有需要的同学可以自己理解下。

启发式合并std:

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
struct dsu {
    int fa[N], siz[N];
    inline void init(int k) {
        for (int i = 1; i <= k; ++i) fa[i] = i, siz[i] = 1;
    }
    int find(int k) { return k == fa[k] ? k : fa[k] = find(fa[k]); }
    inline bool merge(int x, int y) {
        x = find(x), y = find(y);
        if (x != y) {
            fa[x] = y, siz[y] += siz[x];
            return true;
        }
        return false;
    }
} d;
int deg[N], n, num, t_case;
set<int> fa[N], to[N];
bool vis[N];
int main() {
    scanf("%d", &t_case);
    while (t_case--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) fa[i].clear(), to[i].clear();
        for (int i = 1; i <= n; ++i) {
            scanf("%d", deg + i);
            for (int j = 1, x; j <= deg[i]; ++j) {
                scanf("%d", &x);
                fa[i].insert(x);
                to[x].insert(i);
            }
        }
        int ans = 0;
        d.init(n);
        for (int i = 1; i <= n; ++i)
            if (d.find(i) == i) {
                if (fa[i].size() == 1 && *fa[i].begin() > i)
                    continue;
                auto update = [&](int k) {
                    for (auto it = to[k].begin(); it != to[k].end(); ++it)
                        if (d.find(*it) != *it)
                            it = to[k].erase(it);
                };
                update(i);
                queue<int> q;
                for (int j : to[i]) q.push(j);
                while (q.size()) {
                    int p = q.front();
                    q.pop();
                    if (!to[i].count(p))
                        continue;
                    for (auto it = fa[p].begin(); it != fa[p].end();) {
                        if (d.find(*it) == i)
                            it = fa[p].erase(it);
                        else {
                            to[i].insert(p);
                            goto skip;
                        }
                    }
                    d.merge(p, i);
                    to[i].erase(p);
                    update(p);
                    for (int j : to[p])
                        if (i != j)
                            q.push(j), to[i].insert(j);
                skip:;
                    fa[p].insert(i);
                }
                ans = max(ans, d.siz[i]);
            }
        printf("Case #%d: %d\n", ++num, ans);
    }
    return 0;
}

//Every night that summer just to seal my fate
//And I scream, "For whatever it's worth
//I love you, ain't that the worst thing you ever heard?"
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define mp make_pair

char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
	int v = getchar();T f = 1;t = 0;
	while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
	while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
	t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
	read(t);read(args...);
}

const int N = 2e5 + 10;

int n,f[N],siz[N],cas;
set <int> G1[N],G2[N];
int find(int x) {
    return f[x] == x ? x : f[x] = find(f[x]);
}

void dfs(int u,int v) {
    int fx = find(u),fy = find(v);
    if (fx == fy) return ;
    if (G2[fx].size() > G2[fy].size()) swap(fx,fy);
    vector <pii> edg;
    for (auto y : G2[fx]) {
        G2[fy].insert(y);
        G1[y].erase(fx);
        G1[y].insert(fy);
        if (G1[y].size() == 1) edg.push_back(mp(fy,y));
    }
    f[fx] = fy;
    siz[fy] += siz[fx];
    for (auto p : edg){
        dfs(p.first,p.second);
    }
}

void solve() {
    read(n);++cas;
    for (int i = 1;i <= n;++i) G1[i].clear(),G2[i].clear(),f[i] = i,siz[i] = 1;
    for (int i = 1;i <= n;++i) {
        int k;read(k);
        for (int j = 1;j <= k;++j) {
            int y;read(y);
            G1[i].insert(y);G2[y].insert(i);
        }
    }
    for (int i = 1;i <= n;++i) {
        if (G1[i].size() == 1) {
            dfs(i,*G1[i].begin());
        }
    }
    int ans = 0;
    for (int i = 1;i <= n;++i) ans = max(ans,siz[i]);
    printf("Case #%d: %d\n",cas,ans);
}

signed main() {
    int T;read(T);
    while (T--) solve();
	return 0;
}

D

出题学长的祖传好题。

学长的做法是：考虑 BFS 序，先预处理出每个点 $x$ 到其第 $2^k$ 级祖先路上的最大值。然后考虑处理每个询问，我们先找出对应的子树，然后在这个 BFS 序列上进行二分，找到对应点（感觉说的很抽象，大家结合代码理解）复杂度大概是 $\mathcal{O}(n\log^2 n)$ 的

我的做法是：考虑每个点维护一颗以深度为下标的线段树，然后实际上这个过程就是把每个点上的线段树合并，所以总时间复杂度实际上是可以做到 $\mathcal{O}(n\log n)$。当然你也可以用 DSU on tree 来实现，反正就是多一个 log 的事。

学长的 std:

#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 500005;

struct edge {
	int v, pre;
} e[MAXN<<1];
int N, T, C[MAXN], fst[MAXN];
// C: the maximum in the node's tree
int qwq[MAXN], pq[MAXN], pd[MAXN], pl[MAXN], pr[MAXN];
// qwq: bfs
// pq: nodes' poi in qwq
// pd: nodes' deep in qwq
// pl: the left poi of the same deep in qwq
int maxn[MAXN][25];
int vis[MAXN], dep[MAXN], depp[MAXN];
int fth[MAXN][25], son[MAXN][25], lg[MAXN];

inline int max(int x, int y) { return x > y ? x : y; }
inline int min(int x, int y) { return x < y ? x : y; }
inline int read()
{
	register int o = 0;
	register char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	while (c >='0' && c <='9') o = (o<<3)+(o<<1)+(c&15), c = getchar();
	return o;
}
inline void adde(int a, int b, int k)
{
	e[k] = (edge){b, fst[a]}, fst[a] = k;
}
void bfs()
{
	register int h = 0, t = 1, uu, vv;
	qwq[1] = 1, vis[1] = 1, pd[1] = 0;
	do {
		uu = qwq[++h], pq[uu] = h;
		for (register int o=fst[uu]; o; o=e[o].pre) if (!vis[e[o].v]) {
			vv = e[o].v, qwq[++t] = vv, vis[vv] = 1, pd[t] = pd[h] + 1;
		}
	} while (h < t);
	for (register int i=1; i<=N; i++) pr[pd[i]] = i;
	for (register int i=N; i>=1; i--) pl[pd[i]] = i;
}
void dfs(int k, int d)
{
	vis[k] = 0, dep[k] = d;
	for (register int i=1; i<=lg[d]; i++)
		fth[k][i] = fth[fth[k][i-1]][i-1];
	for (register int o=fst[k]; o; o=e[o].pre) if (vis[e[o].v]) {
		fth[e[o].v][0] = k, dfs(e[o].v, d+1);
		C[k] = max(C[k], C[e[o].v]);
		if (depp[k] < depp[e[o].v] + 1) {
			depp[k] = depp[e[o].v] + 1;
			son[k][0] = e[o].v;
		}
	}
	for (register int i=1; i<=lg[depp[k]]; i++)
		son[k][i] = son[son[k][i-1]][i-1];
}
void init()
{
	N = read();
	for (int i=1; i<=N; i++) C[i] = read();
	for (int i=1; i< N; i++) {
		int a = read(), b = read();
		adde(a, b, i), adde(b, a, i+N);
	}
	for (int i=1; i<=N; i++)
		lg[i] = lg[i-1] + ((1<<(lg[i-1]+1)) == i);
	bfs(), dfs(1, 0);
	for (register int i=1; i<=N; i++) maxn[i][0] = C[qwq[i]];
	for (register int k=1; k<=lg[N]; k++)
		for (register int i=1; i+(1<<k)-1<=N; i++)
			maxn[i][k] = max(maxn[i][k-1], maxn[i+(1<<(k-1))][k-1]);
}
int lca(int a, int b)
{
    if (dep[a] < dep[b]) a ^= b ^= a ^= b;
    while (dep[a] > dep[b]) a = fth[a][lg[dep[a]-dep[b]]];
    if (a == b) return a;
    for (register int i=lg[dep[a]]; i>=0; i--)
        if (fth[a][i] != fth[b][i]) a = fth[a][i], b = fth[b][i];
    return fth[a][0];
}
void work()
{
	T = read();
	for (; T; T--) {
		register int uu = read(), vv = uu, dd = read(), pv;
		while (dep[vv] < dep[uu] + dd) vv = son[vv][lg[dep[uu]-dep[vv]+dd]];
		pv = pq[vv];
		register int l = pl[pd[pv]] - 1, r = pr[pd[pv]] + 1, tmp, mid;
		tmp = pv; //(l, tmp]
		while (l + 1 < tmp) {
			mid = (l + tmp) >> 1;
			if (dep[lca(vv, qwq[mid])] < dep[uu]) l = mid; else tmp = mid;
		}
		tmp = pv; //[tmp, r)
		while (tmp + 1 < r) {
			mid = (tmp + r) >> 1;
			if (dep[lca(vv, qwq[mid])] < dep[uu]) r = mid; else tmp = mid;
		}
		l++, r--;
		int ans = max(maxn[l][lg[r-l+1]], maxn[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);
		printf("%d\n", ans);
	}
}
int main()
{
	init();
	work();
}