研究 – 数据结构及其应用 (1)
September 22nd, 2008
1 comment
呵呵，最近很忙啊，大家可以看看我的上一篇文章。 Well, I think the first step of doing anything you wanna do is to believe in yourself, and believe in it, just like “Forrest Gump” shows, no matter how “unwise” you are, there will always be a way to sucess, you’ve just got to believe in it. 有点像新东方的校训啊，“追求卓越，挑战极限，从绝望中寻找希望，人生终将辉煌！”，这个在这段时期也成为了我的座右铭。
至于我为什么要这么“贯彻”新东方 Spirit 。呃，这又是一个励志典故啊，今天先来谈谈我这段时间钻研的 OI 内容。
罗TW同学在周日给我们讲了有关数据结构的应用的专题，主要是讲题，也是为了镇镇我们，我就弄到了PPT，在这里做简述。
PPT（ .PPTX File Under PowerPoint 2007 ）在这里下载。
数据结构在简单的就是线性结构，其中栈又是相当有用的一部分。
栈的主要应用是深搜。这里弄一道只用了栈的性质而实际上是很巧妙的递归的题目：
•有n个栈，标号为1~n，栈大小分别为s[1]~s[n]，全为空栈。•将数字1，2，3，4，5…依次加入第一个栈•如果第i个栈满了，将这一个栈的元素依次出栈，加入第i+1个栈，之后将第1~i个栈改为空栈。如果第n个栈满了，求第n个栈第x个元素到第y个元素的和(1<=x<=y<=s[n])，否则再将数字1，2，3，4，5…依次加入第一个栈。•N<=1000；s[i]<=longint；数组组数≈1000；时限5s来源：ZJU 2962 Stack by Stack
这道题目实际上由不断的递归实现，当然，在递归的同时，可以做一点小小的冗余计算优化。
这里还给一道例题：
•给定n(n<=1000000)个区间[ai,bi]，事先按ai由小到大排序。满足0<=ai<bi<=100000000。每个区间表示的范围是ai到bi范围内的连续的整数。•请你找到一个整数集合Z，使得：
1、|Z|最小。即集合z内的整数个数最小。
2、z∩[ai，bi]>=2。 即z和每个集合至少有2个相交的不同整数。
这实际上要用队列实现：读入ai，bi，加入队列，判断对我目前的Z是否符合条件，如不符合，则做小调整（自己想啦，其实就是做两个指针来标Z的范围，若这个ai比b[i-1]小则……，反之则……）很典型的O(n)题目，维护指针。
另外的线性结构就是字符串了，kmp和扩展kmp自己查查资料啊。
还有就是树形结构了，主要有一个并查集：
并查集•实现：数组记录父亲•作用：合并集合；判断一个元素是否在集合内；
•核心操作：路径压缩。•扩展：路径压缩时，记录到根的路径长度。•应用：食物链银河英雄传说
假面舞会
其实一个树可以压缩为一个集合，每个集合都有其代表元，说白了就是一种父亲指向，每个元素的代表元就是其父亲，而代表元为自己的元素无疑就是整棵树的根了。
给道例题：
•有n个罐子，每个罐子配有一把钥匙，有钥匙就能打开罐子。告诉你这n把钥匙分别放在哪个罐子里。•现在你要打开所有罐子，但是一开始你没有钥匙。于是你可以直接打碎一些罐子，取出里面的钥匙，或者利用之后拿到的钥匙，打开其他罐子。•请问，最少打破多少罐子，才能拿到所有钥匙。•数据范围：n<=1000000
这道题我觉得用图来做，用拓扑或者判断入度的方法判断。很快啊。
这里我就总结了线性结构和简单的树形结构并查集，说明这些简单的数据结构也同样发挥着重要作用，也是相当节省时间与空间的。