zcmimi's blog

categories/刷题记录/共658篇文章

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

点击跳转

$$ \frac{1}{n}\sum_{i=1}^{n}(a_i-\bar a)^2

\\

= \frac 1n \sum_{i=1}^{n}(a_i^2-2\bar a\times a_i+{\bar a}^2)

\\

= \frac 1n (\sum_{i=1}^nai^2 - 2\bar a\sum{i=1}^n a_i + n \bar a^2)

\\

= \frac 1n \sum_{i=1}^n a_i^2 - \bar a^2 $$

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

点击跳转

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

点击跳转

找度最大的点

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

点击跳转

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

点击跳转

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

点击跳转

可以参考线段树或分块维护区间加和区间减的思路

看一下数据范围,每次操作只能O(1)的复杂度。

点的位置可以离散化一下

记得先乘后加

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

点击跳转

f_{k,i}:第i位,改变k

显然f_{k,i} = MIN(f_{k-1,j}+res(i,j))

那这个res要怎么求呢?

res=MAX(a_i,..,a_j)-\sum_{t=j-1}^i a_t

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

点击跳转

55/66
Search
search