Ⅰ. 快速沃尔什变换认知
这东西英文名叫$Fast Walsh$-$Hadamard Transform$
$FWT$是用来快速计算位运算卷积的，至于什么是卷积，可以先学习一下$FFT$
FFT小结，点击链接
既然提到了位运算，必然要和子集扯上关系，也就是说可以来求子集卷积
Read more
TaoSama
Sep 10, 2016
Ⅰ. 高斯消元认知
$这东西英文名叫Gaussian Elimination$
$高斯消元对矩阵进行操作，对满足一定运算规律的方程利用矩阵初等变换进行消元$
$主要用来求解线性方程组、矩阵的秩、以及可逆方阵的逆矩阵$
$还可以用来线性空间的基向量，比如线性基（线性无关的极大子集）$
$PS:关于线性相关，具体可以读2014集训队论文《浅谈线性相关》$
Read more
TaoSama
Aug 05, 2016
Ⅰ. 背包问题认知
$物品：不可拆分，具有三种属性(体积w_i, 价值v_i, 个数c_i)$
$背包问题：将物品装入V大小的背包获得最优价值的问题$
$c_i=1时，称为01背包$
$c_i=\infty 时，称为完全背包$
$c_i=不定值时，称为多重背包$
Read more
TaoSama
May 18, 2016
Ⅰ. 斜率优化认知
这东西英文名叫$Convex Hull Trick (CHT)$
主要优化形如$f_i = min\{ f_j + cost(j+1, i) \}的这种dp$
由于等号右边的式子并不能$O(1)$计算，所以我们需要一些技巧来优化
Read more
TaoSama
May 11, 2016
$1. 递归时隐藏的修改了全局变量例如点分治重心$ $\to 每次复制一遍$$2. 测试数据时未将空间开到题目要求, 隐藏的空间倍数关系例如无向图2倍$ $\to RE$$3. 除数是个减法式子$ $整数\to RE 浮点数\to WA \to 特判$$4. 离线并查集的重复操作$ $\to 只有第一次才需要unite$$5. 回溯暴搜的复杂度是阶乘级或者指数级$ $\to 看到正常数据的题再爆搜就可以去死了$$6. 乘法取模, a \times b$ $\to a \% MOD \times (b\%MOD)\%MOD $$7. two pointers的时候，相等时移动指针$ $\to 小心重复数据，死循环死你啊$$8. 利用欧拉定理降幂的时候x^n\% MOD，特判x\% MOD == 0$ $\to 此时答案是0啊$
Read more
TaoSama
May 02, 2016