hk_cnyali's Blog

[Summary]

来自xhb课件的一些图论题

有一个 $n\times n$ 的矩阵，矩阵内有 $2n$ 个球。对于 $i \in [1,n]$ ，$(0,i) (i,0)$ 的位置各有一个启动后往右走/往上走的机器人，机器人撞到球会和球一起消失。问启动机器人顺序的方案数，满足所有球最后都消失。

$n \le 10^{5}$

给定一棵 $n$ 个节点的树，有 $m$ 天修路

每一天修一条路的花费固定，为 $w _i(1 \le i \le m)$。第 $i$ 天会指定两个点 $u, v$，在第 $i$ 天时只可以在树中 $u$ 到 $v$ 的链上的任意两点之间修路。同时还有 $p$ 条限制 $(t, a, b)$，表示第 $t$ 天不能在 $a, b$ 之间修路

问最小生成树的总花费。保证无自环重边，$a, b$ 在 $u _t, v _t$ 的路径上，且一定有一个合法生成树。

有$n$堆石子，第$i$堆有$a_i$个

$m$次操作$(l, r, k)$，每次你需要从$[l, r]$堆中取出尽量多石子，且总共不能超过$k$个，问每次最多能取多少个

注意，第$i$次操作是建立在第$1$到$i-1$次都取到你回答的个数下，即询问不是相互独立的

保证任意$[l, r]$不存在包含关系

$n\le 4\times 10^4, a_i\le 500$

有$n$个栈,$m$次操作

区间压数,单点弹栈,求区间栈顶和

强制在线

$n, m\le 5\times10^5$

给你一颗 $n$ 个点的树 , 每个节点有两个权值 $a_i,b_i$

从 $u$ 跳到 $v$ 的代价是 $a_u\times b_v$你需要计算每个节点跳到叶子的最小代价.

$n\le 10^5;-10^5\le a_i, b_i\le 10^5$

继续填小学没学好的坑

都高二了还这么菜...

来自xcy课件的一些树题

坐标轴上有 $n$ 个星球,第 $i$ 个星球坐标为 $i$ ,与星球 $[l_i , i - 1]$ 之间都有双向通道。其中,经过每个通道都需要 1 的单位时间。

定义$dist(x, y)$为从星球$x$出发到达星球$y$的最短时间，求$\displaystyle \sum_{i=l}^{r}dist(x, i)$

多组询问，保证$l < r < x$

$n, q\le 3\times 10^5$