menu zcmimi's blog

arrow_back 排序

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

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

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

include<bits/stdc++.h

zc
2020-04-26 14:01

排序后动态规划

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

f[i][j]=(f[i-1][j]+f[i-1][j-1]\times(p-j+1))\times(n-i)!

zc
2020-01-21 16:39

先排序

从小到大添加

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

否则新建一个组

可以使用 桶+堆 实现 ```cpp

include<b

zc
2020-01-20 10:19

一个矩形要想被保护的话,必须满足所有行 / 所有列上均有一个车的限制。这样我们解决问题就可以转化为判断一个矩形所有行上是否都有一个车了(对于列只需要把图转一下做就可以)。这样我们自然想到线段树 + 扫

zc
2019-12-21 19:47

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

![](https://s2.ax1x.com/2019/08/08/e

zc
2019-12-21 19:47

咋一看:

f[i][j] = MAX(f[i-1][j-1]+a[j]*i,f[i][j-1]+a[j]*j)

n \le 3 \times 10^5,。。。

。。。

那么其实这不是

zc
2019-12-21 19:47

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

```cpp

include<bits/stdc++.h>

namespace ZDY{

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

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

  1. x 既不在 A 中,也不在 B 中,即找不到 a-x 和 b-x,NO;
  2. x 既可以在 A 中,也可以在
zc
2019-12-21 19:47

m \le 5000

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

include<bits/stdc++.h>

namespace ZDY{

zc
2019-12-21 19:47

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

用两个矩形的话:

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

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

计算按y轴方向断开

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