zcmimi's blog

arrow_back排序共12篇文章

avatar
zc
2020-04-26 14:01:00
查看原题

点击跳转

建立新数c,使c_i=a_i-b_i

那么就是要找多少对i<jc_i>c_j

c排序,然后双指针统计一下就可以了

avatar
zc
2020-01-21 16:39:00
查看原题

点击跳转

排序后动态规划

f[i][j]表示前i个女生,至少有j个比男生高

f[i][j]=(f[i-1][j]+f[i-1][j-1]\times(p-j+1))\times(n-i)!(p表示有p个男生比前i个女生矮)

avatar
zc
2020-01-20 10:19:00
查看原题

点击跳转

先排序

从小到大添加

如果有以a_i-1的组,那么a_i必然添加在目前以a_i-1结尾的组的末尾

否则新建一个组

可以使用 桶+堆 实现

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

点击跳转

就是直接求中位数作那个点

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

点击跳转

首先,我们只用分析 NO 的情况,其他的都是 YES,NO 的情况有两种:

  1. x 既不在 A 中,也不在 B 中,即找不到 a-x 和 b-x,NO;
  2. x 既可以在 A 中,也可以在 B 中,也就是找到了 a-x 和 b-x,如果 x 在 A 中,那么 b-x 一定不在 B 中,因为数唯一,所以 b-x 只能在 A 中,也就是说必须存在 a-(b-x),如果不存在就行不通,同理得如果 x 在 B 中,则必须存在 b-(a-x),如果不存在就行不通,那么如果两个方案都行不通了,也就是说 NO 了。
avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

一个矩形要想被保护的话,必须满足所有行 / 所有列上均有一个车的限制。这样我们解决问题就可以转化为判断一个矩形所有行上是否都有一个车了(对于列只需要把图转一下做就可以)。这样我们自然想到线段树 + 扫描线,我是用列上的扫描线从上到下,每一次扫到一个矩形的下边界就判断一下。线段树上维护每一列上距离最远的一个车的纵坐标,我们判断一个矩形是否被保护就只需要判断最远的车是否在当前矩形的范围内了。感觉OFN说的扫描线就是把问题转化到一个前缀的维护上面去其实是挺有道理的恩~

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

点击跳转

m \le 5000

数据这么小,直接把边排序一下,然后暴力枚举,用kruskal就可以了

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

点击跳转

只用一个矩形的当然很容易求

用两个矩形的话:

先把所有点按x坐标排序,提前记录从前数和从后面数的最大的坐标和最小的坐标(x,y都要)

枚举断开的位置,记录最小值

计算按y轴方向断开的方式一样,把x,y交换后如法炮制就可以了

tip:

记录坐标最小值时要把坐标初始化为- \infty,要开long\ long,要不然会出锅

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

点击跳转

图形可以分割成一个个小矩阵

于是我们可以把每个矩形变成两条线段后对这些线段进行排序

如此

那么总共覆盖了多少长度?

线段树求!

那管儿子节点的事干嘛,让他们自生自灭得了

于是,我们想到,除左右端点l,r之外,在线段树的每个节点上维护两个值:该节点代表的区间被矩形覆盖的长度len,该节点自身被覆盖的次数cnt。最初,二者均为0.

注意: 每个节点代表的范围是[l,r+1],最后面的那个节点不算入统计

对于每一个(x,y1,y2,k),我们再[val(y1),val(y2)-1](离散化后的区间)上执行期间修改。该区间被线段树划分成 \log n个节点,我们把这些节点的cnt都加k

对于线段树中任意一个节点 [l,r] ,若cnt>0,则len等于raw(r+1)-raw(l)(离散化前的距离),否则,该店len等于两个子节点的len之和。在一个节点的cnt被修改,以及线段树从下往上传递信息时,我们都按照该方法更新len值。根节点的len值就是整个扫描线上被覆盖的长度

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

点击跳转

1/2
Search
search