最长公共子序列 ！这篇笔记还不完整 洛谷的模板 做法（只适用两个串为1~n全排列 ) 给a串定义一个映射f,满足f(a[i])=i 对b串执行操作b[i]=f(b[i]) 最长公共子序列长度=b中最长上升子序列

左偏树 这篇笔记尚不完整。 使用队列的左偏树 注意：叶节点dis=-1,单儿子节点dis=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107

一些零散的整理 划分数问题 推荐阅读 整理的很全面。 斜率优化 JSOI2009集训队论文

动态树（Link-Cut Tree） 增删无权边+询问连通性 略 增删无权边+询问到根路径长度 例题:bzoj2002 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96

动态规划——状态压缩 描述 将状态用二进制表示，直接使用数组下标。 例题：hdu3311 斯坦纳树+SPFA+状压DP。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94

四分树 例题:uva297 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 /* uva297 the std is wrong, str should be larger */ #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> using namespace std; int t; const int maxa=33; const int maxn=1033; char s[maxn*maxn]; bool pic[maxa][maxa]; int cnt; void draw(char* s,int& pos,int x,int y,int a) { ++pos; if(s[pos]=='p') { draw(s,pos,x,y+a/2,a/2); draw(s,pos,x,y,a/2); draw(s,pos,x+a/2,y,a/2); draw(s,pos,x+a/2,y+a/2,a/2); } else if(s[pos]=='f') { for(int i=x;i<=x+a-1;++i) for(int j=y;j<=y+a-1;++j) if(!pic[i][j]) pic[i][j]=true,++cnt; } } int main() { freopen("uva297_2.in","r",stdin); freopen("uva297.out","w",stdout); for(scanf("%d\n",&t);t;--t) { memset(pic,0,sizeof(pic)); cnt=0; for(int i=1;i<=2;++i) { scanf("%s",s); int p=-1; draw(s,p,1,1,32); } printf("There are %d black pixels.\n",cnt); } return 0; }

Prufer序列 概念 略 Cayley定理 不同的n节点标号树的数量为n^(n-2) 性质 prufer序列中某个编号出现的次数+1 Prufer转树 例题：poj2568 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71

最近公共祖先（LCA） Tarjan算法 详见Tarjan——强连通分量&最近公共祖先（LCA） 倍增算法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96

莫队算法 普通莫队 例题：bzoj2038 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 /* bzoj2038 */ #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; template<typename T> void read(T& w) { char r;int f=1; for(r=getchar();r!='-'&&(r<48||r>57);r=getchar());

快速傅里叶变换 多项式乘法 例题：luogu3803 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 /* luogu3803 FFT */ #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> using namespace std; template<typename T> void read(T& w)