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

点击跳转

动态开点线段树模板

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

点击跳转

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

应该将f_xy的点的答案+1

我们可以差分一下,

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

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

记得开long long

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

点击跳转

我们考虑两个断点(设为l,r)符合的条件:

每种颜色的珠子只能出现在其中一条链中

也就是若[l,r]中出现了某种颜色[l,r]也就包含了所有的这种颜色

我们可以记录颜色出现的前缀和

记录前i个位置每种颜色的出现次数,如果位置i是 颜色a[i]的最后一个位置, 就把颜色 a[i] 的结果清零。

这样若两个位置的前缀和相同,就是合法的

可以通过hash来判断,记录所有hash值,排序后统计

两个分割点 l,r 要尽可能满足 r−l 接近 \frac n2

可以用类似双指针的方式维护

这题卡hash,要双hash

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. ST \xrightarrow{\text{选文科的值}} (i,j) \xrightarrow{\text{选理科的值}}ED

  2. ST \xrightarrow{\text{同时选文科的额外快乐}}new,new\rightarrow(i,j),new\rightarrow(i+1,j)(其他同理)

  3. (i,j)\rightarrow new,(i+1,j)\rightarrow new,new \xrightarrow{\text{同时选理科的额外快乐}}ED(其他同理)

每个点只能选择文科或理科,当某个点选择了文科,那么它向理科(ED)的边都应该要被断开。

它直接连向ED的边、它和别的点组合连向ED的边都要切断

这些边的权值就会从最终答案中减去

infinf同时选文科选理科选文科同时选理科infinf选理科选文科ST(i,j)ED(i+1,j)newnew'
avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

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

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

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

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

点击跳转

a是确定的,考虑b的情况:

  1. a的祖先

    可以作为b的点的数量是\min(d_x,k)(d_xx的深度),

    a的子树中除a外其他点都可以作为c

    总方案数为\min(d_x,k)\times(siz_x-1)

  2. a子树中

    对于每个b,可以作为c的点的数量为siz_b-1

    我们可以dfs序,记录当前区间中深度为d的数

    然后用主席树(可持久化权值线段树)维护

    这样就可以查询深度\in [d_a+1,d_a+k]的所有'点的子树大小-1'的和

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

点击跳转

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

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

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

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

解↓决↑!

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}

35/73
Search
search