zcmimi's blog

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

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

树形dp up and down

考虑 up:

s_x为点x子树中所有点到x的距离之和

S_x = \sum (s_{to}+siz_{to})

考虑 down:

s_{to} = s_{to} + (s_x-s_{to}-siz_{to}) + n - siz_{to}

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

记录每个点左边和右边第一个比它小的,就可以求出它能的贡献区间

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

先把所有区间按右端点排序。

因为m \le 10,所以直接枚举k值就可以了

假设当前位置为i,现在要找位置j满足|b_i-b_j|等于当前k值,可以是b_i-b_j,即b_i > k,也可以是b_j - b_i = k

b_i+k = b_j, b_i+k\le n我们事先用p_x记录值为xb数组中的哪个位置(b_i互不相同,也就是b数组是1~n的组合)

用线段树维护位置i可以达到的最大的值就可以了,因为已经按右端点排序好了,不会超过当前区间的右端点

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

先把所有(替换成),然后每次遇到(cnt++,否则cnt--,如果cnt<0,那么从前面的问号中挑一个从)改成(费用最小的替换掉

如果最后没法使cnt=0,那么就输出-1

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

记录S_i表示[1,i]中大于等于T的个数

[L,R]满足要求时,S_R - S_{L-1} \ge k

如果[L,R]满足要求[1...L,R]都满足要求

于是我们就可以用two\ pointer

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

那个只要有 10000…… 11000…… …… 就可以一直搞下去 直到为0

但是也有特殊情况:

比如k \le 4

不过这种情况特判和dfs都可以解决

33/66
Search
search