20联赛集训day12 题解
A一个暴力的想法是找出这条链，暴力跳。跳的定义是走到第一个满足和 $\geq k$ 的位置。于是可以想到用倍增。设 $f_{x,i}$ 表示 $x$ 点跳 $2^i$ 步在哪个点，首先跳 $2^0$ 步可以二分预处理，然后直接转移就好了。但是这只能处理往上的，往下怎么做呢？一种方法是直接树链剖分，就变成了若干个链的问题，但是这是 $O(\log^2n)$ 的，又难写又难调。我们可以观察到对于...
A一个暴力的想法是找出这条链，暴力跳。跳的定义是走到第一个满足和 $\geq k$ 的位置。于是可以想到用倍增。设 $f_{x,i}$ 表示 $x$ 点跳 $2^i$ 步在哪个点，首先跳 $2^0$ 步可以二分预处理，然后直接转移就好了。但是这只能处理往上的，往下怎么做呢？一种方法是直接树链剖分，就变成了若干个链的问题，但是这是 $O(\log^2n)$ 的，又难写又难调。我们可以观察到对于...
题目描述给 $n$ 个节点的树。定义 $g(a,b)$ 表示 $a$ 的子树中除 $b$ 之外深度不超过 $b$ 的节点个数，定义 $f(v) = \sum_{x \in anc(v)} g(x,v)$ (其中 $anc(v)$ 是 $v$ 的祖先组成的集合)。 现在要对于每一个点，求出 $f(v)$ $n \leq 10^5$题解如果这题 $n \leq 10^5$ 那还是很 eazy 的...
题目链接题目大意现在有一个 $n\times m$ 的矩阵，给定的起始点上有个钢琴，矩阵上有些方格是障碍物，用连续的区间 $[l,r]$ 和一个参数 $d$ 表示在时间 $[l,r]$ 时会向 $d$ 方向滑动（上下左右），当然每个时间点可以选择让钢琴不动，不允许钢琴超出边界或者碰到障碍，询问钢琴可能走的最远距离是多少。 其中 $1 \leq n,m \leq 200$,区间个数 $k \l...