zcmimi's blog

arrow_back共13篇文章

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

点击跳转

这题真的很妙

可以想到二分最大值

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

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

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

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

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

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工作调度

2/2
Search
search