zcmimi's blog
avatar
zc
2020-01-18 23:37:00
查看原题

点击跳转

看到边不能重复用,n\le 200,T\le 200就可以想到网络流

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

点击跳转

先钦定树的重心处理出答案

若当前点是距离最大点对的lca(即在它们之间的路径上),这个点就是最优的

否则最优答案一定在最大点对的lca的子树中

每次都选树的重心来处理,最多需要处理\log n次,总复杂度\Theta(n \log n)

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序作为下标,深度作为时间轴

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

点击跳转

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

点击跳转

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

点击跳转

f[i][j]表示前i个分j个邮局

f[i][j]=\min(f[x][j-1]+w[x+1][i])

满足决策单调性

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

点击跳转

Count-on-a-tree-II top: 0

树上莫队模板

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

点击跳转

模板

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

点击跳转

看到交换相邻字母,就想到逆序对

考虑一下,一定是将A的每个字母移动到离它最近的B中相同字母的位置

我们可以用讲位置存起来然后处理一下

之后数组变成了A中每个位置最后在B中的位置

这个数组中逆序对的数目就是答案

34/73
Search
search