0%

「NOI2014」购票

给一棵以1为根的树,每个点$u$有属性$p_u,q_u,l_u$,边有边权。若$v$为$u$的祖先且$u,v$距离不超过$l_u$,则$u$可以花费$d(u,v)p_u+q_u$的代价跳到$v$上。问每个点跳到根的最短距离。

$n\le 2\times 10^5,p_u\le 10^6,q_u\le 10^{12},s_u\le l_u\le 2\times 10^{11},\sum s_u\le 10^{11}$

Read more »

loj 2048. 「HNOI2016」最小公倍数

给一个$n$个点$m$条边的无向图,每条边有属性$a_i,b_i$.有$Q$次询问,每次询问给出$u,v,A,B$,你需要回答从点$u$到点$v$是否存在一条路径$P$(不要求是简单路径)满足 $\max_{e\in P}\{a_e\}=A$且$\max_{e\in P}\{b_e\}=B$

$n,q\le 5\times 10^4,m\le 10^5.$

My solution:

考虑如果我们得到了图$G(A,B)=(V,\{e|a_e\le A,b_e\le B\})$,如何处理询问。维护一个并查集,将$G(A,B)$中所有边加入并维护连通块的$a_e$最大值和$b_e$最大值。

【判定】: $u,v$存在合法路径 $\Leftrightarrow $ $u,v$在$G(A,B)$中连通,且所在连通块$a_e$最大值为$A$,$b_e$最大值为$B$.

所以就是如何得到图$G(A,B)$了。大概就是要实现”不强制在线的二维可持久化并查集”。

Read more »

yLOI2020 题解

扶咕咕6题4.5h残忍虐杀脑子慢手速慢选手Orz.不过题的质量是很好的,尤其是D题,我可能一辈子都出不出这种题,真的只能Orz。

Read more »