ACM中的数据结构

1、 南阳理工学院 ACM集训队基础：队列、堆栈排序与检索：快速排序和归并排序的思想串的模式匹配：KMP, Trie(*)，AC自动机后缀树，后缀数组树：哈夫曼树，树状数组，线段树，(各种树)。字典：Hash、并查集(*)、可并优先队列，堆串的模式匹配串的模式匹配-KMP-KMP串的模式匹配串的模式匹配-KMP-KMP Trie结构 基于关键码分解的数据结构，叫作Trie结构 “trie”这个词来源于“retrieval” 主要应用 信息检索 用来存储英文字符串，尤其大规模的英文词典 自然语言理解系统中经常用到TrieTrie结构应用字典树存储字典里面的单词英文的单词是有26个字母组成的（简单起见

2、，我们忽略大小写） 英文字符树每一个内部结点都有26个子结点 树的高度为最长字符串长度字典树字典树 trietrie由于单词可能不等长，所以更好的存储是其内部结点不存储单词信息，只有叶结点才存储单词信息字典树中的检索首先用待查关键码的第一个字符与树林的各个根的字符相比较，然后下一步的检索在前次比较相等的那棵树上进行其中，用待查关键码的第二个字符与选定的这棵树的根的各个子结点进行比较，接着再沿着前次比较相等的分支进行进一步的检索，.，直到进行到某一层，该层所有结点的字符都与待查关键码相应位置的字符不同，这说明此关键码在树目录里没有出现；若检索一直进行到树叶，那么就在树目录里找到了给定的关键码Tr

3、ieTrie树的插入树的插入首先根据插入纪录的关键码找到需要插入的结点位置如果该结点是叶结点，那么就将为其分裂出两个子结点，分别存储这个纪录和以前的那个纪录如果是内部结点，则在那个分支上应该是空的，所以直接为该分支建立一个新的叶结点即可TrieTrie树的删除树的删除根据插入纪录的关键码找到需要删除的结点位置如果一个被删除结点的父结点没有其他的儿子，那么就需要合并否则只需要将此分支设置为空即可算法实现算法实现链接：http:/ 61 2 3 4 5QUERY 1 3ADD 1 2QUERY 1 3ADD 2 3QUERY 1 2QUERY 1 5样例输出样例输出68820链接：http:/ y

4、2)，并且将矩阵中的数字全部取反（原来是1现在变成0，原来是0现在变成1）,还可以每次查询第x行第y列的格子中的数字是什么。T 100,N 1000 , Q 50000.输入输入Line1：给出一个T，表示组数Line2:给出两个数N，Q.矩阵大小，询问次数Line：3.3+Q: 输入C，则后又四个数(x1,y1),(x2,y2)输入Q，则后两个数(x,y)输出输出每次询问输出查询结果。样例输入样例输入12 10C 2 1 2 2Q 2 2C 2 1 2 1Q 1 1C 1 1 2 1C 1 2 1 2C 1 1 2 2Q 1 1C 1 1 2 1Q 2 1样例输出样例输出1001线段树是一种

5、二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。对于线段树中的每一个非叶子节点a,b，它的左儿子表示的区间为a,(a+b)/2，右儿子表示的区间为(a+b)/2+1,b。因此线段树是平衡二叉树，最后的子节点数目为N，即整个线段区间的长度。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN）。而未优化的空间复杂度为2N，因此有时需要离散化让空间压缩。参考论文： 数据结构的选择与算法效率 从IOI98试题PICTURE谈起线段树解决的基础问题线段树解决的基础问题1.数组数组能解决的所有问题（插点问线、插线问点、逆序数

6、、第k大等）2.插线问线（lazy标记）3.各种区间更改、查询问题练习练习链接：http:/ A a b c 表示给区间a到b内每个数都加上c；2. S a b 表示输出区间a到b内的和；3. Q a b 表示输出区间a到b内的奇数的个数；接下来有M（1=M= rankb) if (ranka = rankb) fatherb = a; fatherb = a; ranka += rankb; ranka += rankb; else else fathera = b; fathera = b; rankb += ranka; rankb += ranka; 链接：http:/ K 表示有多少

7、组测试数据。 接下来对每组测试数据：第1行: N M第2M+1行： Xi Yi Vi (i=1,.,M)表示神经元Xi 到神经元Yi之间通道的速度必须是Vi最后一行： S T ( S T )【约束条件】2K5 1N500 0M5000 1 Xi, Yi , S , T N 0 Vi 30000，Vi是整数。数据之间有一个空格。输出输出对于每组测试数据，输出一行：如果神经元S到神经元T没有路线，输出“IMPOSSIBLE”。否则输出一个数，表示最小的速度比。如果需要，输出一个既约分数。样例输入样例输入23 21 2 22 3 41 33 31 2 101 2 52 3 81 3样例输出样例输出2

8、5/4题目分析题目分析 枚举速度最大的边，找出能够从S到达T的最大速度，然后求出它们的比值，与已经求出的比值进行比较，如果比之前的比值小，则更新比值，记录此种情况下的最大速度和最小速度，直到枚举到从S不能到达T，跳出循环。求出最大速度和最小速度的比值即可。如果从S可以到达T，说明S和T属于同一个集合，因此可以利用并查集来判断从S是否可以到达T。make_heap(a,a+n,cmp) 默认是最大堆化，即cmp为真时a做叶子pop_heap(a,a+n,cmp) 将堆顶元素移至an-1且a0:n-2仍为堆push_heap(a,a+n,cmp) 将an-1加入堆a0:n-2sort_heap(a,a+n,cmp) 将堆an-1化为排序好的数组an-1bool cmp(int x,int y) return xy; /最大堆 a0为堆顶元素。练习练习链接：http:/ 100组）每组测试数据第一行有两个数n（n = 1000）和m（1 =m = n）第二行有n个数，分别代表每颗树上枇杷果的数量输出输出输出小Y同学所花费的最小的力气，每个结果占一行。样例输入