CODEPLAY0314

概述说起来，链表是少数几个在正式学习之前就有点概念的数据结构。记得很久很久之前有一题，貌似是要插入什么，当时是用线段树(?)解决了问题，但是想，为什么数组之间插入元素这么不方便呢？然后就想到可以自己做个结构体用指针接起来，这样插入就可以O(1)实现了！后来知道这就是链表。再后来知道，这样插入也是非常不支持的，因为找到插入的位置也是O(n)的。又后来，学会了数组模拟链表，可以快速找到插入位置。然后就是一个非常兹磁的东西了！其实很多时候都是用于优化，程序的主算法都不会改变的。下面是一些例题：例题 [BZOJ 1098] 办公楼biu [Description] 求一个n点m边的无向图补图的连通块数。 [Hint] n≤105,m≤2⋅106n≤10^5,m≤2⋅10^6n≤105,m≤2⋅106 [Solution] 直接建补图肯定是爆炸的。考虑某个点，不与它相邻的点在补图中肯定跟它位于同一个连通块。与这些点不相连的所有点肯定也与这些点位于同一个连通块。这样，可以一次把一个连通块里的所有点找出来。删除后找下一个连通块。提高效率的办法就是用链表。永远都只考虑链表 ...

算法 | 矩阵乘法和高斯消元

Created2015-09-07|OI&ACM

高斯消元这个坑竟然现在才来补… 感觉这两个东西放在一起有一点点强行（雾矩阵乘法 - matrix 概述概念什么的不用多说，n×m的矩阵乘m×q的矩阵=n×q的矩阵，c[i][j]=∑i,j,k(a[i][k]×b[k][j])c[i][j]=\sum_{i,j,k}(a[i][k]×b[k][j])c[i][j]=∑i,j,k(a[i][k]×b[k][j])，大概就这样… 实现上O(n3)O(n^3)O(n3)已足够。例题 [UVa 10870] Recurrences [Description] 有f(n)=a1×f(n−1)+a2×f(n−2)…ad×f(n−d)f(n)=a_1×f(n−1)+a_2×f(n−2)…a_d×f(n−d)f(n)=a1×f(n−1)+a2×f(n−2)…ad×f(n−d)，给定d,a1 ad,f(1) f(d)d,a_1~a_d,f(1)~f(d)d,a1 ad,f(1) f(d)，求f(n)f(n)f(n)，答案对mmm取模。 [Hint] n＜231,d<16,m<46340n＜2^{31},d<16,m& ...