洛谷黑题做题记录

· · 个人记录

看到了的点个赞吧 qwq

顺便宣传
顺便宣传

前言

因为某种原因，在洛谷本站上刷了点题目。

因为洛谷上没有很好的衡量题目难度的分数啥的，所以就记录黑题吧。

这篇博客很可能长时间不会更新，毕竟我还是更喜欢 CF 和 AT 的题目。

题号都是链接，链的是洛谷的题面。 题目链接为红色的说明为独立想出的（嘴巴出来的也算），蓝色为大体思路方向是对的，黑色的大概说明当时思路偏了或完全没有思路（（（

除了题目链接只有做法简述，因为大概是给自己看的所以可能不会特别清晰。

目前 cnt=2，其中有 0 道还在咕。

最后一次施工：10.15。

\color{blue}{\texttt{P5327 [ZJOI2019]语言}}

2021-10-13 17:18:49

考虑一个结论，树上的一个点集构成的最小联通块的大小是，将点集按照 dfs 序排序之后的 \sum_{i=1}^k \mathrm{dep}_{a_i} - \sum _{i=1}^{k-1} \mathrm{dep}_{\mathrm{lca}(a_i,a_{i-1})}-\mathrm{dep}_{\mathrm{lca}(a_1,a_2,a_3,\cdots a_k)}。

我们用树上差分优化给一条链的集合加入一个点的过程。
但是如果你用桶来维护集合，首先向上合并复杂度就很大，而且每次还是要重新算一遍。

我们用动态开点线段树维护出每个点可以到达的范围中，dfs 序在 [l,r] 范围内，存在的最小值和最大值，以及答案，然后线段树合并即可。

放一下 pushup 的代码： 

void pushup(int x)
{
    T[x].mn=T[ls[x]].mn?T[ls[x]].mn:T[rs[x]].mn;
    T[x].mx=T[rs[x]].mx?T[rs[x]].mx:T[ls[x]].mx;
    T[x].sum=T[ls[x]].sum+T[rs[x]].sum-dep[lca(rnk[T[ls[x]].mx],rnk[T[rs[x]].mn])];
}

用 Euler 序 +st 表来 O(n \log n )- O(1) 求 lca，复杂度是 O(n+q) \log n 的。

\color{blue}{\texttt{P6670 [清华集训2016] 汽水}}

2021-10-14 07:11:23

辣鸡 O(n \log^3 n) 做法。

首先考虑二分答案，设当前值为 \mathrm{mid}，那么需要满足 k-\mathrm{mid}<\mathrm{ave}<k+\mathrm{mid}，不妨设其为 L,R。

考虑点分治，维护出每个后代到根的路径的长度 s 及边数 c。
我们现在要求两个不同子树的后代有 l < \dfrac{s_1+s_2}{c_1+c_2}<r。
有 s_1-rc_1<rc_2-s_2，lc_2-s_2 <s_1-lc_1。
设一个路径 (c,s) 对应一个点对 (x,y)=(s-rc,s-lc)。
则上面那个式子可以转化为 x_1<-x_2,y_1>-y_2。
这就是一个二维数点问题，这样就是 O(n \log^3 n) 的了，如果用 DS 去维护看上去常数就很大。

仔细一想我们并不需要求出具体是多少个，那么我们用 zzy 点分，每次合并最小的两棵子树，按照一个下标排序，求出前缀 \max，然后二分即可，常数小很多。

还有一些题，做了没写啊……可惜我，到此为止了。