zcmimi's blog
avatar
zc
2020-09-14 16:15:00
查看原题

点击跳转

题意: 给一颗树,每条边权值可以修改为x,使得修改后这条边可以在最小生成树上,问x最大可以是多少?

首先求出最小生成树(以下的树指最小生成树)

修改一条边时,若不是最小生成树上的边,则为树上该边两端节点之间的最大值

若是树上的边,那么就是该边子树中找出一些非树边(使它们最大值尽可能小)连接除子树部分的点,答案为该边权值

看上去不是很好处理

我们将非树边按权值从小到大排序,从下往上合并,用并查集维护即可

每次遇到非树边x,y时,就更新并合并x\to \text{lca}_{x,y},y\to \text{lca}_{x,y},从下往上跳时,并查集可以跳过已经打过标记的边

详见代码

avatar
zc
2020-09-11 22:22:00
查看原题

点击跳转

可以发现查询的c\le 20,那么我们直接对每个节点记录每个c的答案

区间加

设当前区间a_1,a_2,\dots,a_n

区间加后:a_1+x,a_2+x,\dots,a_n+x

选取i个方案:

\begin{aligned} &\quad (a_1+x)(a_2+x)\cdots(a_i+x)\\ &=a_1a_2\cdots a_i+xa_2a_3\cdots a_i+x^2a_3a_4\cdots a_i+\dots\\ &=a_1a_2\cdots a_i+\sum_{j=1}^ix^j \left( \text{从i个数中取出i-j个数的乘积之和} \right) \end{aligned}

该区间取i个数的乘积之和增加的贡献:

\displaystyle ans_i\operatorname{+=}\sum_{j=0}^i x^{i-j}ans_j{n-j\choose i-j}

区间反转

选取奇数个的答案变成相反数

选取偶数个的答案没有影响

区间查询

设当前答案为ans,左儿子答案为l,右儿子答案为r

\displaystyle ans_i=\sum_{j=0}^i l_j\times r_{i-j}

(左边选j个,右边选i-j个)

avatar
zc
2020-09-10 14:05:00
查看原题

点击跳转

每次给一个叶子节点添加两个儿子,而这个叶子节点能到达的最远的点,也就是上一次求得的直径的两个端点之一

那么每添加一个点更新改点,比较直径与该点到之前直径两端的距离即可

avatar
zc
2020-09-10 12:45:00
查看原题

点击跳转

一个数如果两边的数都比它大,那么删掉它是最优的

那么用单调栈维护就可以了

avatar
zc
2020-09-10 12:45:00
查看原题

点击跳转

每个容器x求出它存活轮数的期望可以表示为

\sum_{i=1}^{n-1}P(x_i)

x_i表示第x个容器到第i轮仍未被击倒

记录L_ii左边第一个比它大的数的位置,R_ii右边第一个比它大的数的位置

每个容器i被击倒的时候也就是[L_i,i][i,R_i]的容器都被选中

P(A)表示[L_i,i]全被选中,P(B)表示[i,R_i]全部被选中,l=i-L_i,r=R_i-i,

\displaystyle \begin{aligned} P(x_i) &=1-P(A)-P(B)+P(AB)\\ &=1-\frac{{n-1-l \choose i-l}-{n-1-r\choose i-r}+{n-1-l-r\choose i-l-r}}{n-1\choose i} \end{aligned}

avatar
zc
2020-09-08 20:15:00
查看原题

点击跳转

首先两次dfs找出任意一条直径

设直径为序列A,L_i为点i到直径左端的距离,R_i为点ii到直径右端的距离

可以发现这条直径把树分割成了若干棵子树,直径上每个点对应一颗子树

mxd_ii点对应子树的最大深度

从左到右枚举,直到mxd_i<L_i,得到l

从右到左枚举,直到mxd_i<R_i,得到r

序列Alr之间的点都是必须经过的点

avatar
zc
2020-09-08 17:08:00
查看原题

点击跳转

题意:

给出一棵n个点的树,每次询问给出两对叶子,求这两对叶子产生路径的交点数

解法:

先把一条链上的点都+1,然后查询另一条链的权值和就是答案

也就是链加、链查询

可以直接树剖套线段树/树状数组 \log^2

更优秀的线性做法: 虚树

avatar
zc
2020-09-08 07:47:00
查看原题

点击跳转

线段树维护动态直径

考虑设A_x为每个点的深度

答案可以写成这样的形式:

ans=\max_{1\le x<y\le n}\{ A_x + A_y - 2A_{\text{lca}(x,y)} \}

考虑欧拉序

因为边权为正,且欧拉序,那么

ans=\max_{1\le x<z<y\le n}\{ A_x + A_y - 2A_z \}

线段树维护区间内的min,max,sl,sr,s

其中min为区间最小值,max为区间最大值

sl_x=\max_{l<i<j<r} \{ A_i-2A_j \}\\ sr_x=\max_{l<i<j<r} \{ A_j-2A_i \}\\ s_x=\max_{l<i<k<j<r} \{ A_i+A_j-2A_k \}

最终答案就是s_1

修改边权可转化为子树(区间)加

avatar
zc
2020-09-07 16:56:00
查看原题

点击跳转

可以离线处理,按照左右端点排序

考虑每个点的贡献?

记录左边(L_i)/右边(R_i)第一个比它大的地方

  1. 对于区间[L_i,R_i],它有p_1的贡献
  2. 对于区间[l,R_i],l\in [L_i+1,i-1],它有p_2的贡献
  3. 对于区间[L_i,r],r\in [i+1,R_i-1],它有p_2的贡献

每个询问[l,r]可以转化为r的答案减去l-1的答案

把转化后的询问和每个点的贡献区间按位置排序

对于1,我们在扫到R_i时,更新点L_i的贡献

对于2,我们在扫到R_i时,更新区间L_i+1i-1的贡献

对于3,我们在扫到L_i时,更新区间i+1到R_i-1的贡献

avatar
zc
2020-09-02 16:45:00
查看原题

点击跳转

思路还算挺神奇的

题意:

\sum C_i=k,要让\sum \dfrac{A_i}{C_i}最小

T_i=\dfrac{A_i}{C_i}

假设我们每次要给一个C_i加一,那么\Delta T_i=\dfrac{A_i}{C_i}-\dfrac{A_i}{C_i+1},

我们要让\Delta T_i尽可能大

这样一直加一到最后,会让所有\Delta T_i趋近于相同

\begin{aligned} \Delta T_i &=\dfrac{A_i}{C_i}-\dfrac{A_i}{C_i+1}\\ &=\dfrac{A_i}{C_i(C_i+1)}\\ &=\dfrac{A_i}{C_i^2+C_i} \end{aligned}\\ C_i^2+C_i-\dfrac{A_i}{\Delta T_i}=0\\ C_i=\dfrac{-1+\sqrt{1+\frac{4A_i}{\Delta T_i}}}2

由于\Delta T_i是单调的,\Delta T_i越小,答案越小

所以我们可以二分\Delta T_i,并倒推得出C_i

13/73
Search
search