zcmimi's blog
avatar
zcmimi
2019-12-01

划分dp

题意

每组输入是两个整数nk(1\le n \le 50, 1 \le k \le n)

输出

对于输入的n,k;

第一行: 将n划分成若干正整数之和的方案数。

第二行: 将n划分成k个正整数之和的方案数。

第三行: 将n划分成最大

avatar
zcmimi
2019-12-01

容斥

容斥原理

  • 求具有n个属性之一(并集)的元素的个数

  • 求不具有n个属性中任何一个(交集)的元素的个数

两个集合的并集

|A \bigcup B| = |A|+|B|-|A \bigcap B|

三个集合的并集

$ \begin{aligned

avatar
zcmimi
2019-11-17 21:26:25

赛后总结

其实感觉这次打的失误挺多的。

day1:

  1. t1其实就是个二分或者递归模拟一下就好了(2^{64}要特判一下)
  2. t2看到是括号序列这样的套路也还可以接受,就是每个点的答案就是父节点的答案加上它自己的贡献(以它结尾的合法子串有多少个),(早知道还是循规蹈矩写
avatar
zcmimi
2019-11-11

静态链分治用于解决静态树上众数问题,比如Codeforces\ 600E

静态链分治是离线算法,有点像莫队,复杂度\Theta (n \log n \log n)

比如说遍历一遍子树可以得出答案,但是每棵子树

avatar
zcmimi
2019-11-01

点分治

点分治用于大规模处理树上路径

树的重心

树的最大子树最小的点

性质:每一个子树的大小都不超过\frac n2

```cpp int rt,mxs=inf,siz[N];// 当前 根,最大子树大小 void frt(int x,int f){ siz[x]=1

avatar
zcmimi
2019-10-20

Lucas定理

C_n^m\pmod p\equiv C_{n\mod p}^{m\mod p}*C_{\lfloor n/p\rfloor}^{\lfloor m/p\rfloor}\pmod p

就是一个组合数可以拆成P进制下的乘积

这个算法可以处理当m,n非常大的时

前置知识: 莫队算法(Mo's Algorithm)

树上莫队:

也就是把莫队搬到树上

入手模板: SP10707 COT2 - Count on a tree II

给定一个n个节点的树,每个

avatar
zcmimi
2019-03-06 00:03:14

题目地址:

网络流24题真的好有质量~\ (\ge \le ) /~!

进度: $\frac

avatar
zcmimi
2019-02-08 18:15:39

| A | Parity standard input/output1 s, 256 MB | [![Sub

avatar
zcmimi
2019-01-30

建树

tarjan求出双连通分量后把其中的点连向新建的节点

建成的新图(树)即为圆方树

**性质:可

7/74
Search
search