zcmimi's blog

arrow_back前缀和共23篇文章

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

点击跳转

f_i表示前i个拆分后最大战斗力和

f_i=\max_{j=1}^{i-1}(f_j+a(s_i-s_j)^2+b(s_i-s_j)+c)

这个很明显是斜率优化式子

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

f_j+a(s_i-s_j)^2+b(s_i-s_j)+c\ge f_k+a(s_i-s_k)^2+b(s_i-s_k)+c \\ 2as_i\le\frac{(f_k+a{s_k}^2-bs_k)-(f_j+a{s_j}^2-bs_j)}{s_k-s_j}

维护个下凸壳就完事了

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

点击跳转

连续和相当于区间和,题目的意思是求所有S_i-S_j的异或和

一般位运算的题我们都拆成二进制下32位来解决

考虑每一位

枚举k

如何统计有多少个((S_i-S_j)>>k)\&1呢?

可以开两个权值树状数组来统计01的数量

如果当前S_i的第k位为1,如果S_j\&(1<<k) = 0S_i+S_j在二进制下进位不会影响到第k位的都符合条件

也就是S_j\&((1<<k)-1) \not = (S_i\&((1<<k)-1))

\&((1<<k)-1)也就是取前k

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

点击跳转

首先二分出最大一段的最小值,然后dp找出方案数

f[i][j]表示前j个分成i组的方案数,求出的最小值为x

f[i][j] = \sum(f[i-1][k])(S_j-S_k \le x,k \le j-1)

\Theta(n^3m)当然会TLE

我们发现只要找到最小的k之后[k,j-1]都是合法的

这时我们就可以前缀和优化dp

sum[i][j] = \sum_{k=0}^j f[i][k]

f[i][j]=sum[i-1][j-1] - sum[i-1][k-1]

可是\Theta(n^2m)还是TLE

我们可以先预处理出第一个S_j-S_k \le xk

因为S_i具有单调性,所以k不需要每次都重新枚举

还没结束

因为f[i][j]每次更新的时候只需要用到f[i-1][...]这一维,我们可以用滚动数组滚掉数组的一维

但是\Theta(nm+n \log \sum L_i)的复杂度还是觉得很悬

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

点击跳转

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

点击跳转

预处理出二维前缀和

预处理出每个以(i,j)为右下角的A*B矩阵的和

预处理出每个以(i,j)为右下角的C*D矩阵的和

先用单调队列出列的C*D的最小值

再用另一个单调队列处理出行的

然后枚举比较即可

照着代码意会

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

点击跳转

咋一看:

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,。。。

。。。

那么其实这不是dp题,而是思维题

我们发现:

(s[r]-s[l])\times k +(s[r']-s[l'])\times(k-1)+...+s[r''']

s表示前缀和,g表示后缀和

相当于:

g[x_1]+g[x_2]+g[x_3]+...

那我们给后缀和排个序就可以了

注意:

答案里必须要有g_1,这就是为什么要g1加(1ll<<50)再答案减(1ll<<50)的原因

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

点击跳转

S_i表示[1,i]的异或和,区间[l,r]的异或和就是S_r \bigoplus S_{l-1}

那么题目可以转化为[l-1,r]中有多少对S_i \bigoplus S_j = k,直接用莫队统计就可以了

2/3
Search
search