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

点击跳转

仔细考虑一下,最终能够形成最小权值的生成树的情况一定是把S都用在减小某条边的费用

  1. 如果那条边在最小生成树上,那么直接处理即可

  2. 如果在外面,设这条边为x \rightarrow y,我们求出最小生成树上xy上最大的一条边,删掉这条边

枚举删掉哪条边,然后执行上面的操作就可以了

记得开long\ long,rmq的数组开大点

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

点击跳转

先用并查集求出所有连通块(相邻且相同颜色的节点)

接着是相邻节点的颜色都不一样的一棵树

最少次数就是树的直径/2了

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

点击跳转

假设我们已经知道区间[l,r]左右节点的答案

记录:

lv,rv:左右端点的值
s: 区间答案
l:以左端开始最长下降
r:以右端结束的最长上升
L:以左端开始最长先上升(再下降)
R:以右端结束最长先上升(再下降)

然后考虑最高点再左节点还是有节点

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

点击跳转

好题!

重新排序后能变成回文串,出现次数为奇数的字母最多只能有一种

因为只有22种字符所以我们可以用状态压缩来记录每种字母出现的次数是奇数或者偶数

设路径端点的两端为x,y,d_x表示1~x所有状态的异或值,D_x表示x的深度

那么如果这条路径满足条件,则d_x \oplus d_y在二进制下最多只有一个1

它的长度为D_x + D_y - 2 \times D_{lca(x,y)}

我们可以开一个桶来记录每种状态出现的最深的位置是哪里

sta为满足条件的状态

用每个店更新答案的时候就ans=\max(ans,b[sta \oplus d_x] + D_x - 2 \times D_{lca})

接下来就按静态链分治的套路操作就可以了

复杂度: \Theta( n \log n)

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

点击跳转

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

点击跳转

f[i][k]为第i位,分成k

f[i][k] = MAX(f[j][k-1] + cnt[j+1][i])

这样的话肯定复杂度爆炸

既然看到MAX,那是不是可以用线段树优化呢?

记录每个点贡献的范围,更新时把这个范围的点++就可以了。

相信看代码可以看懂

其实我还加了滚动数组OwO

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

点击跳转

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

点击跳转

把所有路径上的最大值的和 和 所有路径上的最小值的和 分开算

我们按最大值的计算考虑(最小值就是反过来)

我们考虑一个点能贡献多少次

从它的各个子树中拿出来组合

我们可以按权值从小到大的顺序添加节点

这样就只要和当前要添加的节点联通的点都符合要求

这样的话我们可以用并查集来维护连通块大小

63/66
Search
search