menu zcmimi's blog

arrow_back 前缀和

很妙的一道题

对每位置i分别统计[l,i],l\in [1,i]的方案数

S_i表示\sum_{j=1}^i [H_i \ge X],pre为位置i-1的方案数,$now

zc
2020-03-23 16:44

先离散化,然后用树状数组统计两边的数目,比较即可 ```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3)
zc
2020-03-23 00:30

带 套 路 题

$$ \sum{i=1}^n\sum{j=1}^n(i+j)^k\mu^2(\gcd(i,j))\gcd(i,j) \ =\sum_{d=1}^n \mu^2(d) d

zc
2020-03-20 12:57

我们考虑两个断点(设为l,r)符合的条件:

每种颜色的珠子只能出现在其中一条链中

也就是若[l,r]中出现了某种颜色[l,r]也就包含了所有的这种颜色

我们可以记录颜色出现的前缀和

zc
2020-01-18 22:40

这题考验的是仔细读题

可以发现修改带查询的只有1000个,这部分直接暴力求就可以了

区间加可以用差分来解决

剩下的部分:

可以预处理出[1,i]的答案ans_i

查询[l,r]

zc
2020-01-18 22:40

可以先看一下LG P4868 Preprefix sum,很经典一道题,维护一下后缀和就可以了

这题的话就是把上面

zc
2020-01-18 22:40

我们可以用倍增求出能控制某个点x的最远的点y的位置

应该将f_xy的点的答案+1

我们可以差分一下,

++ans_{f_x},--ans_{f_y}

然后从下加得到的就是

zc
2020-01-18 22:40

```cpp

include<bits/stdc++.h>

namespace ZDY{

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

预处理出二维前缀和

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

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

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

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

zc
2019-12-21 19:47

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

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

$f[i][j] = \sum(f[i-1][k])(Sj-S

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