menu zcmimi's blog

arrow_back

题目的意思就是相同子树中的点不能分配到同一段内存

每个点都开一个大根堆

合并一个点和它的子节点的时候最大值互相对应

启发式合并

具体看代码 ```cpp

include<bits/stdc+

zc
2020-02-29 13:32

仔细看题意,发现k最大只有400

解法1: 堆 贪心

先把和每个点相连的所有边按边权从小到大排序。

考虑一条路径的两个端点,如果这两个端点间的路径第一次被弹出(是两点间最短路),则我们向

zc
2020-01-18 22:40

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

接着我们枚举删掉哪个点

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

删掉这个

zc
2019-12-31 11:31

这题真的很妙

可以想到二分最大值

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

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

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

扫描时遇到点值不够时,就从优

zc
2019-12-21 19:47

算法:贪心+堆维护

贪心策略:

我们考虑先按t贪心,中途再更改。 按t从小到大排序之后,开始轮流遍历每个建筑。 如果中途某个建筑i无法在t_it的时间内修复,那么在先前选择修复的建

zc
2019-12-21 19:47

```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define il __inline__ 
zc
2019-12-21 19:47

离线处理,倒着添加

```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
#define il 
zc
2019-12-21 19:47

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

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

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

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

每次取出堆顶,求

zc
2019-12-21 19:47

二分

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

include<bits/stdc++.h>

namespace ZDY{

#pragma G
zc
2019-12-21 19:47

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

```cpp

include<bits/stdc++.h>

namespace ZDY{

zc
2019-12-21 19:47
1 / 2
Search
search