信競轉生~到了文化課就拿出真本事~

TrenchGenius · 2026-11-01 09:33:55 · 生活·游记

赛前一天连封两号无敌了。

我是你🐖哥哥，T4 直接赌徒心理学，没写笨儿暴力，去冲 n\log^2 惨遭 0pts。

紧张哭了。

T1

你将数组排序后，一段区间的花销为 \sum a_x-a_i，收获是 len。

那么移动右端点，左端点不停向有移动，直接做就可以了。

T2

考虑到每条路线内部不会花费任何代价，那么你可以对于每个站，得出从一条经过路线到另一条线路之间交换的最小代价。

那么这个可以直接 md^2 得出，然后你再计算一下任意一条线路到另一条线路的花费，这个 n^3\log 用 dij 求。

然后询问枚举从哪一条线路出发和结束。

T3

在此之前我们用双指针计算一个点能直接到的最右边的点 r_x。

考虑 dp，f(x,0/1/2) 表示某一个 i 以最优线路到了 x，同时我们钦定的分别是：

0. 我们认为我们不能通过任何一条非最优线路到达当前点。
1. 我们要求至今为止我们可以以两条路径即 l_{l_{\cdots _x-1}},\cdots,l_{x-1},x-1，和 l_{l_{\cdots _x}},\cdots,l_{x},x。
2. 我们已经经过了 1 的部分，同时约束变为和 0 相同。

我们发现路线一定是 0,1,2 拼起来。

那么转移有以下，边界情况自视：

4. f(r_x,2)\leftarrow f(x,2)$ 当且仅当 $r_{x-1}\neq r_x

这是显然的，求答案部分则仅允许 f(x,1/2)：

花了大概 2.25\ h。

中途花时间在 T4 写了个无职转生。

T4

发现我们难以考虑两连通块存在祖先关系的情况。

想了很久的暴力，但是始终没有 n^3 的做法，所以哭了，但是想到了一个优良性质。

我们考虑将根换为直径中心，那么存在一个性质“两个连通块的根要么是这个根，要么在不同的两个子树中”，这是显然的。

尝试二分答案，使得一个距离合法的条件是：假设一个在 x，一个在 y，那么我们的 f(x)+f(y)\le k 而且对于任意 z 有 \min(dis(x,z),dis(y,z))\le Mid。

考虑对于每一个子树得到其中每一个节点的 x,len,val,g，分别表示这个节点，在这个子树中 mid\lt dis(x,z) 的最深的 z 与根的距离，val 如果这个连通块以 x 为根需要花费多少使得子树内部是合法的，还有一个是这个到根节点的距离。

val

好求，考虑 dp，f(x) 表示 x 的子树，那么 f(x)=\sum _{son} f(son)+[mid \lt MxDp(x)]。

len

这个看起来难求，试图遍历一棵树，我们不妨拆开看 dis(x,z)=dp(z)+dp(x)-2 dp(lca)，所以当我们从 fa 进到某个子树时，我们维护一个线段树，在 OtherSonMxDp-2dp(fa) 处，取 max=OtherSonMxDp，那么我们只需要使得满足条件的一段区间的最大值就是 len。

我们已经对于一个子树求出了这些信息。

考虑后面一个式子，当我们选取 x,y 时分别钦定其来自深度最深的子树和次深的子树，次深的子树和最深的子树，最深的子树和非次深的子树，和两个非最深的子树，我们建立三个线段树分别表示另一个应该是哪一种。

具体而言，我们加入一个节点时，（mx,demx,trimx 分别表示最深子树的最深度，次深子树的最深度，再次深子树的最深度），处理一下另一个子树需要有多浅才行，当然我们会发现不可能存在一种情况使得一者需要另一个处理子树内的某点，而另一者需要该者处理另一子树内的某点：

for([x,len,val,g]) {
    if(x==mx)
        Tdemx.modify(trimx+g<=mid?len:max(trimx,len),val);
        Tnone.modify(demx+g<=mid?len:max(demx,len),val);
    if(x==demx) {
        Tmx.modify(trimx+g<=mid?len:max(trimx,len),val);
        Tnone.modify(mx+g<=mid?len:max(mx,len),val);
    }
    if(x!=mx&&x!=demx) {
        Tmx.modify(demx+g<=mid?len:max(demx,len),val);
        Tnone.modify(mx+g<=mid?len:max(mx,len),val);
        Tdemx.modify(mx+g<=mid?len:max(mx,len),val);
    }
}

以及询问：

[x,len,val,g]
if(x==mx)
    if(Tmx.query(0,g)<=k-val)
        return true;
if(x==demx)
    if(Tdemx.query(0,g)<=k-val)
        return true;
if(x!=mx&&x!=demx)
    if(Tnone.query(0,g)<=k-val)
        return true;

那么根据不可能互补的性质，我们只需要正反做两遍就可以得出每一种情况。

一种特殊的情况是 root 本身也被选择了，这种情况下，一定是 f(u)\le k 时可行，复杂度是 n\log^2 的，如果你愿意写可持久化的东西，求 len 可以用树状数组，因为操作撤销不难，而且仅和前缀相关是的树状数组时可以维护前缀或后缀相关的 min/max 的，然后最后的部分也可以树状数组实现。

这就是精神 385 的全部部分。

注意到你有七八成概率写完 T4 的 n\log^2，但是我没有写完，预计零分，哭都哭球了。

但是去看我 T4 代码，有无职转生。

士織（指正）