下载文档原格式
Python中的Hash函数实现方式1.概述Hash函数是计算机科学中十分重要的一个概念，在Python语言中，Hash函数被广泛使用，Python标准库中也包含了一些常用的Hash函数。
本文将从以下几个方面对Python中的Hash函数进行介绍：Hash函数的概念、Hash函数的应用、Hash函数的实现方式以及Hash函数的应用实例等。
2. Hash函数的概念Hash函数，也叫散列函数，是将任意长度的输入（又叫做预映射，pre-image），通过散列算法，变换为固定长度的输出（又叫做散列值，Hash值，message digest）的函数。
Hash函数的特点是输入和输出的类型不一定相同，而且无论输入的数据多少，输出的结果长度是固定的。
Hash函数的设计是为了保证输入数据的机密性、数据完整性以及防止重放攻击等。
在Python中，Hash函数是一个内置函数，它被用于创建Hash对象，Hash函数的格式如下：hash(object)其中，object表示要计算Hash值的对象，可以是数字、字符串、元组、列表、字典等。
3. Hash函数的应用Hash函数在计算机科学中有很多应用，下面简单介绍几个常见的应用：3.1哈希表哈希表是一种数据结构，它通过Hash函数将关键字映射为索引，可以实现快速的数据检索，常见的哈希表有字典（Dictionary）、集合（Set），Python中的字典和集合就是基于哈希表实现的，因为Hash函数可以将输入的键(Key)映射为索引(Hash值)，并将索引与值(Value)组合存储在相应的数据结构中。
在Python中，字典和集合是非常常见的数据结构，它们在实际开发中被广泛使用。
3.2文件完整性验证Hash函数还可以被用于文件完整性验证，比如，我们可以通过计算文件内容的Hash值来判断文件是否被篡改或者被恶意软件所感染，这对于保证文件的安全性具有重要作用。
3.3数字签名数字签名是一种用于确认在不可否认的情况下，数据的来源和完整性的技术。
全国青少年信息学奥林匹克联赛特殊数据结构——并查集龚禹在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。
这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能采用一种全新的抽象的特殊数据结构——并查集来描述。
一、数学准备首先，我们从数学的角度给出等价关系和等价类的定义：定义1：如果集合S中的关系R是自反的，对称的，传递的，则称他为一个等价关系。
——自反：x＝x；——对称：若x＝y，则y＝x；——传递：若x＝y、y＝z，则x＝z。
要求：x、y、z必须要同一个子集中。
定义2：如果R是集合S的等价关系。
对于任何x∈S，由[x]R＝{y|y∈S and xRy}给出的集合[x]R S称为由x∈S生成的一个R的等价类。
定义3：若R是集合S上的一个等价关系，则由这个等价关系可产生这个集合的唯一划分。
即可以按R将S划分为若干不相交的子集S1，S2，S3，S4，……，他们的并即为S，则这些子集Si变称为S的R等价类。
划分等价类的问题的提法是：要求对S作出符合某些等价性条件的等价类的划分，已知集合S及一系列的形如“x等价于y”的具体条件，要求给出S的等价类的划分，符合所列等价性的条件。
（我们上面提到的联系，即可认为是一个等价关系，我们就是要将集合S划分成n个联系的子集，然后再判断x，y是否在一个联系子集中。
）二、引题——亲戚（relation）【问题描述】若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。
部分NOIP基础模块代码总结--by Evan1004一、数据结构1、哈希表procedure hash_a(x:longint);vart:longint;begint:=x mod 399997;if first[t]=0 thenbegininc(tot1);first[t]:=tot1;a[tot1].x:=x;a[tot1].zhi:=0;end elsebegint:=first[t];while (a[t].zhi>0) and (a[t].x<>x) dot:=a[t].zhi;if a[t].zhi=0 thenbegininc(tot1);a[tot1].x:=x;a[tot1].zhi:=0;a[t].zhi:=tot1;end;end;end;2、堆(代码为大根堆操作，小根堆只需将a[i]>a[j]改为a[i]<a[j]即可) 1).插入(上调)procedure up(i);beginwhile i>1 dobeginj:=i div 2;if a[i]>a[j] thenbeginswap(a[i],a[j]);i:=j;endelsebreak;end;end;2).删除(下调)procedurd down(i,n:longint);beginwhile i<=n shr 1 do //因为a[n shr 1]的儿子就是a[n]了beginj:=2*i;if (j+1<=n) and (a[j+1]>a[j]) then //选择两个儿子中的较大者j:=j+1;if a[j]>a[i] thenbeginswap(a[i],a[j]);i:=j;endelsebreak;end;end;3、线段树1.建树procedure start(l,r:longint; var t:longint);varm:longint;beginm:=(l+r) div 2 ;inc(tot);t:=tot;a[t].l:=l;a[t].r:=r;if l<r then beginstart(l,m,a[t].lc);start(m+1,r,a[t].rc);end;end;2.修改区间procedure insert(t,l,r:longint);beginif (a[t].l=l) and (a[t].r=r) thenbegin inc(a[t].data); exit; end;if (r<=a[a[t].lc].r) then insert(a[t].lc,l,r)else if l>=a[a[t].rc].l then insert(a[t].rc,l,r)else begininsert(a[t].lc,l,a[a[t].lc].r);insert(a[t].rc,a[a[t].rc].l,r);end;end;3.修改点procedure insert(t,x:longint);beginif t=0 then exit;if (x=a[t].l) and (x=a[t].r) then begin inc(a[t].data);exit;end;if (x>=a[t].l) and (x<=a[t].r) thenbegininc(a[t].data);insert(a[t].lc,x);insert(a[t].rc,x);end;end;4.查询点procedure find(t,x:longint);beginif t=0 then exit;if (x=a[t].l) and (x=a[t].r) then begin inc(ans,a[t].data); exit;end;if (x>=a[t].l) and (x<=a[t].r) thenbegininc(ans,a[t].data);find(a[t].lc,x);find(a[t].rc,x);end;4.第K小(大)function find(t,x:longint):longint;beginif t=0 then exit;if (a[t].l=a[t].r) then find:=a[t].lelse if a[a[t].lc].data>=x then find:=find(a[t].lc,x)else find:=find(a[t].rc,x-a[a[t].lc].data);5.最大(小)function find(t,x,y:longint):longint;beginif t=0 then exit;if (a[t].l=x) and (a[t].r=y) then exit(a[t].data) elseif y<=a[a[t].lc].r then exit(find(a[t].lc,x,y)) elseif x>=a[a[t].rc].l then exit(find(a[t].rc,x,y)) elseexit(min(find(a[t].lc,x,a[a[t].lc].r),find(a[t].rc,a[a[t].rc].l,y)));end;4、二叉搜索树二叉搜索树procedure insert(var t,x:longint);beginif t=0 thenbegininc(tot);t:=tot;tree[t].x:=x;tree[t].lc:=0;tree[t].rc:=0;tree[t].time:=1;end elsebeginif x>tree[t].x then insert(tree[t].rc,x);if x<tree[t].x then insert(tree[t].lc,x);if x=tree[t].x then inc(tree[t].time);end;end;//======================================================== procedure print(t:longint);beginif t=0 then exit;print(tree[t].lc);writeln(tree[t].x,' ',tree[t].time);print(tree[t].rc);end;二、图论1、最小生成树1.prim算法procedure prim;vari,j,min,minj:longint;beginv[1]:=0;for i:=1 to n dobeginmin:=maxlongint;for j:=1 to n doif (b[j]=0) and (v[j]<min) thenbeginmin:=v[j];minj:=j;end;sum:=sum+min;b[minj]:=1;for j:=1 to n doif (b[j]=0)and(a[minj,j]>0)and(v[j]>a[minj,j]) thenv[j]:=a[minj,j];end;writeln(sum);end;2.Kruskal算法(算法过程较多，引一道纯最小生成树题举例)constmaxn=1000000;vari,j,k,m,n,p,q,x,y:longint;f,u,v:array[1..maxn] of longint; ans,s:extended;e:array[1..maxn] of real; procedure swap(var x,y:longint); vart:longint;begint:=x;x:=y;y:=t;end;procedure qsort(l,r:longint);vari,j:longint;x,y:extended;begini:=l;j:=r;x:=e[random(r-l)+l];repeatwhile e[i]<x do inc(i);while e[j]>x do dec(j);if i<=j thenbeginy:=e[i];e[i]:=e[j];e[j]:=y;swap(u[i],u[j]);swap(v[i],v[j]);inc(i);dec(j);end;until i>j;if l<j then qs(l,j);if i<r then qs(i,r);end;function get(x:longint):longint; beginif f[x]=0 then exit(x);if f[f[x]]=0 then exit(f[x]);f[x]:=get(f[x]);exit(f[x]);end;procedure init;beginfillchar(e,sizeof(e),0);fillchar(u,sizeof(u),0);fillchar(v,sizeof(v),0);fillchar(f,sizeof(f),0);readln(s);readln(n);m:=0;while not eof dobegininc(m);readln(u[m],v[m],e[m]);end;end;procedure outit;beginif (k=n-1) and (ans<=s) thenwriteln('Need ',ans:0:2,' miles of cable') elsewriteln('Impossible');end;begininit;qsort(1,m);// Kurskalk:=0;for i:=1 to m dobeginp:=get(u[i]);q:=get(v[i]);if p<>q thenbeginans:=ans+e[i];f[p]:=q;inc(k);end;end;outit;end.2、最短路问题1.Floyd (简单，但是雷达不动的o(n3)...)for k:=1 to 52 dofor i:=1 to 52 dofor j:=1 to 52 doif a[i,k]+a[k,j]<a[i,j] thena[i,j]:=a[i,k]+a[k,j];2.Dijkstraprocedure Dijkstra;vari,j,p:integer;min:longint;beginp:=0;fillchar(v,sizeof(v),100);fillchar(b,sizeof(b),false);v[m]:=0;for i:= 1 to n dobeginmin:=maxlongint;for j:= 1 to n doif (min>v[j])and(not b[j]) thenbeginmin:=v[j];p:=j;end;b[p]:=true;for j:= 1 to n doif (not b[j])and(v[j]>a[p,j]+v[p]) thenv[j]:=a[p,j]+v[p];end;for i:= 1 to n dowriteln(v[i]);end;3.SPFAprocedure spfa;beginfillchar(q,sizeof(q),0); h:=0; t:=0;//队列fillchar(b,sizeof(b),false);//b[i]判断i是否在队列中for i:=1 to n dov[i]:=maxint;//初始化最小值inc(t);q[t]:=1;b[1]:=true;v[1]:=0;//这里把1作为源点while h<>t dobeginh:=(h mod n)+1;x:=q[h];b[x]:=false;for i:=1 to n doif (a[x,i]>0) and (v[x]+a[x,i]<v[i]) thenbeginv[i]:=v[x]+a[x,i];if not(b[i]) thenbegint:=(t mod n)+1;q[t]:=i;b[i]:=true;end;end;end;end;三、不知道分什么类1、最大公约数：function gcd(n,m:longint):longint;beginif m=0 then exit(n);gcd:=gcd(m,n mod m);end;2、最小公倍数：lcm(n,m)：=n*m/gcd(n,m) //先除再乘，不然超LONGINT了3、快速排序procedure qsort(l,r:longint);vari,j,k,mid:longint;begini:=l;j:=r;mid:=a[(l+r) shr 1];repeatwhile a[i]<mid do inc(i);while a[j]>mid do dec(j);if i<=j thenbegink:=a[i]; a[i]:=a[j];a[j]:=k;inc(i);dec(j);end;until i>j;if i<r then qsort(i,r);if l<j then qsort(l,j);end;4、并查集1.判断是否在同一并查集内function get(x:longint):longint; beginif f[x]=x then exit(x) elsebeginf[x]:=get(f[x]); \\捎带路径压缩exit(f[x]);end;end;2.合并procedure union(x,y:longint); beginif get(x)<>get(y) thenf[get(x)]:=get(y);end;深搜的基本框架procedure search;varif 结束条件1 thenbeginif 结束条件2 then inc(ans);exit;end;{ 计算、操作}for i:=1 to n do //n为搜索宽度search(n);end;。
python中哈希表用法哈希表是Python中常用的数据结构之一，它可以用来存储和查询大量的键值对数据。
本文将介绍哈希表在Python中的基本用法和一些常见的应用场景。
首先，我们需要了解哈希表的概念。
哈希表其实是一个数组，每个元素都是一个键值对的集合。
在哈希表中，每个键都通过哈希函数转换成一个索引，然后该键值对将被存储在索引对应的位置上。
这样，当我们需要查询某个键的时候，可以直接通过哈希函数计算出它的索引，并在对应位置上找到对应的值，从而实现快速的查询。
在Python中，内置的哈希表实现是字典(dict)。
字典是一种可变、无序的键值对集合，非常适合存储和查询数据。
接下来，我们将详细介绍哈希表在Python中的用法。
1. 创建哈希表在Python中，可以使用大括号{}或者内置的dict()函数来创建一个哈希表。
例如：```pythonhash_table = {}hash_table = dict()```创建一个空的哈希表。
2. 添加键值对可以使用赋值运算符=来向哈希表中添加键值对。
例如：```pythonhash_table["name"] = "Alice"hash_table["age"] = 25```上述代码向哈希表中添加了键"name"和"age"，并分别对应值"Alice"和25。
3. 查询键值对可以使用键来查询对应的值。
例如：```pythonname = hash_table["name"]age = hash_table["age"]```上述代码通过键"name"和"age"查询到了对应的值。
4. 修改键值对可以通过赋值运算符=修改哈希表中的键值对。
例如：```pythonhash_table["name"] = "Bob"```上述代码将键"name"对应的值修改为"Bob"。
哈希数据结构哈希（Hash）数据结构是一种常用的数据结构，它在计算机科学领域被广泛应用。
哈希数据结构的主要特点是能够快速地进行数据查找和插入操作，具有高效的时间复杂度。
一、哈希数据结构的定义和原理哈希数据结构是一种将数据元素与索引值建立映射关系的数据结构。
它通过将数据元素经过哈希函数的计算得到对应的索引值，从而将数据元素存储在数组中的相应位置。
在哈希数据结构中，哈希函数起到了关键的作用，它能够将任意大小的数据映射为固定大小的索引值。
常见的哈希函数有散列函数、MD5、SHA等。
二、哈希数据结构的应用1. 数据存储和检索：哈希数据结构可以将数据元素按照一定的规则进行存储，从而实现快速的数据检索。
例如，在散列表中，通过哈希函数将关键字映射为索引值，就可以快速地找到对应的数据。
2. 缓存管理：哈希数据结构可以用于缓存管理，可以将频繁访问的数据存储在哈希表中，以提高数据的访问速度。
例如，在操作系统中，页面置换算法中的最近最少使用（LRU）算法就可以使用哈希表来实现。
3. 数据完整性校验：哈希数据结构可以用于数据完整性校验，通过对数据进行哈希运算，得到一个唯一的哈希值，用于校验数据是否被篡改。
例如，在文件传输过程中，可以对文件进行哈希运算，将哈希值与接收到的文件进行比较，以确保文件的完整性。
4. 密码存储：哈希数据结构可以用于密码存储，通过将密码进行哈希运算，将哈希值存储在数据库中，可以提高密码的安全性。
例如，在用户注册过程中，可以对用户密码进行哈希运算，将哈希值存储在数据库中，而不是明文存储用户密码。
三、常见的哈希数据结构1. 散列表（Hash Table）：散列表是一种以键值对形式存储数据的数据结构，它使用哈希函数将关键字映射为索引值，将数据存储在数组中的相应位置。
散列表具有快速的查找和插入操作的特点，广泛应用于各种编程语言中。
2. 哈希集合（Hash Set）：哈希集合是一种集合数据结构，它使用哈希函数将元素映射为索引值，将元素存储在数组中的相应位置。
NOIP《数据结构》练习题及答案NOIP《数据结构》练习题及答案数据结构是计算机科学中非常重要的一个概念，它指的是组织和存储数据的方式。
在NOIP（全国青少年信息学奥林匹克竞赛）中，数据结构是一个常见的考题类型。
本文将介绍一些NOIP中关于数据结构的练习题，并给出相应的答案。
一、题目1给定一个整数数组nums和一个目标值target，在数组中找出和为目标值的两个整数，并返回它们的索引。
示例：输入：nums = [2, 7, 11, 15], target = 9输出：[0, 1]解释：nums[0] + nums[1] = 2 + 7 = 9，所以返回[0, 1]。
解答：这道题可以使用哈希表来解决。
我们可以遍历数组中的每个元素，将其与目标值的差值存储在哈希表中。
如果下一个元素在哈希表中存在，那么就找到了和为目标值的两个数。
代码实现：```pythondef twoSum(nums, target):hashmap = {}for i in range(len(nums)):complement = target - nums[i]if complement in hashmap:return [hashmap[complement], i]hashmap[nums[i]] = i```二、题目2给定一个字符串s，找到字符串中最长的回文子串。
假设字符串s 的最大长度为1000。
示例：输入："babad"输出："bab"解释："bab"是最长的回文子串，因为它从左至右读和从右至左读是相同的。
解答：这是一个动态规划的问题。
我们可以定义一个二维数组dp，其中dp[i][j]表示字符串s从索引i到索引j是否是回文串。
初始时，所有长度为1的子串都是回文串。
然后我们遍历所有长度大于1的子串，如果子串的两端相等且除去两端的子串也是回文串，则该子串也是回文串。
python哈希查找算法# Python哈希查找算法：快速访问数据的秘诀在Python编程中，哈希查找是一种非常高效的查找方法。
这种方法利用了散列函数（也称为哈希函数）将数据转换成唯一的索引值，并将这些数据存储在一个叫做哈希表的数据结构中。
当你需要查找某个特定的数据时，只需要再次使用相同的散列函数来计算它的索引值，然后直接去哈希表中找到对应的项即可。
这就是为什么哈希查找如此快速的原因。
1. 散列函数：从数据到索引首先，我们来看一下散列函数的工作原理。
散列函数可以接受任何类型的数据作为输入，包括字符串、整数和浮点数等。
它的任务是将这些输入转换为一个固定的长度的数字，这个数字通常被称为哈希值或者索引值。
举个例子，假设我们有一个简单的散列函数，它接受一个字符串作为输入，并返回该字符串的长度。
那么，如果我们用这个函数来处理字符串"hello"，结果就是5。
对于字符串"world"，结果则是5。
注意，不同的输入可能会得到相同的输出，这种现象被称为哈希碰撞。
当然，在实际应用中，我们会选择更复杂的散列函数，以减少哈希碰撞的可能性。
例如，Python内置的hash()函数就是一个很好的选择。
它能够生成一个唯一的哈希值，用于标识任何不可变类型的数据。
pythonprint(hash("hello")) # 输出：-309472816print(hash("world")) # 输出：-15276294052. 哈希表：数据的高效存储现在，我们已经知道了如何通过散列函数将数据转换为索引值。
接下来的问题是如何存储这些数据。
这里，我们需要引入一个新的数据结构——哈希表。
哈希表是一个键值对的集合，其中每个键都是由散列函数生成的索引值，而每个值则是对应的数据项。
由于索引值是唯一的，因此我们可以直接通过索引来查找数据，无需像在列表或数组中那样遍历所有元素。
数据结构--哈希表 在哈希表这种数据结构中，使⽤将在 5-3 节讲解的“哈希函数”，可以使数据的查询效率得到显著提升。
哈希表存储的是由键（key）和值（value）组成的数据。
例如，我们将每个⼈的性别作为数据进⾏存储，键为⼈名，值为对应的性别。
为了和哈希表进⾏对⽐，我们先将这些数据存储在数组中 此处准备了 6 个箱⼦（即长度为 6 的数组）来存储数据。
假设我们需要查询Ally的性别，由于不知道Ally的数据存储在哪个箱⼦⾥，所以只能从头开始查询。
这个操作便叫作“线性查找” 查找到4号箱⼦的时候，发现其中数据的键为Ally。
把键对应的值取出，我们就知道 Ally 的性别为⼥（F）了。
数据量越多，线性查找耗费的时间就越长。
由此可知：由于数据的查询较为耗时，所以此处并不适合使⽤数组来存储数据。
但使⽤哈希表便可以解决这个问题。
⾸先准备好数组，这次我们⽤5个箱⼦的数组来存储数据。
使⽤哈希函数（Hash）计算 Joe 的键，也就是字符串“Joe”的哈希值。
得到的结果为4928 将得到的哈希值除以数组的长度5，求得其余数。
这样的求余运算叫作“mod 运算”。
此处mod运算的结果为3。
因此，我们将Joe的数据存进数组的3号箱⼦中。
重复前⾯的操作，将其他数据也存进数组中。
Nell键的哈希值为6276，mod 5的结果为1。
本应将其存进数组的1号箱中，但此时1号箱中已经存储了 Sue 的数据。
这种存储位置重复了的情况便叫作“冲突” 遇到这种情况，可使⽤链表在已有数据的后⾯继续存储新的数据。
Ally键的哈希值为9143，mod 5的结果为3。
本应将其存储在数组的3号箱中，但3号箱中已经有了Joe的数据，所以使⽤链表，在其后⾯存储Ally的数据。
解说 在哈希表中，我们可以利⽤哈希函数快速访问到数组中的⽬标数据。
如果发⽣哈希冲突，就使⽤链表进⾏存储。
这样⼀来，不管数据量为多少，我们都能够灵活应对。
如果数组的空间太⼩，使⽤哈希表的时候就容易发⽣冲突，线性查找的使⽤频率也会更⾼；反过来，如果数组的空间太⼤，就会出现很多空箱⼦，造成内存的浪费。
下图是他们在平均以及最差情况下的时间复杂度：哈希表就是一种以键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即key，即可查找到其对应的值。
哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。
这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。
使用哈希查找有两个步骤:1.使用哈希函数将被查找的键转换为数组的索引。
在理想的情况下，不同的键会被转换为不同的索引值，但是在有些情况下我们需要处理多个键被哈希到同一个索引值的情况。
所以哈希查找的第二个步骤就是处理冲突2.处理哈希碰撞冲突。
有很多处理哈希碰撞冲突的方法，本文后面会介绍拉链法和线性探测法。
哈希表是一个在时间和空间上做出权衡的经典例子。
如果没有内存限制，那么可以直接将键作为数组的索引。
那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。
哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。
只需要调整哈希函数算法即可在时间和空间上做出取舍。
哈希查找第一步就是使用哈希函数将键映射成索引。
这种映射函数就是哈希函数。
如果我们有一个保存0-M数组，那么我们就需要一个能够将任意键转换为该数组范围内的索引（0~M-1）的哈希函数。
哈希函数需要易于计算并且能够均匀分布所有键。
比如举个简单的例子，使用手机号码后三位就比前三位作为key更好，因为前三位手机号码的重复率很高。
再比如使用身份证号码出生年月位数要比使用前几位数要更好。
在实际中，我们的键并不都是数字，有可能是字符串，还有可能是几个值的组合等，所以我们需要实现自己的哈希函数。
获取正整数哈希值最常用的方法是使用除留余数法。
即对于大小为素数M的数组，对于任意正整数k，计算k除以M的余数。
M一般取素数。
将字符串作为键的时候，我们也可以将他作为一个大的整数，采用保留除余法。
Noi数据结构知识点0. 算法的时空分析0.1 时间分析0.2 空间分析0.3 时空分配1. 基础算法1.1 枚举1.2 模拟1.3 递推1.4 贪心1.5 递归1.6 分治2. 排序算法2.1 冒泡排序2.2 选择排序2.3 桶排序2.4 插入排序2.5 归并排序2.6 快速排序2.7 堆排序2.8 二叉排序树3. 查找算法3.1 顺序查找3.2 二分查找3.3 二分答案4. 搜索算法4.1 BFS和DFS4.2 简单剪枝4.3 记忆化搜索5. 动态规划5.1 动态规划初步5.2 背包问题5.3 最大(小)代价子母树6. 排列组合6.1 基本概念6.2 二项式定理6.3 康托展开6.4 袋与球问题7. 数论7.1 素数判断7.2 最大公约数7.3 扩展欧几里德7.4 不定方程7.5 几类数列7.6 数的进制8. 线性表8.1 数组和向量8.2 堆栈8.3 队列8.4 字符串9. 图9.1 图的遍历和拓扑排序9.1.1 图的遍历9.1.2 拓扑排序9.2 最短路9.2.1 Floyd算法9.2.2 Dijstra算法9.2.3 Bellman-Ford算法9.2.4 SPFA算法9.3 生成树9.3.1 Prim算法9.3.2 Kruskal算法9.4 圈和块9.4.1 最小环9.4.2 负权环9.4.3 连通块10. 树10.1 树的遍历10.2 树上距离问题10.2.1 节点到根的距离10.2.2 最近公共祖先10.2.3 节点间的距离10.2.4 树的直径10.3 哈夫曼树10.4 二叉堆10.5 树形动态规划10.6 二叉排序树10.7 并查集11. HASH11.1 ELFhash11.2 SDBM11.3 BKDR11.4 RK12. 数论12.1 矩阵乘法12.2 高斯消元12.3 异或方程组13. 动态规划13.1 多维状态动态规划13.2 状态压缩动态规划13.2.1 递推13.2.2 基于连通性13.3 动态规划优化13.3.1 降低维度13.3.2 优先队列13.3.3 单调队列13.3.4 矩阵加速13.3.5 斜率优化13.3.6 四边形不等式14. 二分图14.1 最大匹配14.1.1 匈牙利算法14.1.2 最大流算法14.1.3 覆盖集和独立集14.1.4 非二分图最大匹配14.2 带权二分图匹配14.2.1 KM算法14.2.2 费用流算法15. 网络流15.1 网络流初步15.2 最大流15.2.1 Dinic算法15.2.2 Sap算法15.2.3 有上下界的最大流15.3 最小割15.3.1 最小割15.3.2 平面图最小割15.3.3 闭合图15.3.4 最小点权覆盖集与最大点权独立集15.3.5 0/1分数规划15.3.6 最大密度子图15.4 费用流15.4.1 最短路增广费用流15.4.2 zkw-费用流15.4.3 最小费用可行流16. 图和树16.1 路径问题16.1.1 K短路16.1.2 差分约束系统16.2 生成树16.2.1 生成树的另类算法16.2.2 次小生成树16.2.3 特殊生成树16.3 2-SAT16.4 线段树16.5 平衡树16.5.1 Treap16.5.2 Splay16.6 LCA与RMQ16.7 树状数组17. 字符串17.1 Trie17.2 KMP及扩展17.3 后缀数组18. 选学内容18.1 启发式搜索18.2 跳舞链18.3 随机调整与随机贪心18.4 爬山法与模拟退火18.5 博弈论18.6 动态树18.6.1 树链剖分18.6.2 Link-Cut Tree 18.7 计算几何18.8 DFT和FFT。
