zcmimi's blog

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

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

点击跳转

打算直接把标记用vector记录里,以为可以水过去,结果mle了

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

点击跳转

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

点击跳转

二分

判断的时候枚举区间,用rmq或单调队列来求最值,还可以用堆(看题解的)

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

点击跳转

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

点击跳转

线段树解法:

我们记录d_x表示x的深度还有dfs

每个点修改的时候把它的子树都加上val

因为记录了深度,所以d_{x'}如果和d_x同奇偶则加上val,否则减去val

树状数组解法:

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
查看原题

点击跳转

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

点击跳转

直接边bfs边判断就可以了

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

点击跳转

思路剧毒无比

f[i][j]表示在i的子树中,i所在的连体块大小为j\frac{\text{最大得分}}{j}

f[i][j] = \max(f[i][k] \times f[to][j-k])

f[i][0] = \max(f[i][0],f[i][j] \times j)

还没完

吐血的是还要写高精

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

点击跳转

可以用带权并查集维护

s_x表示x到父亲的异或值

当合并的时候

l=l-1

fl,fr分别为l,r的父亲

合并后应该是:s_r \bigoplus s_l = x

\because s_r' = x \bigoplus s_l, s_r' = s_r \bigoplus s_{fr}',

\therefore s_{fr}' = x \bigoplus s_l \bigoplus s_r

我们又看到0 \leq i < 2^{30}

我们可以用hash或map离散化

注意l,r可以为0,所以实际操作时应该++r

52/65
Search
search