zcmimi's blog

categories/刷题记录/共658篇文章

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

可以先看一下LG P4868 Preprefix sum,很经典一道题,维护一下后缀和就可以了

这题的话就是把上面那道题变了一下

由于值域太大,我们可以使用 动态开点线段树 或 树状数组+离散化

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

f_i表示以i开头合法子序列方案数

f_i=\sum_{j=i+a_i+1}^{n+1} f_j \times {j-i+1 \choose a_i}

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

长链剖分模板

长链剖分优化dp

f_{x,i}表示x子树内与x距离为i的点的个数

f_{x,i}= \sum f_{to,i-1} \\\\ (f_{x,0}=1)

可以发现x从它的儿子继承答案

这时就可以用长链剖分优化dp了(一种类似\text{dsu on tree}的方法)

len_xx到叶节点的最长距离

我们将\max len_{to}设为x的重儿子

x直接继承重儿子的答案,而不用重新再算一次

其他的儿子再按普通方式计算

因为每条链只会被合并一次,因此总复杂度就是\Theta(n)

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

解法1(在线):

bfs序,实现较为麻烦

解法2(离线):

考虑单独的一个节点u,它的操作影响的都是在它子树内的与u深度差小于等于k的节点,那么我们只要维护每层深度的操作总和就行了

修改x影响的只有x的子树,我们可以在dfs时这样操作:

1.进入该点

  1. 实现该点的所有操作
  2. 递归它的子树
  3. 撤销操作

这样就不会影响到其他点了

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

仔细看题意,发现k最大只有400

解法1: 堆 贪心

先把和每个点相连的所有边按边权从小到大排序。

考虑一条路径的两个端点,如果这两个端点间的路径第一次被弹出(是两点间最短路),则我们向其中一端扩展一条与它相连的最短边。

现在假设堆顶有一条路径u\rightarrow v,它的一个端点v是由u\rightarrow扩展来的,此时我们可以尝试把与x相连的边中比x\rightarrow v权值略大的取出来(即排好序后的下一条边),压到堆中。

因为要处理两个端点比较麻烦,我们转化成有向路径(只有一个端点),然后取第2k大的。

记住我们需要维护的信息:路径的两个端点st,ed,端点ed前面的点x(即ed是由st\rightarrow x扩展来的),以及这条路径的长度。

解法2: floyd

考虑答案应该小于等于第k小的边的长度。因此只有前k小的边对答案有贡献。这k条边构成的子图的节点数也是O(k)的,于是我们就可以做floyd了。

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

可以先rmq预处理出区间gcd和区间min

若区间gcd=区间min那么这个区间是合法的

若一个区间合法,那么它一定有合法的子区间

我们可以根据这个性质二分区间长度

解↓决↑!

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

我们可以用倍增求出能控制某个点x的最远的点y的位置

应该将f_xy的点的答案+1

我们可以差分一下,

++ans_{f_x},--ans_{f_y}

然后从下加得到的就是当前点的答案

记得开long long

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

我们可以第一次修改的时候就用第一个黑点建树,可以预处理出a_i表示i到根节点路径上点编号的最小值

我们考虑接下来将一个点x变为黑点对其他点的影响:

显然x变成黑点对它的子树内的点的答案没有影响

对子树外的影响:

子树外的点可以通过根到达x,可以记录一个值t表示根能到黑点的所有路径上值的点的最小编号

查询时答案就是\min(a_x,t)

自己画个图就懂了

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

dfs序作为下标,深度作为时间轴

28/66
Search
search