zcmimi's blog

arrow_back枚举共8篇文章

avatar
zc
2020-05-03 01:04:00
查看原题

点击跳转

暴力枚举即可

avatar
zc
2020-01-19 21:11:00
查看原题

点击跳转

f[k][i][j]表示前k种面值,Ai元,Bj元最少交换几张

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

点击跳转

一个点对应的只有可能是R,G,B

那么枚举3次就完事了

枚举以R为起点,G为起点,B为起点

记录前缀和S_i表示前i个出错的有几个

ans=\min_{i\ge k}(S_i-S_{i-k})

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

点击跳转

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

点击跳转

两点之间距离为MAX(|x-x'|,|y-y'|)

这种距离好像叫做切比雪夫距离

套路:

将一个点 \color{Blue}{(x,y)(x,y)} 的坐标变为 \color{Blue}{(x+y,x-y)(x+y,x−y)}后,原坐标系中的曼哈顿距离 = 新坐标系中的切比雪夫距离

那么: 将一个点 \color{Blue}{(x,y)(x,y)} 的坐标变为 \color{Blue}{(\frac{x+y}{2},\frac{x-y}{2})}后,原坐标系中的切比雪夫距离 = 新坐标系中的曼哈顿距离!

假设当前所有松鼠来x

\Delta X(a,b) = |a_x - b_x| , \Delta Y(a,b) = |a_y-b_y|

$$ ans =\sum{i=1}^n d(i,x) \\ = \sum{i=1}^n\Delta X(i,x) + \sum_{i=1}^n \Delta Y(i,x)

$$

假定x,和y都是有序的。

那是不是可以用前缀和呢?

lowerbound一下,前后反过来就可以了

最后:记得加 \color{red}{long\ long} !

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

点击跳转

其实一点stl什么的都不用用到

区间交也就是[\max(l_i),\min(r_i)]

我们要求的就是每次删掉某个区间后其他区间的区间交

我们只需要记录最大l_i和次大l_i还有最小r_i和次小r_i

若当前要删掉的区间[l_i,r_i],l_i为最大L,那我们就取次大L

R同理

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

点击跳转

H:minH , V:minV

  A \times (h-H) + B \times (v-V) \le C

A \times h + B \times v -C \le A \times H + B \times V

s = Ah + Bv - C,按s排序,确保i可以取j就可以取(j<i)

枚举H,V,然后用双指针,具体看代码

1/1
Search
search