zcmimi's blog

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

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

点击跳转

就bfs

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

点击跳转

分成两部分

  1. dp出结尾最小是多少

  2. dp出字典序最大的方案

第一步:

f_i表示以i结尾最靠近i的下标

枚举j,判断j是否可行

f_i = max(j)|(num(f[j],j) < num(j+1,i))

第二步:

方法类似第一步

记得考虑前导零

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很小,所以直接k^2dp就可以了

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

点击跳转

直接求很难

突然看到二分的标签

那我们二分k的值,判断排名不就可以了

如何判断排名:

如果区间[l,r]满足要求,那么左端点换成[1,l-1]中的任何一个也都满足要求

那我们只要枚举右端点,然后用双指针法就可以了

求众数可以用莫队的思想

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

点击跳转

图形可以分割成一个个小矩阵

于是我们可以把每个矩形变成两条线段后对这些线段进行排序

如此

那么总共覆盖了多少长度?

线段树求!

那管儿子节点的事干嘛,让他们自生自灭得了

于是,我们想到,除左右端点l,r之外,在线段树的每个节点上维护两个值:该节点代表的区间被矩形覆盖的长度len,该节点自身被覆盖的次数cnt。最初,二者均为0.

注意: 每个节点代表的范围是[l,r+1],最后面的那个节点不算入统计

对于每一个(x,y1,y2,k),我们再[val(y1),val(y2)-1](离散化后的区间)上执行期间修改。该区间被线段树划分成 \log n个节点,我们把这些节点的cnt都加k

对于线段树中任意一个节点 [l,r] ,若cnt>0,则len等于raw(r+1)-raw(l)(离散化前的距离),否则,该店len等于两个子节点的len之和。在一个节点的cnt被修改,以及线段树从下往上传递信息时,我们都按照该方法更新len值。根节点的len值就是整个扫描线上被覆盖的长度

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

点击跳转

前置定理:

d(ij) = \sum_{x|i} \sum_{y|j}[gcd(x,y) = 1]

所以:

n<m

\sum_{i=1}^n \sum_{j=1}^m d(ij) \\ =\sum_{i=1}^n \sum_{j=1}^m \sum_{x|i} \sum_{y|j}[gcd(x,y) = 1] \\ =\sum\limits_{x=1}^n\sum\limits_{y=1}^m \left\lfloor\frac{n}{x}\right\rfloor \left\lfloor\frac{m}{y}\right\rfloor [\gcd(x,y)=1]

x、y换成i、j

\sum\limits_{i=1}^n\sum\limits_{j=1}^m \left\lfloor\frac{n}{i}\right\rfloor \left\lfloor\frac{m}{j}\right\rfloor[\gcd(i,j)=1] \\ =\sum\limits_{i=1}^n\sum\limits_{j=1}^m \left\lfloor\frac{n}{i}\right\rfloor \left\lfloor\frac{m}{j}\right\rfloor \sum_{k|gcd(i,j)}\mu(k)

g(i)=\sum_{i=1}^n \left \lfloor \frac ni \right \rfloor

ans=\sum_{k=1}^n\mu(k) g(\left \lfloor \frac nk \right \rfloor) g(\left \lfloor \frac mk \right \rfloor) \\

49/65
Search
search