树链剖分学习

对于序列上线性结构,我们可以很轻松的用一些数据结构来维护区间的某些信息。

但是对于树上的结构,对于不需修改的情况下,可以用树上倍增和树上差分很轻松的维护。 但对于需要修改的情况,倍增和差分就难以解决了。

这时候我们就需要一个更加有效的方法来维护,就是树链剖分。

组合数公式

(Cn0)2+(Cn1)2+(Cn2)2+...+(Cnn)2=(C2nn)2(C^{0}_{n})^{2} + (C^{1}_{n})^{2} + (C^{2}_{n})^{2} + ...+ (C^{n}_{n})^{2} = (C^{n}_{2n})^{2}

Cn1+2Cn2+3Cn3+...+nCnn=n2n1C^{1}_{n} + 2C^{2}_{n} + 3C^{3}_{n} +...+nC^{n}_{n} = n2^{n-1}

网络流学习

Loj 6002 最小路径覆盖

题解:最小路径覆盖指在一个有向图中,找出最少的路径,使得这些路径经过了所有的点。

最小路径覆盖分为最小不相交路径覆盖和最小可相交路径覆盖。

最小不相交路径覆盖:每一条路径经过的顶点各不相同。如图,其最小路径覆盖数为3。即1>3>4251->3->4,2,5

最小可相交路径覆盖:每一条路径经过的顶点可以相同。如果其最小路径覆盖数为2。即1>3>42>3>51->3->4,2->3->5

莫队算法学习

O(n2S+mS)O(\frac {n^2} {S} + mS)

S=nmS = \frac {n}{\sqrt{m}}时 复杂度最小 即 O(nm)O(n\sqrt{m})

带修改莫队

BZOJ 2122

https://www.lydsy.com/JudgeOnline/problem.php?id=2120

题意:给定nn个数 mm个询问
两种操作:
1、Q L R 计算[L, R]区间不同种类个数
2、R L R 将a[L]改为R

二分图判定

二分图的判定
(参见算法竞赛进阶指南)

定理

一张图是无向图,当且仅当图中不存在奇环

如何判断一张图为无向图

BZOJ 2456

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=2456

给你一个n个数的数列,其中某个数出现了超过n div 2次即众数,请你找出那个数。

CF 1133E

题目链接:https://codeforces.com/contest/1133/problem/E

题解:很显然可以看出dp方程为dp[i][j]=min(dp[i1][j],dp[t][j1]+(it+1))dp[i][j] = \min (dp[i-1][j], dp[t][j-1] + (i - t + 1))
其中设ll为第一个a[l]a[i]5a[l] \geq a[i] - 5的下标。 其中t[l,i]t \in [l, i] 很显然这是个O(n3)O(n ^ 3)

CF 1140C

题目链接:https://codeforces.com/contest/1140/problem/C

题意:题意大概是找出至多kk个人使得(ti)×min(bi)(\sum{t_{i}}) \times min(b_{i}) 最大。

题解:这题刚开始想了优先队列,但是都是往大根堆的方向想,但如果是大根堆,那么每次查询都得是kk次很明显是超时的。不妨转换一下思路,用小根堆。首先我们先将playlist从 bib_{i}从大到小排序。那么遍历的时候,无非遇到这两种情况,

CF 1141F

题目链接: [https://codeforces.com/contest/1141/problem/F2]

题解:很巧妙的一道题,不妨我们枚举出所有的区间,然后用map来处理区间和为kk的所有[l,r][l, r] ,对于所有的kk我们可以将用贪心的思想来求最多不相交区间即可

CF 1141G

题目链接:https://codeforces.com/contest/1141/problem/G

题解:我们不妨考虑每个点的度数indind,那么当k==0k == 0是很显然此时答案应为max(ind[i])max(ind[i]),(类似于抽屉原理的思维),那么当k>0k > 0时 答案很显然为第k+1k + 1大的点的度数。那么我们只需要确定一个答案之后,直接对图染色即可。(染色必然是可行的,在已知答案的情况下)