二楼强调一下我是男性

听说你们班比较好，所以有些问题你们知道了，就跟我说一声，说你们懂。另外有什么问题没听懂，直接举手问。
数组：
我们信息学要求的是，空间是指定的，所以我们就可以开一个静止的空间。要不然我们就不用数组了。其中数组可以观察变量，很方便的，一般我们的时间限制都在一秒，其中呢数组比动态空间几乎要快一倍。所以我们信息学大部分都用数组来实现。数组是固定的大小的。我一开始就申请好了空间，不是说我们需要的时候才申请。数组的大小是固定的，静态的，连续的。数组的插入、删除操作的时间是O(n)。
数组的插入删除为O(n)，这个在某些条件下就显得特别低效了，因此我们通过对数组元素的操作的限制，来达到高效的操作，于是引出了栈，队，堆。

栈：
信息学的栈一般使用数组实现。栈是后进后出的。进栈出栈都是取栈顶的。今年NOI已经让用STL库了，NOIP希望很大（干我啥事情……可怜的Pascal默默流泪……）如果用STL库的话，就可以直接调用栈。
一般用栈的时候，可以在栈底放上一个哨兵，比如说一个#号什么的，这样可以让栈在特定的时候停住，而不是继续作无意义的深入。

队列：
队列就是人在排队嘛……当然也有双向队列。但是队列有一个问题，就是初始化的时候，根据题目的不同，初始化也会不同。数组实现队列的时候，就有可能数组逾界，这个时候可以用循环数组来处理，就是到最后的时候还原到1。
队列最常用的是BFS（宽搜）单调队列以及SPFA算法。动态规划百分之二十以上就是单调队列。队列，而且是单调的。动态规划中国的产生是在95年出现的，单调队列也是近五年才出现的。单调队列技术呢，很多用。07年第一次在全国赛上用，到了去年，分区联赛普及组最后一题也要用单调队列。所以说这个在发展，很多东西在联赛当中也可能出现，这种技术也在不断的更新。到了高中，这种技术就应该要掌握。
有很多数据，有个窗口叫做数据窗口，只能看见窗口的一段，窗口长度为L，求窗口内的最大值和最小值之差最大的，求这个值
如果新进的数字大于前面的最大的（次大的，第三大的等等）数字，则前面全部扔掉，如此保持队列的始终单调。从而保留出每个窗口内的最大值，最小值并且保证数据不重复处理，减少时间复杂度，从而进行操作。
求01矩阵中最大的全零矩阵。
最笨的方法就是枚举左上角右下角，然后看里面是不是全零。单调队列的方式就是统计出来0的高度，然后找左边或者右边第一个比自己小的从而进行运算。

堆(heap)：
堆是以数组存储的完全二叉树，如果每个节点的左右节点的值都不比他的值小，则成为小根堆。反之称之为大根堆。编辑堆用的是数组，数组的特点是连续，为了保证连续性，所以这个树一定是完全二叉树（不一定是满二叉树）。第i个节点左孩子是第2*i个，右孩子是第2*i+1。n个节点的堆，高度为2为底N的对数。
堆的常见应用有：堆排序，动态求最小（大）值以及Dijkstra算法的优化（类似的还有Prim算法）
动态求最大小值：如合并果子（NOIP2004）就不讲了

黑匣子：
原题：
黑匣子（全国青少年信息学奥林匹克联赛培训教材（中学高级本））
【试题描述】
我们使用黑匣子的一个简单模型。它能存放一个整数序列和一个特别的变量i。在初始时刻，黑匣子为空且i等于0。这个黑匣子执行一序列的命令。有两类命令：
ADD(x)：把元素x放入黑匣子；  
     GET：i增1的同时，输出黑匣子内所有整数中第i小的数。牢记第i小的数是当黑匣子中的元素以非降序排序后位于第i位的元素  
可以分成两个堆，i代表大根堆的根，第二个堆放入比i大的元素组成的小根堆。插入元素x的时候，则比较与i的大小，从而判断是插入第一个堆还是第二个堆。取i的时候，直接取第一个堆的根即可。
有n个时间段，某个时间段可能包含其它时间段。
请找到能包含其它时间段最多的那个段，并计算出它包括的其他时间段有多少。
想的太入神？没打？误？随便吧……

上午结束

hash表，也叫做散列表，一般应用于有大量“动态”的插入（删除）和查找操作的一类问题。如果是静态的，通常可以先对数据排序，查找时就可以用“二分查找”，时间效率也很好了。虽然可以用平衡树，但是还是hash表，更容易实现。hash的思想是能直接找到需要的元素，因此必须在元素的存储位置和他的关键字之间建立一定的对应关系。这种一一对应的计算也称作hash函数。hash表冲突：通常hash函数不是一一对应关系，普通情况下hash函数可能会出现keyi不等于keyj，f(keyi)=f(keyj)的现象，也就是几个关键字可能对应同一个“地址”。解决冲突方法有多种：常见的有“拉链法”，即就是在地址上拉一条“链”（用链表排一下），分别对应关键字。“线形探测法”：即若存储的地址如果被占有则向下找空位进行存储，之后若要调用此数据的时候，则判定位子被占用了，则向下进行查找。直到下标等于本数据。
常用的hash函数有：直接取余数的方法，乘法取整的方法，平方取中的方法，字符串hash法。


并查集的引入
OI的比赛中，经常会有这样一个问题：给一些集合，要求不断作：“合并两个集合”和“查找两个元素是否在一个集合中”对于这类问题，已经有时间效率也很好的专用数据结构。当树的深度过长的时候，并查集的这棵树的查找效率就会降低，称之为并查集退化，这时候用“压缩路径技术”简单处理即可。


Allbarns：
原题：
农民约翰打算建一个新的矩形谷仓。但是,矩形谷仓的4个角落不能在落在软土路基上,只能落在一些固定点上。现在,他已经找到地面上有N（4 <= N <= 1,000）个点,角落只可以落在这些点上。他想知道依次每加多一个点，可以建立新谷仓的方法数量,请你帮助他找到答案。
输入格式：
第1行：一个整数，N
第2行至N +1行：每行有两个被空格分隔的整数的x，y,作为一个点的坐标。
         所有的x,y都不会超过16,000。所有点都是不同的。
输出格式：
共 N 行：每行表示当前可以建立的新的谷仓的数目。
样例输入（allbarns.in）：
8
1 2
1 -2
2 1
2 -1
-1 2
-1 -2
-2 1
-2 -1
样例输出（allbarns.out）：
0
0
0
0
0
1
3
6
样例解释：
最后的答案是（1,2,6,5），（1,3,6,8），（1,4,6,7），（2,3,5,8），（2,4,5,7），（3,4,8,7）
按照对角线相等，对角线中点相同，进行查询。如果能组成就是一个，能组成就是一个。然后进行合并和运算。

做空间的计算的时候，最好要减5MB的来计算，给程序也留一点空间去运行。所以要学会估算空间。计算当中零碎的变量，我们不看，因为占用的空间太小了。我们最关注的就是数组了。比如说我们开一个字符型数组是十的六次方的，就是1MB，如果是整型，就是2MB，长整型的话，就是4MB。要是开十的七次方个，我们就是40MB。递归函数，每递归一层，就要占用一个空间，如果递归过程里面有一个十的六次方数组，递归了两三层就可能爆掉。所以说最好用全局变量。
                                       

全文完

明天讲图论，大概听不懂……没有再接再厉了