zcmimi's blog

arrow_back共13篇文章

avatar
zc
2020-02-29 13:32: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
2019-12-31 11:31:00
查看原题

点击跳转

这个图是个DAG,我们可以很快地处理出每个点以他为起点(ds_i)或终点(dt_i)的最长路

接着我们枚举删掉哪个点

我们可以将拓扑序小于当前点的点称作A集合,大于的称作B集合

删掉这个点后的最长路有三种可能:

A\rightarrow A,A\rightarrow B,B\rightarrow B

(to指x连接的点)

当删除一个点x时,我们可以删去所有集合中的dt_to+1+ds_x(反向图中的)

求出集合中的最大值就是当前最长路长度

接着将dt_x+1+ds_to加入集合,转移到下一个状态(原图中的)

于是我们需要一个数据结构满足以下要求:

  1. 插入某个值
  2. 删除某个值
  3. 查找最大值

我们可以用堆(手写堆或者两个stl优先队列)、平衡树、权值线段树等维护

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

点击跳转

先按左端点排序,每次添加右端点的时候如果堆中个数等于k就统计答案,然后弹出最小的右端点

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

点击跳转

先求个异或前缀和,然后就变成求k对最大异或和

因为(i^j) = (j^i)

所以我们设2k对,到答案在除以2就可以了

我们先找出每个点能得到的最大异或和,然后放堆里

每次取出堆顶,求出它能得到的第rk+1大的异或和

如果rk+1 \le n,那就放到堆里

(因为一个点最多用n次,要不就重复了)

记得long\ long

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

点击跳转

同usaco工作调度

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

点击跳转

n个小根堆,然后启发式合并即可

可以用并茶几判断一个人所在的团

唉唉,过了,stl开o2

等等,居然是左偏树

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

点击跳转

这题真的很妙

可以想到二分最大值

问题就转化为如何判断是否合法

从左到右扫描区间的左端点,扫描到的就把右端点放入堆

每个点的权值可以用线段树树状数组维护

扫描时遇到点值不够时,就从优先队列中找到最大的右端点,区间加一遍

当优先队列为空或次数不足时就不符合要求

1/2
Search
search