zcmimi's blog

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

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

可以先考虑离散化

离散话后是1~n

一般要求中位数可以:

二分中位数x

将区间中<x的赋值为-1,\ge x的赋值为-1

若区间和为0,那么x就是中位数

题目是要求左端点在[a,b],右端点在[c,d]的序列的最大中位数

区间[b+1,c-1]是必选的

我们可以求[a,b]的最大后缀和[c,d]的最大前缀

如果这三个部分的和大于零,那么当前二分的值是合法的

这个一看就可以用线段树维护

我们再来考虑x变成x+1会有什么变化:

  1. 原来<x的还是-1
  2. 原来>x的还是1
  3. 原来=x变成-1

所以我们只需修改值为x的位置(可以先用链表或vector存下所有值为x的位置)

其实从小到大排序后按顺序更改就完事了

数离散化后的大小不超过n

我们可以先预处理出所有x(中位数)对应的线段树

可是空间不够啊

这时候主席树就派上用场了

下面是简洁的代码:

avatar
zc
2019-12-22 14:39:00
查看原题

点击跳转

此题卡常,需要使用二维树状数组

联想一维的树状数组:

差分数组:d_0=a_0,d_i=a_i-a_{i-1}(i>0)

令差分数组的前缀和sd_i=\sum_{j=0}^id_j,那么sd_i=a_i

我们现在来看看二维前缀和

s(i,j)=s(i-1,j)+s(i,j-1)-s(i-1,j-1)+a(i,j)

查询(x_1,y_1)(x_2,y_2)的和则为:

s(x_2,y_2)-s(x_1-1,y_2)-s(x_2,y_1-1)+s(x_1-1,y_1-1)

我们可以使用差分数组:

d(i,j)=a(i,j)-(a(i-1,j)+a(i,j-1)-a(i-1,j-1))

修改

d(x_1,y_1)+=v

d(x_1,y_2+1)-=v

d(x_2+1,y_1)-=v

d(x_2+1,y_2+1)+=v

举个例子:

0 0 0 0 0
0 1 1 1 0
0 1 1 1 0 
0 0 0 0 0

1部分加上v,那么

0  0 0 0 0
0 +v 0 0 -v
0  0 0 0 0 
0 -v 0 0 +v

查询

对于点(x,y)它的值应该是:\sum\limits_{i=1}^x\sum\limits_{j=1}^y d(i,j)

那么(1,1)(x,y)的和就是:

$$

\sum{i=1}^x\sum{j=1}^y\sum{p=1}^i\sum{q=1}^j d(p,q) \ =\sum{i=1}^x\sum{j=1}^yd(i,j)\times(x-i+1)\times(y-j+1) \ =\sum{i=1}^x\sum{j=1}^yd(i,j)\times[(xy-xj+x)+(-yi+ij-i)+(y-j+1)] \ =\sum{i=1}^x\sum{j=1}^yd(i,j)\times (xy+x+y+1)-d(i,j)\times i(y+1)-d(i,j)\times j(x+1) + d(i,j)\times i \times j $$

我们需要维护d(i,j),d(i,j)\times i,d(i,j) \times j, d(i,j)\times i \times j

avatar
zc
2019-12-22 13:54:00
查看原题

点击跳转

区间加,单点查询

设差分数组d_i=a_i-a_{i-1}

修改:d_l+=v,d_{r+1}-=v

查询:a_i=\sum\limits_{j=1}^id_j

区间加,区间查询

\sum_{i=1}^na_i=\sum_{i=1}^n\sum_{j=1}^id_i \\ =\sum_{i=1}^nd_i\times(n-i+1) \\ =n\sum_{i=1}^nd_i-\sum_{i=1}^n d_i\times(i-1)

维护两个树状数组,一个记录d_i,另一个记录d_i\times(i-1)

修改:

d_l+=v,d_{r+1}-=v

d'_l+=v\times(l-1),d'_{r+1}-=v\times(l-1)

查询:如上述

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

点击跳转

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

点击跳转

一道中档题-Factorial top: 0

观察一下,

一个数在k进制下有多少个后缀0,就是一个数能整除k多少次

那么先把k分解质因数,并求出每个质因数的个数,存到数组里面

要怎么算出n!里面有多少个质因数?

p(p是质数)个数里面有一个p,这些数是p^1,p^2,...p^x,这些数中每p个数中又有一个p,那我们这样一直循环下去就可以求出质因数的个数,然后在除以他们在k中出现的次数,然后取min就是答案

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

点击跳转

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

点击跳转

可以看到n\le 15,我们很容易想到状压

状压解法:

f[i][j]表示到了第i位,匹配的状态为j

代码:

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

点击跳转

静态链分治

记得开long\ long

31/66
Search
search