冻结扫描算法例题

1. 卡巴扫描时在“事件”里的“原因”是iswift这个iswift是什么意思

这并不是什么蠕虫、木马之类的病毒文件,是因为你的系统里有不安全的数据源文件,没事的,一般盗版的系统里经常会有此类问题,只要设置卡巴斯基不用再提醒,就没事了

iSwift technology (iSwift技术)

Features: Use technology that can increase scan speed by only scanning new and altered objects. iSwift Works only for NTFS partitions. It identifies files by internal descriptors of the NTFS. The "footprint" of each file is stored in the dedicated database called FIDBOX.

特征：使用此技术能够增加扫描的速度，经由只有扫描新的和变更过的档案。
iSwift只能于NTFS分割磁区下运作。他是由NTFS内部的描述符号来识别档案。
每个档案的“痕迹”会被储存于专用的资料库，被称为FIDBOX。

Benefits: The algorithm is fast because no checksum has to be calculated. Works independent of format and size of the file.

优点：因为没有效验总和被计算，运算法则是快速的。
此运作与档案的格式与大小无关。

Limitations: it only applies to objects in NTFS file systems. Using the iSwift technology is not possible on computers running Microsoft Windows 98SE/ME/XP64 operating system. If the object is moved, it has to be re-scanned. iSwift requires a special driver.

限制：他只适用于NTFS档案系统中的物件。
在Microsoft Windows 98SE/ME/XP64的作业系统下是不可能使用iSwift技术的。
假如档案被移动时，它必须再次被扫瞄。iSwift需要特别的驱动程式。

iCheckertechnology(iChecker技术)
文件保护默认只扫描新建或者修改的文件，也就是说，在扫描前文件被添加或者修改过。 iCheckerТМ 和iStreamsТМ 技术使这成为可能。这些技术使用了一个统计表来检查文件。文件会根据以下的算法来执行扫描：
用户或者程序处理的每个文件被组件中断
文件保护扫描 iChecker和 iStreams数据库信息来拦截文件。对于这点，如下操作都是可能的：
如果没有信息在数据库中被拦截，它会被进行深层病毒扫描。所检测的文件总数会记录到一个数据库中。
如果数据库有相关文件的信息，那么文件保护在扫描期间对文件的当前状态和数据库记录的信息进行对比。如果信息是完全匹配，那么用户访问这些文件就不会被扫描。如果文件有某些改变，那就会对它进行详细扫描，然后把新信息记录到数据库中。

主要功能特性是：减少反病毒软件处理的时间。通过在将来检测时排除已检测过的对象来实现。

iChecker技术把反病毒检测的结果存储在特殊的数据库中。只能存储iChecker模块所支持的格式的文件信息。
包括：EXE，COM，LNK，TTF，ELF，INF，SYS，CHM，ZIP这些格式。

此项技术的意义在于“为了检查出哪些文件是已经检测过并且没有变化的”。此项技术基于KAV Inspector的原理而运作。数据库中存储了已检测过的文件的CRC记录。

当用户打开某文件时，反病毒软件对此文件进行CRC校验，处理数据库里CRC记录（这里检查文件是否被修改？）。如果文件没有变动则不检测。如果文件感染了未知病毒，采用这种技术也可以检查出来。

实际上进行CRC校验库的比对，会比全面进行文件病毒检测节省3-5倍的时间。

2. 启发式扫描技术的避免虚报

正如任何其他的通用检测技术一样，启发式扫描技术有时也会把一个本无病毒的程序指证为染毒程序，这就是所谓的查毒程序虚警或谎报现象。原因很简单。被检测程序中含有病毒所使用或含有的可疑功能。例如，QEMM所提供的一个LOADHI.COM程序就会含有以下可疑功能调用。 LoadHi程序中确实含有以上功能调用，而这些功能调用足以触发检毒程序的报警装置。因为LoadHi的作用就是为了分配高端内存，将驻留程序（通常如设备驱动程序等等）装入内存，然后移入高端内存，等等……，所有这些功能调用都可以找到一个合理的解释和确认，然而，检毒程序并不能分辨这些功能调用的真正用意，况且这些功能调用又常常被应用在病毒程序中，因此，可怜的检测程序只能判定Load Hi程序为“可能是病毒程序”。 虚警（谎报）的后果有多严重 如果某个基于上述启发式代码扫描技术的病毒检测程序在检测到某个文件时弹出报警窗口“该程序可以格式化磁盘且驻留内存”而你自己确切地知道当前被检测的程序是一个驻留式格式化磁盘工具软件，这算不算虚警谎报呢？ 因为一个这样的工具软件显然应当具备格式化盘以及驻留内存的能力。启发式代码检测程序的判断显然正确无误，这可算做虚警，但不能算做谎报（误报）。问题在于这个报警是否是“发现病毒”， 如果报警窗口只是说“该程序具备格式化盘和驻留功能”，好，100%正确，但它如果说“发现病毒”，那么显然是100%的错了。关键是我们片怎样看待和理解它真正的报警的含义。检测程序的使命在于发现和阐述程序内部代码执行的真正动机，到底这个程序会进行哪些操作，关于这些操作是否预期或合法，尚需要用户方面的判断。不幸的是，对于一个一的新手来说，要做出这样的判断仍然是有困难的。
不管是虚警也好，误报或谎报也好，抛开具体的名称叫法不谈，我们决不希望在每次扫描检测的时候我们的检测程序无缘由地狂喊“狼来了”，我们要尽力减少和避免这种人为的紧张状况，那么如何实现呢？必须努力做好以下几点：
1、 对于病毒行为的准确把握而给定的关于可疑功能调用集合的精确的定义。除非满足两个以上的病毒重要特征，否则不予报警。
2、 对于常规的程序代码的和识别能力。某些编译器提供运行时实时解压或解码的功能及服务例程，而这些情形往往是导致检测时误报警的原因，应当在检测程序中加入认知和识别这些情状的功能模块，以避免再次误报。
3、 对于特定程序的识别能力。如上面涉及到的LoadHi及驻留式格式化工具软件等等。
4、 类似“无罪假定”的功能，首先假定程序和电脑是不含病毒的。许多启发式代码分析检毒软件具有自学习功能，能够记信那些并非病毒的文件并在以后的检测过程中避免再报警。
如何处理虚警谎报
不管采用什么样的措施，虚警谎报现象总是要存在的。因此不可避免地用户要在某些报警信息出现时作出自己的抉择：是真正病毒还是误报？也许会有人说：“我怎么知道被报警的程序到底是病毒还是属于无辜误报？”大多数人在问及这个问题的第一反应，是“谁也无法证明和判断。”事实上是有办法作出最终判决的，但是这还要取决于应用启发式代码分析检测技术的查病毒程序的具体解释。 假如检测软件仅仅给出“发现可疑病毒功能调用”这样简单的警告，信息而没有更多的辅助信息，对于用户来说几乎没有什么可资判断是否真正病毒的实际帮助价值，换个说法，“可能是病毒”似乎永远没错，不必担负任何责任，而用户不希望得到这样模棱两可的解释。 相反地，如果检测软件把更为具体和实际的信息报告给用户，比如“警告，当前被检测程序含有驻留内存和格式化软硬盘的功能”，类似的情况更能帮助用户扩清楚到底会发生什么？该采取怎样应对措施。比如这种报警是出现在一个字处理编辑软件中，那么用户几乎可以断定这是一个病毒。当然如果这种报警是出现在一个驻留格式化盘工具软件上，用户大可不必紧张万分了。这样以来，报警的可疑病毒常用功能调用都能得到合理的解释，因而也会得到圆满正确的处理结果。 自然地， 需要一个有经验的用户从同样的报警信息中推理出一个 “染毒”还是“无毒”的，结论并非每一个用机者可以完全胜任的。因此，如果把这类软件设计成有某种学习记忆的能力，在第一次扫描时由有经验的用户逐一对有疑问的报警信息作好“是”与“非”的判断，而在以后的各次扫描检测时，由于软件学习并记忆了第一次检测时处理结果，将不再出现同样的烦人的提示警报。因为不论在什么情况下，偶尔请教一下某个有经验的“高手”并不，难难堪的是每次就同样的问题去麻烦别人。 不管怎样的缺点和不足，和其它的扫描识别技术相比起来，启发式代码分析扫描技术几乎总能提供足够的辅助判断，信息让我们最终判定被检测的目标对象是染毒的，亦或是干净的。启发式代码分析检测技术的实用应用效果如何？启发式扫描技术仍然是一种正在发展和不断完善中的新技术，但已经在大量优秀的反病毒软件中得到迅速的推广和应用。按照最保守的估计，一个精心设计的算法支持的启发式扫描软件，在不依赖任何对病毒预先的学习和了解的辅助，信息如特征代码，指纹字串，校验和等等的支持下，可以毫不费力地检查出90%以上的对它来说是完全未知的新病毒。 可能会出现一些个虚报、谎报的情况，适当加以控制，这种误报的概率可以很容易地被降低在0.1%以下。 传统扫描技术与启发式代码分析扫描技术的结合运用 前面论述了簋多启发式代码分析技术的优点和长处，会不会引起某些人的误解，以为传统的检测扫描技术就可以丢弃了呢？情况当然不是这样。从实际应用的效果看来，传统的手法由于基于对已知病毒的分析和研究，在检测时能够更准确，减少误报；但如果是对待此前根本没有见过的新病毒，由于传统手段的知识库并不存在该类（种）病毒的特征数据，则有可能毫无瓜，产生漏报的严重后果。而这时基于规则和定义的启发式代码分析技术则正好可以大显身手，使这类新病毒不至成为漏网之鱼。传统与启发式技术的结合支用，可以使病毒检测软件的检出率提高到前所未有的水平，而另一方面，又大大降低了总的误报率。
详见以下测试实验结果对比数据：
启发式判定结果 传统式判定结果 可能的真正结果 干净 干净 非常可能就是干净的 干净 有毒 很可能误报 有毒 干净 很可能有毒 有毒 有毒 极有可能确实染毒 三种技术结合使用 虚报率 10% 1% 1% 漏报率 0.1% 0.001% 0.00001% 某种病毒能够同时逃脱传统和启发式扫描分析的可能性是小的，如果两种分析的结论相一，致那么真实的结果往往就如同其判断结论一样砍无，疑两种不同技术对同一检测样分析的结果不一致的情况比较少见，这种情形下需借助另外的分析去得出最后结论。 仍然以 TbScan 6.02为测试举例，下面是分别使用不同技术和结合应用的测试结果： 测试用技术 总数为7210个样本的病毒检出数 检出率 传统的 7056 97.86% 启发式 6465 89.67% 结合应用 7194 99.78% 启发式反毒技术的未来展望 研究的逐步深入，使技术发展不断进步。一方面绝大多数反病毒厂家的产品中还未能引入一个较为成功和可靠的启发式检测技术的内核，另一方面，即使是在少数依靠的知名反病毒产品中这项技术的运用也还需要经受不断的完善和发展。任何改良的努力都会有不同程度的质量提高，但是不能企望在没有虚报为代价的前提下使检出率达到100%，或者反过来说，大约在相当长的时间里虚报和漏报的概率不可能达到0%。 这听上去或许有些不可思议，其实不难理解。100%正确的检测结果只所以不存在，是因为有相当一部分程序（或代码）介乎于病毒与非病毒之间，即便对于人脑来说，合乎逻辑又合乎病毒定义的结论往往会截然相反。随便举一个例子，如果依据广为接受的病毒的定义：“病毒，就是复制自身的拷贝或改良的复本的一些程序。”那么，众所周知的磁盘复制程序 DiskCopy岂不是也落入病毒的分类中了吗？但是，情况显然并非如此…… 病毒技术与反病毒技术恰如“道”与“魔”的关系，也许用“道高一尺，魔高一丈”来形容这对矛盾的斗争和发展进程再为恰当不过了。当反病毒技术的专家学者在研究启发式代码分析技术对传统的特征代码扫描法查毒技术进行改革的时候，也确实收到了很显着的效果，甚至可以说，相对于病毒技术的加密变换(Mutation)，尤其是多形、无定形病毒技术(Polymorphsm) 对于传统反毒技术的沉重打击，杀了一个漂亮的回马枪。但是，反毒技术的进步也会从另一方面激发和促使那些丧心病狂的病毒制作者的不断研制出更新的病毒，具有某种反启发式扫描技术功能，可以逃避这类检测技术的新型病毒。但是，值得庆幸的是，即便能够写出具有这种能力的病毒，它所需要的技术水准和编程能力要复杂得多，绝不可能象对搞传统的基于特征值扫描技术的反毒软件，那么容易，任何一个程序的新手只要将原有的病毒稍加改动， 哪怕只是一个字节，只要恰 好改变了所谓“特征字节”， 就可使这种旧病毒的新变种从未经升级的传统查毒软件的眼皮底下逃之夭夭。

3. C／C++三角形的扫描转换算法谁知道吗

解：由题意知，a^2c^2-b^2c^2=a^4-b^4
可以化为（a^2-b^2）c^2=(a^2+b^2)(a^2-b^2)
分析：
1）当a^2-b^2不等于0时，上式可化为c^2=a^2+b^2，这时，此三角形为直角三角形，c为斜边
2）当a^2-b^2＝0时，即：a^2=b^2，由于a,b,c均为正数，所以a=b，此三角形是等腰三角形。

4. 运用NStepScan算法来实现磁盘的扫描!我是要搞磁盘的调度!你能给出这种算法的VB源代码吗

我有C++版本的源码，你也可以拿去修改成VB的。如果你真的需要，可以联系我。

5. 哪位高手能给我解释解释单片机点阵扫描原理不谢谢

谈LED点阵的扫描原理，只要一看LED点阵的原理图就一目了然了，如下图：

图中，A--H可以看做行，1--7看做列；假如我们给点阵送人一个列数据0x80（1000 0000），并且同时送人一个行数据0x7f（0111 1111），此时我们就点亮了这个点阵左上角的那颗LED发光管，如果我们不停的行数据：0111 1111；1011 1111；1101 1111；1110 1111；1111 0111；1111 1011；1111 1101；1111 1110，这8个数据周而复始的送人点阵就是行扫描的过程，这个过程一般采用74HC138等译码器来完成，而在对应的行数据送人的同时也送人1--7的列数据，例如：

行=0111 1111，列=1000 0000

行=1011 1111，列=0100 0000

行=1101 1111，列=1010 0000

行=1110 1111，列=1001 0000

行=1111 0111，列=1000 1000

行=1111 1011，列=1000 0100

行=1111 1101，列=1000 0010

行=1111 1110，列=1000 0001

此时程序循环执行的结果会在点阵屏上显示左上至右下的对角斜线。

仔细想想应该不难理解。

在代码编写上，实现上述功能有很多方法，最长用的就是for循环，如果你网络资料会发现，大凡点阵显示代码中都会在显示函数中引用for循环，而且根据点阵数的不同会有：

for(i=0;i<8;i++)或for(i=0;i<16;i++)或for(i=0;i<32;i++)这就是对于8行、16行、32行点阵的扫描算法。

就说到这里吧，更多的知识请网络搜索吧。

6. 磁盘调度算法中的~扫描算法~还有~循环扫描算法~，需要移动到0磁道再返回码麻烦高手指点，学校发的破书写

总是按一个方向移动磁盘臂（向0反方向移动），处理完编号最高的磁道后，移动到具有读写请求的编号最低的磁道，然后继续向上移动。

这里你反过来理解就好了，就是从高到低

这里先访问168，然后是140,117，小于117的磁道已经没有请求了，此时磁盘臂应该回到288，然后向0方向移动

7. 扫描算法和电梯调度算法区别

扫描算法和电梯调度算法没有区别。扫描算法通常称为电梯调度算法，但是会出现饿死现象。

8. 计算机图形学：直线段扫描转换算法

//数值微分算法（DDA算法）
#include<iostream>
using namespace std;
int main()
{
float x0,y0,x1,y1,x2,y2;
cin>>x1>>y1;
cin>>x0>>y0;
float k;
k=(y1-y0)/(x1-x0);
if(k<1)
{
x2=x1+1;
y2=y2+k;
}
else if(k>=1)
{
y2=y1+1;
x2=1/k+x1;
}
cout<<x2<<" "<<y2<<endl;
return 0;
}
//中点划线算法
#include<iostream>
using namespace std;
int main()
{ float x,y;
float x0,y0,x1,y1;
cin>>x0>>y0>>x1>>y1;
float a,b,c;
a=y0-y1;
b=x1-x0;
c=x0*y1-x1*y0;
float sum;
sum=a*x+b*y+c;
float Xq,Yq;
float Xm,Ym;
Xm=x0+1;
Ym=y0+0.5;
float d;
d=a*Xm+b*Ym+c;
if(d<0)
{Xq=x0+1; Yq=y0+1; }
else if(d>0)
{ Xq=x0+1; Yq=y0; }
else if(d=0)
{ Xq=x0+1; Yq=y0; }
cout<<Xq<<" "<<Yq<<endl;return 0;
}
//Bresenham算法//有一个整数数组，请求出两两之差绝对值最大的值（最小的值）
#include<iostream>
using namespace std;
int jisuan(int a,int b)
{ int des=0; des=a-b; if(des<0)
des=-des;
return des;}
int main()
{ int dec=0; int max=0; int a[5]={0,2,5,9,4}; for(int i=1;i<5;i++)
{ dec=jisuan(a[i],a[i-1]); if(max<dec) max=dec; }
cout<<max<<endl;
return 0;
}
不好意思，最后一个是我写的另一个代码，贴错了

9. pascal题目

2003年国家集训队论文，王知昆，浅谈用极大化思想解决最大子矩形问题
网上有的，O(n²)的复杂度，n，m是5000都能1秒出解

浅谈用极大化思想解决最大子矩形问题

福州第三中学 王知昆

【摘要】
本文针对一类近期经常出现的有关最大（或最优）子矩形及相关变形问题，介绍了极大化思想在这类问题中的应用。分析了两个具有一定通用性的算法。并通过一些例题讲述了这些算法选择和使用时的一些技巧。

【关键字】 矩形，障碍点，极大子矩形

【正文】
一、 问题
最大子矩形问题：在一个给定的矩形网格中有一些障碍点，要找出网格内部不包含任何障碍点，且边界与坐标轴平行的最大子矩形。

这是近期经常出现的问题，例如冬令营2002的《奶牛浴场》，就属于最大子矩形问题。

Winter Camp2002,奶牛浴场
题意简述：（原题见论文附件）
John要在矩形牛场中建造一个大型浴场，但是这个大型浴场不能包含任何一个奶牛的产奶点，但产奶点可以出在浴场的边界上。John的牛场和规划的浴场都是矩形，浴场要完全位于牛场之内，并且浴场的轮廓要与牛场的轮廓平行或者重合。要求所求浴场的面积尽可能大。
参数约定：产奶点的个数S不超过5000,牛场的范围N×M不超过30000×30000。

二、 定义和说明
首先明确一些概念。

1、 定义有效子矩形为内部不包含任何障碍点且边界与坐标轴平行的子矩形。如图所示，第一个是有效子矩形（尽管边界上有障碍点），第二个不是有效子矩形（因为内部含有障碍点）。

2、 极大有效子矩形：一个有效子矩形，如果不存在包含它且比它大的有效子矩形，就称这个有效子矩形为极大有效子矩形。（为了叙述方便，以下称为极大子矩形）

3、 定义最大有效子矩形为所有有效子矩形中最大的一个（或多个）。以下简称为最大子矩形。

三、 极大化思想
【定理1】在一个有障碍点的矩形中的最大子矩形一定是一个极大子矩形。
证明：如果最大子矩形A不是一个极大子矩形，那么根据极大子矩形的定义，存在一个包含A且比A更大的有效子矩形，这与“A是最大子矩形”矛盾，所以【定理1】成立。

四、 从问题的特征入手，得到两种常用的算法
定理1虽然很显然，但却是很重要的。根据定理1，我们可以得到这样一个解题思路：通过枚举所有的极大子矩形，就可以找到最大子矩形。下面根据这个思路来设计算法。
约定：为了叙述方便，设整个矩形的大小为n×m，其中障碍点个数为s。

算法1
算法的思路是通过枚举所有的极大子矩形找出最大子矩形。根据这个思路可以发现，如果算法中有一次枚举的子矩形不是有效子矩形、或者不是极大子矩形，那么可以肯定这个算法做了“无用功”，这也就是需要优化的地方。怎样保证每次枚举的都是极大子矩形呢，我们先从极大子矩形的特征入手。

【定理2】：一个极大子矩形的四条边一定都不能向外扩展。更进一步地说，一个有效子矩形是极大子矩形的充要条件是这个子矩形的每条边要么覆盖了一个障碍点，要么与整个矩形的边界重合。

定理2的正确性很显然，如果一个有效子矩形的某一条边既没有覆盖一个障碍点，又没有与整个矩形的边界重合，那么肯定存在一个包含它的有效子矩形。根据定理2，我们可以得到一个枚举极大子矩形的算法。为了处理方便，首先在障碍点的集合中加上整个矩形四角上的点。每次枚举子矩形的上下左右边界（枚举覆盖的障碍点），然后判断是否合法（内部是否有包含障碍点）。这样的算法时间复杂度为O(S5)，显然太高了。考虑到极大子矩形不能包含障碍点，因此这样枚举4个边界显然会产生大量的无效子矩形。
考虑只枚举左右边界的情况。对于已经确定的左右边界，可以将所有处在这个边界内的点按从上到下排序，如图1中所示，每一格就代表一个有效子矩形。这样做时间复杂度为O(S3)。由于确保每次得到的矩形都是合法的，所以枚举量比前一种算法小了很多。但需要注意的是，这样做枚举的子矩形虽然是合法的，然而不一定是极大的。所以这个算法还有优化的余地。通过对这个算法不足之处的优化，我们可以得到一个高效的算法。
回顾上面的算法，我们不难发现，所枚举的矩形的上下边界都覆盖了障碍点或者与整个矩形的边界重合，问题就在于左右边界上。只有那些左右边界也覆盖了障碍点或者与整个矩形的边界重合的有效子矩形才是我们需要考察的极大子矩形，所以前面的算法做了不少“无用功”。怎么减少“无用功”呢，这里介绍一种算法（算法1），它可以用在不少此类题目上。
算法的思路是这样的，先枚举极大子矩形的左边界，然后从左到右依次扫描每一个障碍点，并不断修改可行的上下边界，从而枚举出所有以这个定点为左边界的极大子矩形。考虑如图2中的三个点，现在我们要确定所有以1号点为左边界的极大矩形。先将1号点右边的点按横坐标排序。然后按从左到右的顺序依次扫描1号点右边的点，同时记录下当前的可行的上下边界。
开始时令当前的上下边界分别为整个矩形的上下边界。然后开始扫描。第一次遇到2号点，以2号点作为右边界，结合当前的上下边界，就得到一个极大子矩形（如图3）。同时，由于所求矩形不能包含2号点，且2号点在1号点的下方，所以需要修改当前的下边界，即以2号点的纵坐标作为新的下边界。第二次遇到3号点，这时以3号点的横坐标作为右边界又可以得到一个满足性质1的矩形（如图4）。类似的，需要相应地修改上边界。以此类推，如果这个点是在当前点（确定左边界的点）上方，则修改上边界；如果在下方，则修改下边界；如果处在同一行，则可中止搜索（因为后面的矩形面积都是0了）。由于已经在障碍点集合中增加了整个矩形右上角和右下角的两个点，所以不会遗漏右边界与整个矩形的右边重合的极大子矩形（如图5）。需要注意的是，如果扫描到的点不在当前的上下边界内，那么就不需要对这个点进行处理。
这样做是否将所有的极大子矩形都枚举过了呢？可以发现，这样做只考虑到了左边界覆盖一个点的矩形，因此我们还需要枚举左边界与整个矩形的左边界重合的情况。这还可以分为两类情况。一种是左边界与整个举行的左边界重合，而右边界覆盖了一个障碍点的情况，对于这种情况，可以用类似的方法从右到左扫描每一个点作为右边界的情况。另一种是左右边界均与整个矩形的左右边界重合的情况，对于这类情况我们可以在预处理中完成：先将所有点按纵坐标排序，然后可以得到以相邻两个点的纵坐标为上下边界，左右边界与整个矩形的左右边界重合的矩形，显然这样的矩形也是极大子矩形，因此也需要被枚举到。
通过前面两步，可以枚举出所有的极大子矩形。算法1的时间复杂度是O(S2)。这样，可以解决大多数最大子矩形和相关问题了。

虽然以上的算法（算法1）看起来是比较高效的，但也有使用的局限性。可以发现，这个算法的复杂度只与障碍点的个数s有关。但对于某些问题，s最大有可能达到n×m，当s较大时，这个算法就未必能满足时间上的要求了。能否设计出一种依赖于n和m的算法呢？这样在算法1不能奏效的时候我们还有别的选择。我们再重新从最基本的问题开始研究。

算法2
首先，根据定理1：最大有效子矩形一定是一个极大子矩形。不过与前一种算法不同的是，我们不再要求每一次枚举的一定是极大子矩形而只要求所有的极大子矩形都被枚举到。看起来这种算法可能比前一种差，其实不然，因为前一种算法并不是完美的：虽然每次考察的都是极大子矩形，但它还是做了一定量的“无用功”。可以发现，当障碍点很密集的时候，前一种算法会做大量没用的比较工作。要解决这个问题，我们必须跳出前面的思路，重新考虑一个新的算法。注意到极大子矩形的个数不会超过矩形内单位方格的个数，因此我们有可能找出一种时间复杂度是O(N×M)的算法。

定义：
有效竖线：除了两个端点外，不覆盖任何障碍点的竖直线段。
悬线：上端点覆盖了一个障碍点或达到整个矩形上端的有效竖线。如图所示的三个有效竖线都是悬线。

对于任何一个极大子矩形，它的上边界上要么有一个障碍点，要么和整个矩形的上边界重合。那么如果把一个极大子矩形按x坐标不同切割成多个（实际上是无数个）与y轴垂直的线段，则其中一定存在一条悬线。而且一条悬线通过尽可能地向左右移动恰好能得到一个子矩形（未必是极大子矩形，但只可能向下扩展）。通过以上的分析，我们可以得到一个重要的定理。

【定理3】：如果将一个悬线向左右两个方向尽可能移动所得到的有效子矩形称为这个悬线所对应的子矩形，那么所有悬线所对应的有效子矩形的集合一定包含了所有极大子矩形的集合。

定理3中的“尽可能”移动指的是移动到一个障碍点或者矩形边界的位置。
根据【定理3】可以发现，通过枚举所有的悬线，就可以枚举出所有的极大子矩形。由于每个悬线都与它底部的那个点一一对应，所以悬线的个数＝(n-1)×m（以矩形中除了顶部的点以外的每个点为底部，都可以得到一个悬线，且没有遗漏）。如果能做到对每个悬线的操作时间都为O(1)，那么整个算法的复杂度就是O(NM)。这样，我们看到了解决问题的希望。
现在的问题是，怎样在O(1)的时间内完成对每个悬线的操作。我们知道，每个极大子矩形都可以通过一个悬线左右平移得到。所以，对于每个确定了底部的悬线，我们需要知道有关于它的三个量：顶部、左右最多能移动到的位置。对于底部为(i,j)的悬线，设它的高为hight[i,j],左右最多能移动到的位置为left[i,j],right[i,j]。为了充分利用以前得到的信息，我们将这三个函数用递推的形式给出。

对于以点(i,j)为底部的悬线：
如果点(i－1,j)为障碍点，那么，显然以(i,j)为底的悬线高度为1，而且左右均可以移动到整个矩形的左右边界，即

如果点(i－1,j)不是障碍点，那么，以(i,j)为底的悬线就等于以(i-1,j)为底的悬线＋点(i,j)到点(i-1,j)的线段。因此，height[i,j]=height[i-1,j]+1。比较麻烦的是左右边界，先考虑left[i,j]。如下图所示，(i,j)对应的悬线左右能移动的位置要在(i-1,j)的基础上变化。
即left[i,j]=max

right[i,j]的求法类似。综合起来，可以得到这三个参数的递推式：

这样做充分利用了以前得到的信息，使每个悬线的处理时间复杂度为O(1)。对于以点(i,j)为底的悬线对应的子矩形，它的面积为(right[i,j]-left[i,j])*height[i,j]。
这样最后问题的解就是：
Result＝
max
整个算法的时间复杂度为O(NM)，空间复杂度是O(NM)。

两个算法的对比：
以上说了两种具有一定通用性的处理算法，时间复杂度分别为O(S2)和O(NM)。两种算法分别适用于不同的情况。从时间复杂度上来看，第一种算法对于障碍点稀疏的情况比较有效，第二种算法则与障碍点个数的多少没有直接的关系（当然，障碍点较少时可以通过对障碍点坐标的离散化来减小处理矩形的面积，不过这样比较麻烦，不如第一种算法好），适用于障碍点密集的情况。

五、 例题
将前面提出的两种算法运用于具体的问题。
1、 Winter Camp2002,奶牛浴场
分析：
题目的数学模型就是给出一个矩形和矩形中的一些障碍点，要求出矩形内的最大有效子矩形。这正是我们前面所讨论的最大子矩形问题，因此前两种算法都适用于这个问题。
下面分析两种算法运用在本题上的优略：
对于第一种算法，不用加任何的修改就可以直接应用在这道题上，时间复杂度为O(S2)，S为障碍点个数；空间复杂度为O(S)。
对于第二种算法，需要先做一定的预处理。由于第二种算法复杂度与牛场的面积有关，而题目中牛场的面积很大（30000×30000），因此需要对数据进行离散化处理。离散化后矩形的大小降为S×S，所以时间复杂度为O(S2)，空间复杂度为O(S)。说明：需要注意的是，为了保证算法能正确执行，在离散化的时候需要加上S个点，因此实际需要的时间和空间较大，而且编程较复杂。
从以上的分析来看，无论从时空效率还是编程复杂度的角度来看，这道题采用第一种算法都更优秀。

2、 OIBH模拟赛1,提高组，Candy
题意简述：（原题见论文附件）
一个被分为 n*m 个格子的糖果盒，第 i 行第 j 列位置的格子里面有 a [i,j] 颗糖。但糖果盒的一些格子被老鼠洗劫。现在需要尽快从这个糖果盒里面切割出一个矩形糖果盒，新的糖果盒不能有洞，并且希望保留在新糖果盒内的糖的总数尽量多。
参数约定：1 ≤ n，m ≤ 1000

分析
首先需要注意的是：本题的模型是一个矩阵，而不是矩形。在矩阵的情况下，由于点的个数是有限的，所以又产生了一个新的问题：最大权值子矩阵。

定义：
有效子矩阵为内部不包含任何障碍点的子矩形。与有效子矩形不同，有效子矩阵地边界上也不能包含障碍点。
有效子矩阵的权值（只有有效子矩形才有权值）为这个子矩阵包含的所有点的权值和。
最大权值有效子矩阵为所有有效子矩阵中权值最大的一个。以下简称为最大权值子矩阵。

本题的数学模型就是正权值条件下的最大权值子矩阵问题。再一次利用极大化思想，因为矩阵中的权值都是正的，所以最大权值子矩阵一定是一个极大子矩阵。所以我们只需要枚举所有的极大子矩阵，就能从中找到最大权值子矩阵。同样，两种算法只需稍加修改就可以解决本题。下面分析两种算法应用在本题上的优略：
对于第一种算法，由于矩形中障碍点的个数是不确定的，而且最大有可能达到N×M,这样时间复杂度有可能达到O(N2M2)，空间复杂度为O(NM)。此外，由于矩形与矩阵的不同，所以在处理上会有一些小麻烦。
对于第二种算法，稍加变换就可以直接使用，时间复杂度为O(NM),空间复杂度为O（NM）。

可以看出，第一种算法并不适合这道题，因此最好还是采用第二种算法。

3、 Usaco Training, Section 1.5.4, Big Barn
题意简述（原题见论文附件）
Farmer John想在他的正方形农场上建一个正方形谷仓。由于农场上有一些树，而且Farmer John又不想砍这些树，因此要找出最大的一个不包含任何树的一块正方形场地。每棵树都可以看成一个点。
参数约定：牛场为N×N的，树的棵数为T。N≤1000,T≤10000。
分析：
这题是矩形上的问题，但要求的是最大子正方形。首先，明确一些概念。
1、 定义有效子正方形为内部不包含任何障碍点的子正方形
2、 定义极大有效子正方形为不能再向外扩展的有效子正方形，一下简称极大子正方形
3、 定义最大有效子正方形为所有有效子正方形中最大的一个（或多个），以下简称最大子正方形。

本题的模型有一些特殊，要在一个含有一些障碍点的矩形中求最大子正方形。这与前两题的模型是否有相似之处呢？还是从最大子正方形的本质开始分析。
与前面的情况类似，利用极大化思想，我们可以得到一个定理：
【定理4】：在一个有障碍点的矩形中的最大有效子正方形一定是一个极大有效子正方形。

根据【定理4】,我们只需要枚举出所有的极大子正方形，就可以从中找出最大子正方形。极大子正方形有什么特征呢？所谓极大，就是不能再向外扩展。如果是极大子矩形，那么不能再向外扩展的充要条件是四条边上都覆盖了障碍点（【定理2】）。类似的，我们可以知道，一个有效子正方形是极大子正方形的充要条件是它任何两条相邻的边上都覆盖了至少一个障碍点。根据这一点，可以得到一个重要的定理。
【定理5】：每一个极大子正方形都至少被一个极大子矩形包含。且这个极大子正方形一定有两条不相邻的边与这个包含它的极大子矩形的边重合。

根据【定理5】,我们只需要枚举所有的极大子矩形，并检查它所包含的极大子正方形（一个极大子矩形包含的极大子正方形都是一样大的）是否是最大的就可以了。这样，问题的实质和前面所说的最大子矩形问题是一样的，同样的，所采用的算法也是一样的。
因为算法1和算法2都枚举出了所有的极大子矩形，因此，算法1和算法2都可以用在本题上。具体的处理方法如下：对于每一个枚举出的极大子矩形，如图所示，如果它的边长为a、b，那么它包含的极大子正方形的边长即为min(a,b)。
考虑到N和T的大小不同，所以不同的算法会有不同的效果。下面分析两种算法应用在本题上的优略。
对于第一种算法，时间复杂度为O(T2)，对于第二种算法，时间复杂度为O(N2)。因为N<T，所以从时间复杂度的角度看，第二种算法要比第一种算法好。考虑到两个算法的空间复杂度都可以承受，所以选择第二种算法较好些。
以下是第一种和第二种算法编程实现后在USACO Training Program Gateway上的运行时间。可以看出，在数据较大时，算法2的效率比算法1高。

算法1：
Test 1: 0.009375
Test 2: 0.009375
Test 3: 0.009375
Test 4: 0.009375
Test 5: 0.009375
Test 6: 0.009375
Test 7: 0.021875
Test 8: 0.025
Test 9: 0.084375
Test 10: 0.3875
Test 11: 0.525
Test 12: 0.5625
Test 13: 0.690625
Test 14: 0.71875
Test 15: 0.75 算法2：
Test 1: 0.009375
Test 2: 0.009375
Test 3: 0.009375
Test 4: 0.009375
Test 5: 0.009375
Test 6: 0.00625
Test 7: 0.009375
Test 8: 0.009375
Test 9: 0.0125
Test 10: 0.021875
Test 11: 0.028125
Test 12: 0.03125
Test 13: 0.03125
Test 14: 0.03125
Test 15: 0.034375

以上，利用极大化思想和前面设计的两个算法，通过转换模型，解决了三个具有一定代表性的例题。解题的关键就是如何利用极大化思想进行模型转换和如何选择算法。

五、小结
设计算法要从问题的基本特征入手，找出解题的突破口。本文介绍了两种适用于大部分最大子矩形问题及相关变型问题的算法，它们设计的突破口就是利用了极大化思想，找到了枚举极大子矩形这种方法。
在效率上，两种算法对于不同的情况各有千秋。一个是针对障碍点来设计的，因此复杂度与障碍点有关；另一个是针对整个矩形来设计的，因此复杂度与矩形的面积有关。虽然两个算法看起来有着巨大的差别，但他们的本质是相通的，都是利用极大化思想，从枚举所有的极大有效子矩形入手，找出解决问题的方法。

需要注意的是，在解决实际问题是仅靠套用一些现有算法是不够的，还需要对问题进行全面、透彻的分析,找出解题的突破口。
此外，如果采用极大化思想，前面提到的两种算法的复杂度已经不能再降低了，因为极大有效子矩形的个数就是O(NM)或O(S2)的。如果采用其他算法，理论上是有可能进一步提高算法效率，降低复杂度的。

七、 附录：
1、几个例题的原题。 见论文附件.doc

2、例题的程序。 见论文附件.doc
说明：所有程序均在Free Pascal IDE for Dos, Version 0.9.2上编译运行

参考书目
1、 信息学奥林匹克 竞赛指导
----1997～1998竞赛试题解析
吴文虎 王建德 着
2、 IOI99中国集训队优秀论文集
3、 信息学奥林匹克（季刊）
4、 《金牌之路 竞赛辅导》
江文哉主编 陕西师范大学出版社出版

10. GSP算法的GSP算法描述

GSP算法 基本步骤如下：
1）扫描序列数据库，得到长度为1的序列模式L1，作为初始的种子集
2）根据长度为i 的种子集Li ，通过连接操作和修剪操作生成长度为i+1的候选序列模式Ci+1；然后扫描序列数据库，计算每个候选序列模式的支持度，产生长度为i+1的序列模式Li+1，并将Li+1作为新的种子集
3）重复第二步，直到没有新的序列模式或新的候选序列模式产生为止
产生候选序列模式主要分两步：
连接阶段：如果去掉序列模式s1的第一个项目与去掉序列模式s2的最后一个项目所得到的序列相同，则可以将s1与s2进行连接，即将s2的最后一个项目添加到s1中
修切阶段：若某候选序列模式的某个子序列不是序列模式，则此候选序列模式不可能是序列模式，将它从候选序列模式中删除
候选序列模式[ 的支持度计算：对于给定的候选序列模式集合C，扫描序列数据库，对于其中的每一条序列s,找出集合C中被s所包含的所有候选序列模式，并增加其支持度计数
GSP需要多次扫描序列数据库，在第一次扫描中，对所有的单个项目(1—序列模式)进行计数。利用频繁1—序列模式生成候选频繁2—序列模式，进行第二次扫描并求候选频繁2—序列模式的支持数。使用频繁2—序列模式生成候选频繁3—序列模式，重复以上过程，直到找出所有的频繁序列模式。 哈希树GSP 采用哈希树存储候选序列模式。哈希树的节点分为三类： 1、根节点；
2、内部节点；
3、叶子节点。
根节点和内部节点中存放的是一个哈希表，每个哈希表项指向其它的节点。而叶子节点内存放的是一组候选序列模式。 从根节点开始，用哈希函数对序列的第一个项目做映射来决定从哪个分支向下，依次在第n层对序列的第n个项目作映射来决定从哪个分支向下，直到到达一个叶子节点。将序列储存在此叶子节点。
初始时所有节点都是叶子节点，当一个叶子节点所存放的序列数目达到一个阈值，它将转化为一个内部节点。
候选序列模式支持度的计算
给定一个序列s是序列数据库的一个记录：
1）对于根节点，用哈希函数对序列s的每一个单项做映射来并从相应的表项向下迭代的进行操作 2）。
2）对于内部节点，如果s是通过对单项x做哈希映射来到此节点的，则对s中每一个和x在一个元素中的单项以及在x所在元素之后第一个元素的第一个单项做哈希映射，然后从相应的表项向下迭代做操作 2）或 3）。
3）对一个叶子节点，检查每个候选序列模式c是不是s的子序列.如果是相应的候选序列模式支持度加一。
这种计算候选序列的支持度的方法避免了大量无用的扫描，对于一条序列，仅检验那些最有可能成为它子序列的候选序列模式。扫描的时间复杂度由O(n*m)降为O(n*t),其中n表示序列数量，m表示候选序列模式的数量，t代表哈希树叶子节点的最大容量