zcmimi's blog
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
查看原题

点击跳转

GCD-Extreme top: 0

g(n) = \sum_{i=1}^{n-1} \gcd(i,n)

$$

\sum{i=1}^{n-1} \sum{j=i+1}^n \gcd(i,j)

\\

= \sum_{i=1}^n g(i)

$$

$$

g(n) = \sum_{i=1}^{n-1} \gcd(i,n)

\\

= \sum{d|n}d \sum{i=1}^{n-1}[gcd(i,n)=d]

\\

= \sum{d|n}d \sum{i=1}^{\frac nd - 1}[gcd(i,n)=1]

\\

= \sum_{d|n}d \times \varphi(\frac nd);

$$

求出g的前缀和

可以用筛的方式求g

O(n \sqrt n + T);

不能用之前的套路,否则会tle

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

点击跳转

f_i表示前i块土地

f_i=\min_{j=1}^{i-1}(f_j+maxw[j-1][i]\times maxh[j-1][i])

这样的话怎么想都没有办法优化

我们发现,如果一块土地被另一块土地所包含(即长和宽都比另一块土地小),

那么只需购买那另一块土地即可,于是我们可以据此筛掉其他的土地,

只剩下一些长度递减,宽度递增的土地

那么:

f_i=\min_{j=1}^{i-1}(f_j+l[j+1]\times w[i])

设任意0\le j<k<i,若从j转移比从k转移优,那么

f_j+l[j+1]\times w[i]\le f_k+l[k+1]\times w[i] \\ w[i](l[j+1]-l[k+1])\le f_k-f_j \\ w[i]\le \frac{f_k-f_j}{l[j+1]-l[k+1]}

维护一个下凸壳就完事了

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

点击跳转

lct无脑做

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

点击跳转

我们可以发现交换相邻两个位置用2操作更优,其他的用1操作

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

点击跳转

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

点击跳转

55/73
Search
search