数据结构与算法

1811 篇文章
114 人订阅

全部文章

attack

SDOI 2018二轮题解(除Day2T1)

然鹅学了不到一个月文化课再回来看OI的东西有一种恍如隔世的感觉,烤前感觉也没啥可复习的,就补一补去年二轮的题吧。

531
attack

兹瓷查rank和kth的STL平衡树

明天就是一轮省选了啊。。这可能是退役前的最后一篇博文了吧(如果心情不好怕是连游记都会咕)

641
attack

AFO && OI回忆录

T1 2h写个跟\(k\)无关的假算法写到最后发现是三个log,出考场才发现K很小可以直接枚举

993
attack

临时抱佛脚

\(f[i][j] = min(f[i][k], f[k + 1][j])\)的dp方程,猜想其满足四边形不等式

852
attack

洛谷P2664 树上游戏(点分治)

考虑点分治,那么每次我们只需要统计以当前点为\(LCA\)的点对之间的贡献以及\(LCA\)到所有点的贡献。

613
attack

洛谷P3366 【模板】最小生成树(Boruvka算法)

复杂度\(O(n \log n)\),然鹅没有Kruskal跑的快,但是好像在一类生成树问题上很有用

812
attack

BZOJ5118: Fib数列2(二次剩余)

一种做法是直接用欧拉降幂算出\(2^p \pmod{p - 1}\)然后矩阵快速幂。

712
attack

校内模拟-双面间谍(主席树)

给出两个数组\(A, B\),每次询问\(l, r\)。需要最小化\(\sum_{i=l}^r max\{|a-A_i|, |b-B_i| \}\)

622
attack

loj#2312. 「HAOI2017」八纵八横(线性基 线段树分治)

1003
attack

noi.ac#309 Mas的童年(子集乱搞)

记\(s_i\)表示前\(i\)个数的前缀异或和,我们每次相当于要找一个\(j\)满足\(0 < j < i\)且\((s_i \oplus s_j) + s_...

752
attack

loj#6041. 「雅礼集训 2017 Day7」事情的相似度(SAM set启发式合并 二维数点)

只会后缀数组+暴躁莫队套set\(n \sqrt{n} \log n\)但绝对跑不过去。

952
attack

loj#6073. 「2017 山东一轮集训 Day5」距离(树链剖分 主席树)

首先对询问差分一下,我们就只需要统计\(u, v, lca(u, v), fa[lca(u, v)]\)到根的路径的贡献。

662
attack

loj#6074. 「2017 山东一轮集训 Day6」子序列(矩阵乘法 dp)

然后发现可以用矩阵优化,可以分别求出前缀积和逆矩阵的前缀积(这题的逆矩阵炒鸡好求)

864
attack

loj#6073. 「2017 山东一轮集训 Day5」距离(费用流)

我们可以把图行列拆开,同时对于行/列拆成很多个联通块,然后考虑每个点所在的行联通块/列联通块的贡献。

724
attack

洛谷P5108 仰望半月的夜空(后缀数组)

warning:下面这个做法只有95分,本地拍了1w+组都没找到错误我表示十分无能为力

724
attack

二次剩余Cipolla算法学习笔记

若对于给定的\(n, P\),存在\(x\)满足上面的式子,则乘\(n\)在模\(p\)意义下是二次剩余,否则为非二次剩余

1195
attack

BZOJ3122: [Sdoi2013]随机数生成器(BSGS)

直接把\(X_{i+1} = (aX_i + b) \pmod P\)展开,推到最后会得到这么个玩意儿

601
attack

noi.ac #289. 电梯(单调队列)

傻叉的我以为给出的\(t\)是单调递增的,然后\(100\rightarrow0\)

783
attack

51nod“省选”模测第二场 B 异或约数和(数论分块)

811
attack

bitset中_Find_first()与_Find_next()函数

输出结果为233 1001,也就是说如果某个元素之后没有元素的话会返回bitset的大小

802

扫码关注云+社区