资源简介

最后de祝福 (NOIP考前知识大总结)
DOC文件最后一次更新
明天就要收拾行囊了,今晚是最后一次机会上论坛祝福大家了!
Send My Best Blessing to Every OIer !
想起自己从高一起OI的经历,自己在OI里的成长
我在这里先谢谢各位,一个人孤军奋战自学的滋味并不好受
没有论坛上各位大牛的帮助,我就不会有今天
曾经为了OI付出了巨大的牺牲
顶着老师父母的压力依然执著的追求着自己的理想
高三 , 这次是自己最后一次OI的战役了
在这里
祝福大家在周六的时候能发挥出最好的水平 RP++
实现自己的理想 无悔于对OI的选择!第一题 上升序列（lis.pas/c/cpp）
对于一个给定的S={a1,a2,a3,…,an},若有P={ax1,ax2,ax3,…,axm},满足(x1任务
给出S序列，给出若干询问。对于第i个询问，求出长度为Li的上升序列，如有多个，求出字典序最小的那个（即首先x1最小，如果不唯一，再看x2最小……），如果不存在长度为Li的上升序列，则打印Impossible.
输入
第一行一个N，表示序列一共有N个元素
第二行N个数，为a1,a2,…,an
第三行一个M，表示询问次数。下面接M行每行一个数Li，表示要询问长度为Li的上升序列。
输出
对于每个询问，如果对应的序列存在，则输出，否则打印Impossible.
样例
lis.in
6
3 4 1 2 3 6
3
6
4
5
lis.out
Impossible
1 2 3 6
Impossible
数据范围
N<=10000
M<=1000
【算法简析】
首先很容易发现，如果Li的长度大于这个序列的LIS的长度，那么一定无解，否则一定有解。为方便讨论，下文只考虑有解情况。
暂且抛开“字典序最小”这个限制条件，即任何长度为Li的上升序列Pi都可以看作符合要求，那么题目的所有要求都可以由LIS来满足。这样我们就可以直接求这个序列的LIS，然后对于所有m次询问，用O(n)的时间输出，这样算法总的时间复杂度就是O(nlogn+nm)。
那么如果要求字典序最小又如何处理呢？其实我们完全可以在相同的时间复杂度内解决问题，只是需要一些转化。
注意到在求LIS的过程中，实际上我们得到的不只是LIS，而是每个数作为子序列末尾的所有最长上升序列。把问题换一个角度，假设我们知道以每个数a[i]作为开头的最长上升序列的长度lis[i]，那么就很容易利用贪心思想构造出答案了。这个贪心成立的前提就是：只要以该元素为开头的LIS的长度大于等于Li，则一定有解。该结论是很显然的。
下面简述贪心的方法：
累加下标j，从左到右扫描序列，如果lis[j]≥Li，则答案序列的第Li个数就是a[j]，并且Li减1。重复上述过程直到Li=0。最后将答案序列倒着输出即可。
这个贪心显然是成立的。由于j是从小到大逐次增加，所以第一个符合lis[j]≥Li的必然就是最优解。每次找到一个符合的元素，所需要的LIS的长度就会减少1。这样重复下去得到的必然是最优解。
由于只需要对序列做一遍扫描，时间复杂度最坏O(n)。构造答案的时间为O(nm)，加上预处理求LIS的O(nlogn)的时间，总时间复杂度为O(nlogn+nm)。
细节：求以a[i]为开头的LIS比较麻烦，可以把序列反过来后求以a[i]为末尾的LDS（Longest Decreasing Subsequence），这样处理起来较方便。开个帖子 主要的说一下SGU有关的问题
Q：SGU的速度很慢啊 很费时间啊
A：最根本的 推进国企改革 促进中国电信高速发展 或者 中国吞并俄罗斯 将俄罗斯用户也纳进中国电信范围 除此以外 我也没有什么太好的方法 不过 速度慢也不会太离谱 总没有OIBH慢吧 最后 我想说 比起你写错程序Debug的时间来 这点时间不多吧 真心想做的人 是不怕慢的
Q：SGU的机器很慢啊 我的程序不是会受影响么
A：这个不是借口 每道题目AC的人都那么多 没有上千也有上百 他们不也熬过来了 再说 他的机器慢就变相增加了你AC的难度 请关注下面关于难度的帖子
Q：编译器竟然不是FreePascal 多不好
A：众所周知 Delphi的语法和Pascal是大致一样的 一般用户无所谓的 再说了 明显Delphi编译的程序比FPascal编译出来的快 对你AC有利总不是坏事吧 如果会有莫名其妙的CE 你可以装一个Delphi 也可以在你的程序前面加上{$MODE Delphi}然后在FP下编译 FP就会按照Delphi语法编译 可以帮你找出错误
Q：SGU的题目太难了 我都不会做
A：100总会做吧 但是 如果NOIP NOI都考这样的题目 你觉得中国OI会有发展么 显然的 天天做A+B是不会有进步的 如果你不想进步 可以选择其它很简单的题库 如果你认为题目太难了以至于NOI不会考的话 那可就错了 NOI大多数的题目 其实都比SGU的平均水平难 当然 对于立足NOIP的选手 可能是难了一点点哦
Q：我真的不会做 怎么办
A：最主要的 请参考国家集训队表格中的SGU部分内容 那里的讲解比较详细 如果还不会的话 可以在这里提出
Q：我的程序总是WA(TLE同理) 怎么办
A：最好的办法是自己拿眼睛看程序 拿自己数据测程序 一般情况下 都能找到错误 如果很难的话 请查阅论坛以前的帖子 看看是否有同样的情况 除此以外 可以参考别人的程序 但是我不推荐你这么做
Q：怎么能找到数据
A：有三个办法 一 使用二分+提交的方法 这个方法对服务器影响很大 二 入侵服务器 搞到数据 如果你搞到的话 最好给我来一份 三 拿着刀架在管理员的脖子上 用英语说(俄语最好 不推荐汉语):"要命还是要数据？"
Q：如果我还有问题怎么办
A：解决途径很多 你可以到最近的观音庙去烧香拜佛 祈求神仙姐姐告诉你答案 也可以在论坛发帖 希望用户里面有人知道答案Pascal语言基础知识
Pascal语言基础知识
2.1 Pascal程序基本组成
例1.1计算半径为R的圆面积S
[Copy to clipboard]
CODE:
program Area; {程序首部}
{已知半径求圆的面积}
const pi=3.14159; 　{说明部分——数据描述}
var s,r:real;
begin　　　　　　　　　　　{执行部分}
readln(r);
s:=pi*sqr(r);
writeln(＇s=＇,s);
end.
　
上述程序第一行称为程序首部。其中用花括号(注释可以用{ }或（* *）来表示）括起来的内容是注释，程序第二行就是一个注释，注释除了给人看，增加程序的可读性外，对程序编译和运行不起作用。一个程序可以包含多个出现在不同处注释，亦可无注释。程序第三行是常量说明，程序第四行是变量说明。程序从begin到end都是执行（语句）部分
(1)程序首部
例1.1的第一行称为程序首部。program是保留字，接着是程序名（由你依据“标示符”规则自行定义），最后以分号表示程序首部结束，下面是程序主体的开始。程序首部在一个Turbo Pascal（仅在Turbo Pascal中有效）程序中并非必须出现，它是可选的。写上它仅起了文档作用。因此，在时间有限的情况下，如果用Turbo Pascal编程完全可以省略程序首部。
(2)程序体
a.说明部分
说明部分用于定义和说明程序中用到的数据，由单元说明、标号说明、常量说明、类型说明、变量说明、函数或过程说明组成，并且这些数据的说明次序必须按照以上次序。但是一个简单的Turbo Pascal程序也可以不包含说明部分，也就是说说明部分是可选的。
b.执行部分
执行部分描述了程序要执行的操作。它必须以一个Turbo Pascal保留字begin开始，以保留字end后跟句点结束，其间是一些执行具体操作的语句，并且以分号作为语句之间的分隔符。begin 和end必须成对出现，这是一个Turbo Pascal程序所必须有的。紧跟end之后的句号表示执行部分的结束，也表示整个程序的结束。此后的任何语句都无效。Turbo Pascal规定紧随end之前出现的分号允许省略。
(3)一个完全的Pascal程序结构
[Copy to clipboard]
CODE:
program 程序名；
　uses
　　　已知单元说明；
　label
　　　标号说明；
　const
　　常量说明；
　type
　　　类型说明；
　var
　　变量说明；
　function
　　函数说明；
　procedure
　　过程说明；
begin
　语句；
　语句；
　……
　语句
end.
2.2 Pascal字符与符号
1.保留字(关键字)
所谓保留字是指在Pascal语言中具有特定的含义，你必须了解它的含义，以便于正确的使用，否则会造成错误。标准Pascal语言中的保留字一共有35个，Turbo Pascal语言一共有51个。下面是Pascal语言的保留字(斜体是Turbo Pascal特有的保留字):
[Copy to clipboard]
CODE:
AND，ARRAY，BEGIN，CASE，CONST，DIV，DO，DOWNTO，ELSE，END，FILE，FOR，FUNTION，GOTO，IF，IN，LABEL，MOD，NIL，NOT，OF，OR，PACKED，PROCEDURE，PROGRAM，RECORD，REPEAT，SET，THEN，TO，TYPE，UNTIL，VAR，WHILE，WITH，EXPORTS，SHR，STRING，ASM，OBJECT，UNIT，CONSTRUCTOR，IMPLEMENTATION，DESTRUCTOR，USES，INHERITED，INLINE，INTERFACE，LIBRARY，XOR，SHL
２.标识符
(1)表识符的定义：标识符就是以字母开头的字母数字序列，有效长度为63个字符，并且大小写等效。可以用来标示常量、变量、程序、函数等。例如例1.1中的Area(程序名)，pi(符号常量)，s、r(变量名)都是标识符。
(2)表识符的分类：
　　　　a.标准标识符：指Pascal语言预先定义的表识符，具有特殊含义。
以下列举了Turbo Pascal语言部分常用的标准表识符：
QUOTE:
标准常量 False Maxint True 　 　 　 　
标准类型 Boolean Char Real Integer 　 　 　
标准函数 Abs Arctan Chr Cos Eof Eoln Exp
　 Ln Odd Ord Pred Round Sin Sqr
　 Sqrt Succ Trunc 　 　 　 　
标准过程 Dispose Get New Pack Page Put Read
　 Readln Reset Rewrite Unpack Write Writeln 　
标准文件 Input Output
　 　 　 　 　
b.用户字定义表识符：由你来根据需要定义。
（1）选用的表识符不能和保留字相同。
（2）语法上允许预定义的标准标识符作为你定义的的表识符使用，但最好还是不要用。
以下列举了你在定义表识符时可以用的字符：
[Copy to clipboard]
CODE:
A——Z；a——z；0——9；+，-，*，/，=，<>，<=，>=，<，>，(，)，[，]，{，}，:=，，，；，.，：，..，＇，^
2.3　Pascal数据类型
数据是程序设计的一个重要内容，其重要特征----数据类型，确定了该数据的形、取值范围以及所能参与的运算。
Turbo Pascal 提供了丰富的数据类型，这些数据类型可以分为三大类：简单类型、构造类型和指针类型，其中简单类型可以分为标准类型（整型、实型、字符型和布尔型）和自定义类型（枚举型和子界型），构造类型可以分为数组类型、集合类型、记录类型和文件类型。这些数据类型中除了指针类型是动态数据类型外，其他的都是静态数据类型。在这些数据类型中简单类型都是有序类型，除了实型以外的简单类型都是顺序类型，所谓顺序类型就是他们的值不仅是有序的而且是有顺序号。
在这里主要介绍整型、实型、字符型和布尔型四种常用的数据类型。
1.整型
一个整型数据用来存放整数。Turbo Pascal支持五种预定义整型，它们是shortint（短整型）、 integer（整型）、 longint（长整型）、 byte（字节型）和 word（字类型），Turbo Pascal分别用相同的名字作为他们的表识符。每一种类型规定了相应的整数取值范围以及所占用的内存字节数。
类型 数值范围 占字节数 格式
[Copy to clipboard]
CODE:
shortint -128..128 1 带符号8位
inteter -32768..32767 2 带符号16位
longint -2147483648..2147483647 4 带符号32位
byte 0..255 1 带符号8位
word 0..65535 2 带符号16位
Turbo Pascal规定了两个预定义整型常量表识符maxint和maxlonint，他们各表示确定的常数值，maxint为32767， longint为2147483647，他们的类型分别是integer 和longint。
2.实型
一个实型数据用类存放实数。Turbo Pascal支持五种预定义实型，它们是real（基本实型）、 single（但精度实型）、double（双精度实型）、extended（扩展实型）、comp（装配实型），Turbo Pascal分别用相同的名字作为他们的表识符。每一种类型规定了相应的实数取值范围、所占用的内存字节数以及它们所能达到的精度。
类型 数值范围 占字节数 有效位数
[Copy to clipboard]
CODE:
real 2.9e-39..1.7e38 6 11..12
single 1.5e-45..3.4e38 4 7..8
double 5.0e-324..1.7e308 8 15..16
extended 3.4e-4932..1.1e4932 10 19..20
comp -2**63+1..2**63-1 8 19..20
Turbo Pascal支持两种用于执行实型运算的代码生成模式：软件仿真模式和80x87浮点模式。除了real可以在软件仿真模式下直接运行以外，其他类型必须在80x87浮点模式下运行。
3.布尔型
一个布尔型数据用来存放逻辑值（布尔值）。布尔型的值只有两个：false和true，并且false的序号是0，true的序号是1。false 和true都是预定义常数表识符，分别表示逻辑假和逻辑真。并且true4.字符型
　　
字符型用char作为表识符。字符型必须用单引号括起来，字母作为字符型时，大小写是不等价的，并且字符型只允许单引号中有一个字符，否则就是字符串。
2.4 常量与变量
1.常量
(1)常量：在某个程序的整个过程中其值不变的量。
(2)常量定义：常量定义出现在说明部分。它的语法格式是：
const
<常量标识符>=<常量>;
...
<常量标识符>=<常量>;
常量表识符的类型由定义它的常量的类型决定。例如：const a=12 隐含说明a是整型；const r=3.21 隐含说明r是实型......
(3)常量定义部分必须以保留字const开头，可以包含一个或几个常量定义，而且每个常量均以分号结束。
(4)Turbo Pascal类型常量
类型常量，又称变量常数，它是Turbo Pascal的一个扩充特性。类型常量的定义与标准Pascal规定的常数定义和变量说明有所区别。类型常量定义的语法格式：
const
<简单类型常量标识符>:简单类型=常数；
例如：
[Copy to clipboard]
CODE:
const
counter:integer=0;
flag:boolean=true;
index:0..100=0;
2.变量
(1)变量：在某个程序中的运行过程中其值可以发生改变的量
(2)变量说明：变脸说明出现在说明部分。它的语法格式是：
var
<变量标识符列表>:<类型>;
...
<变量标识符列表>:<类型>;
其中，保留字var表示开始一个变量说明部分。变量标识符列表是一个用逗号隔开的标识符序列，冒号后面的类型是类型标识符。每个变量说明均以分号结束。
例如：
[Copy to clipboard]
CODE:
var
a,b,c:integer;
m,n:real;
2.5　标准函数
1.算术函数
函数标识符
自变量类型
意义
结果类型
abs
整型、实型
绝对值
同自变量
arctan
整型、实型
反正切
实型
cos
整型、实型
余弦
实型
exp
整型、实型
指数
实型
frac
整型、实型
小数部分
实型
int
整型、实型
整数部分
实型
ln
整型、实型
自然对数
实型
pi
无自变量
圆周率
实型
sin
整型、实型
正弦
实型
sqr
整型、实型
平方
同自变量
sqrt
整型、实型
平方根
实型
例：
[Copy to clipboard]
CODE:
abs(-4)=4
abs(-7.49)=7.49
arctan(0)=0.0
sin(pi)=0.0
cos(pi)=-1.0
frac(-3.71)=-0.71
int(-3.71)=-3.0
sqr(4)=16
sqrt(4)=2
2.标量函数
函数标识符
自变量类型
意义
结果类型
odd
整型
判断奇数
布尔型
pred
离散类型
求前趋
同自变量
succ
离散类型
求后继
同自变量
例：
[Copy to clipboard]
CODE:
odd(1000)=false
odd(3)true
pred(2000)=1999
succ(2000)=2001
pred(＇x＇)=＇w＇
succ(＇x＇)=＇y＇
3.转换函数
函数标识符
自变量类型
意义
结果类型
chr
byte型
自量对应的字符
字符型
ord
离散类型
自量对应的序号
longint
round
实型
四舍五入
longint
trunc
实型
截断取整
longint
4.杂类函数
函数标识符
自变量类型
意义
结果类型
random
无自变量
[0,1)之间的随机实数
real
random
word
[0,自变量)之间的随机整数
wird
randomize
无自变量
用一随机值初始化内部随机数产生器
longint
upcase
字符型
使小写英文字母变为大写
字符型
2.6　运算符和表达式
1.运算符和优先级
(1)运算符
a.算术运算符 运算符
运算
运算对象
结果类型
+
加
整型、实型
只要有一个运算对象是实型，结果就是实型，如果全部的运算对象都是整型并且运算不是除法，则结果为整型，若运算是除法，则结果是实型
-
减
整型、实型
*
乘
整型、实型
/
除
整型、实型
div
整除
整型
整型
mod
取余
整型
整型
b.逻辑运算符
运算符
运算
运算对象
结果类型
not
逻辑非
布尔型
布尔型
and
逻辑与
布尔型
布尔型
or
逻辑或
布尔型
布尔型
xor
逻辑异或
布尔型
布尔型
c.关系运算符
运算符
运算
运算对象
结果类型
=
等于
简单类型
布尔型
<>
不等于
简单类型
布尔型
<
小于
简单类型
布尔型
>
大于
简单类型
布尔型
<=
小于等于
简单类型
布尔型
>=
大于等于
简单类型
布尔型
(2)优先级
运算符
优先级
not
1(高）
*,/,div,mod,and
2
xor,+,-,or
3
in,=,<>,>=,<=,<>
4（低）
2.表达式
(1)算术表达式：算术表达式是由算术运算符连接常量、变量、函数的式子。算术表达式中各个运算符的次序为： ( )-->函数-->*,/,div,mod-->+,1
(2)布尔表达式：Turbo Pascal提供给布尔表达式以下基本操作：逻辑运算和关系运算。下载地址：
C语言版：http://www.writely.com/View docid=dgh688m_292t6m
Pacal语言版：http://www.writely.com/View docid=dgh688m_7cz38ht
参考答案：http://www.writely.com/View docid=dgh688m_8dks9j7
注意：本次比赛的两种试题的C语言版为OI商店官方发布。Pascal语言版为非OI商店的人士友情翻译。所以OI商店不对Pascal语言版负责，如两个版本出现冲突以C语言为准。
提交方式：如果您能在10月6日14:00前做完这套题，请把您的答案通过短信发给我（请注明您做的是哪一套题），我会亲自帮您改卷。如果在这之后做完请参考标准答案自行改卷。标准答案会在10月7日发布。陈启峰Size Balanced Tree中文版
叶子我没有找到陈启峰的中文版……（也许是自己无能吧……）于是花了两天的闲工夫，把他的英文版论文翻译成了中文，里面的一些图片重新编辑了一下，发了上来，大牛们和陈启峰本人也不要鄙视，就可以了，主要也是为了丰富我自己的博客。noi 2005官方(hwd)的标程+数据生成器.
hwd给的
我把数据去掉了
http://adn.cn/noi2005/noi2005.rar只写了4道题……剩下一道回头有空补上
顺便说一下
这应该是近期我在OIBH的最后一贴了
以后应该很少会上，即使上了也是潜水或者搜搜贴
下一贴可能就是保送后了
这次省选挂得比较惨
最后三个月，一次APIO一次NOI
无论如何，既然有机会，就一定要努力。
但是，这不是退役宣言……
以后如果有什么事可以qq上留言或者发邮件
OIBH，暂时再见吧
[update]
发现《分割矩阵》的时间复杂度分析出了一个低级错误
现已更正[SGU资源]
SGU地址
http://acm.sgu.ru
题目包
见冷心渡月的置顶帖
http://www.oibh.org/bbs/viewthread.php tid=2428&fpage=1
国家集训队SGU表格
http://www./upload/IOITrain/IOITrain2004.4.SGU.Ural.rar
(内含n位大牛的表格和周天皇的程序，强烈推荐)noip2006解题报告［绝对原创］
　　消耗了一个星期的是时间，躲过了班主任的眼睛，呵呵，终于完成的了０６的解题报告
呵呵．．．
　　本人的处女作了，也是对论坛的第一次贡献吧．．．．
　　　　　　
　　由于附件不能上传．．只能贴了．．呵呵
能量项链
本题是一道很经典的dp题目，其实质就是“石子合并问题”的变形，有谈不上什么变形，倒不如说复制更好一点。我想很多的牛人在这个题目失分的原因多为没弄懂题目的意思就下手做了，把题目看简单了。
简单的说：给你一项链，项链上有n颗珠子。相邻的两颗珠子可以合并(两个合并成一个)。合并的同时会放出一定的能量。不同的珠子的合并所释放的能量是不同的。问：按照怎样的次序合并才能使释放的能量最多？
　　我们用top表示第i颗珠子的头标记，用wei表示第i颗珠子的尾标记，合并两颗相邻珠子所释放的能量是：
　　Q=top*wei*wei[i+1]或top*top[i+1]*wei[i+1]; （一个样的）
　　合并不一定按顺序的，本题所提供的样例也是导致出错的一大原因。
　　n个珠子进行一次合并的后，就归结到了n-1个珠子的合并的问题。所以我们想到了动态规划。
　　既然是dp题目，必然要满足dp的两大条件：、
　　1.最优子结构性质；
　　设Q[i,j]表示第i颗珠子到第j颗珠子合并所产生的能量。显然Q[1,n]表示的是合并产生的总的能量。给定一种标号方法，maxQ[1,n]就是所要求的。设最后一次合并在k处进行，则有Q[1,n]＝Q[1,k]＋Q[k+1,n]＋top[1]*wei[k]*wei[n]。要Q[1,n]最大，必然要Q[1,k]，Q[k+1,n]最大。
　　证明：假设Q[1,k]不是最大，则必然存在一Q'[1,k]>Q[1,k]。
那么就有Q'[1,n]＝Q'[1,k]＋Q[k+1,n]＋top[1]*wei[k]*wei[n]>Q[1,k]。这与Q[1,n]的最优性矛盾。
　　最优子结构性质得证。
2.无后效性；
　　 无后效性是显然的，进行某次合并，合并前与合并后状态是相对独立，不相关联，互不影响的。
　　
　　算法已经定了下来了，关键是怎么实现了。
　　项链是一个环，而我们处理是对一个串进行的。所以我们要把项链从某处割断展开，不同处的割断对应着不同的展开方法，也就是对应着不同的标号方法。产生的maxQ[1,n]也就不同的。所以我们要对这些maxQ[1,n]进行打擂，取其最大的一个，即为解了。
dp的转移方程是：
Best=maxQ[1,n] 1<=i<=n (i表示从第i颗珠子处展开，顺次标号）；
Q[i,j]=max{Q[i,k]+Q[k+1,j]+top*wei[k]*wei[j] 1<=i<=k其中Q[i,i]=0 1<=i<=n;
dp的时间复杂度为O(n^3)，n种的展开方法对应需要n次的dp，所以时间复杂度为O(n^4)。空间为O(n^2)。
显然O(n^4)过这个题目是有点欠缺的，对的大的数据貌似很容易超时的。
　　如果仔细想想，我们还是做了很不重复的工作的，不同的展开方式中必然存在着很多的大量的重复运算。于是还有很大的优化空间，既然展开做了很多的重复的工作，那么就合并起来吧。回到起点，开始的时候为什么我们要对项链做n次的展开呢，基于我们在运算的时候不能够实现第一颗珠子与第n颗珠子的相邻性。为了一次dp就实现所以的的珠子的相邻性，我们做如下处理：
　　　　a[1],a[2],a[3]...a[n],a[1],a[2]...a[n-1]　
（原来的）　 （延伸的）
　　也就是：
　　　　a[1],a[2],a[3]...a[n],a[n+1],a[n+2]...a[m]　　　
　　显然m=2n-1;
　我们对这一串珠子dp一次即可得解；dp方程为：
　　　Best=max{Q[i,i+n-1] 1<=i<=n}
　Q[i,j]=max{Q[i,k]+Q[k+1,j]+top*wei[k]*wei[j] 1<=i<=k其中Q[i,i]=0 1<=i<=m;
显然时间复杂度为O(n^3)，空间为O(n^2)。min(i+n-1,m)已经对dp进行了优化。
　　（附程序）
　　到这里我们可以很完美的过这个题目的所以数据了；但还是觉得不够快，想用四边形优化，但想了想显然是不可以的，W函数不是单调的。
　　用树的知识可以更多的优化为（O(n^2*log2n)）。这里就不多说了，写起来挺烦的。
program Qi(inout,output);
var
n,m:integer;
top,wei:array[1..200] of integer;
f:array[1..200,1..200] of longint;
procedure init;
var
i:integer;
begin
readln(n);
for i:=1 to n do read(top);
readln;
for i:=1 to n-1 do wei:=top[i+1];
wei[n]:=top[1];
m:=n*2-1;
for i:=n+1 to m do begin top:=top[i-n]; wei:=wei[i-n]; end;
end;
procedure doit;
var
p,i,j,k:integer;
begin
fillchar(f,sizeof(f),0);
for p:=1 to n-1 do
for i:=1 to m-1 do
begin
j:=i+p;
if j>m then break;
for k:=i to j-1 do
if f[i,j]then f[i,j]:=f[i,k]+f[k+1,j]+top*wei[k]*wei[j]
end;
end;
procedure print;
var
i:integer; best:longint;
begin
best:=0;
for i:=1 to n do
if bestwriteln(best);
end;
begin
init;
doit;
print;
end.
金明的预算方案
　　如果看过普及组试卷就会发现，对应的第二个题目，也是一个样的背景，提高组只是多了个“主件附件”的的关系，如果去掉这一点，就全没区别了。也就成了经典的背包问题了。也就是多了这么一点，考试的时候就晕了。不知道怎么做了。后来才发现是个很简单的dp题目。可惜我当时没做出来。
　　草率的审题，可能会得到这样的算法：dp，对每一个物品做两种决策，取与不取。如果取，满足两个条件：1.要么它是主件，要么它所属的主件已经在包里了。2.放进去后的重要度与价格的成绩的总和要比没放进时的大。这两个条件缺一不可的。于是呼，得到如下的动规方程：
　　　f[i,j]:=f[i-1,j];
if (i为主件or i的附件在包中）and (f[i,j]then f[i,j]:=f[i,j-v]+v*w;
　　我们来分析一下复杂度，空间：dp的阶段为n^2,对与每一个阶段都要记录该状态下在包中的物品有哪些（因为要确定附件的主件是否在包中)，每个阶段的记录都要O(n)的空间，所以总的就是O(n^3)。时间，一个dp，n^2的外层循环，内部用布尔量加个主附件的对应数组，为O(1)，和起来就为O(n^2)的复杂度。
　　可以看的出，时间的需求为32000*60，不成问题。空间32000*60*60，大约要7.5M的空间，在64M的要求下是完全可以的过的。如果用上题目中的一个很隐秘的条件：“每件物品都是10元的整数倍”，就可以把速度在提高十倍。
　　细细的看题目，还一个很重要的条件我们还没用：“每个主件可以有０个，１个或２个附件”。这貌似不起眼的一句话，却给我们降低复杂度提供了条件。想一想，为什么题目要对附件的个数做限制呢，明显是在降低难度。
　　对于一套物品（包含主件，所以的附件），我们称为一个属类，对一个属类的物品的购买方法，有以下５种：
　　　　１.一个都不买
　　　　２.主件
　　　　３.主件＋附件１
　　　　４.主件＋附件２
　　　　５.主件＋附件１＋附件２
　　这五种购买方法也是唯一的五种方法，也就是说对一属类的物品，我们只有上述的５种购买方法。
　　于是我们很自然的就会想到把物品按物品的属类捆在一起考虑。这样我们把物品的属类作为dp的状态。可以得到如下的dp方程：
　　f[i,j]=max{f[i-1,j];
f[i-1,j-v[i,0]]+v[i,0]*w[i,0];
f[i-1,j-v[i,0]-v[i,1]]+v[i,0]*w[i,0]+v[i,1]*w[i,1];
f[i-1,j-v[i,0]-v[i,2]]+v[i,0]*w[i,0]+v[i,2]*w[i,2];
f[i-1,j-v[i,0]-v[i,1]-v[i,2]]+v[i,0]*w[i,0]+v[i,1]*w[i,1]+v[i,2]*w[i,2];}
很显然时间复杂度为O(n^2)，空间复杂度为O(n^2)，加上利用“每件物品都是10元的整数倍”除以10的优化，本题就很完美的解决了。
　　（附程序）；
program Qi(input,output);
type
node=record
u:integer;
v:array[0..2] of integer;
p:array[0..2] of integer;
end;
var
n,m,k:integer;
w:array[1..60] of node;
f:array[0..60,0..3200] of longint;
g:array[1..60] of integer;
procedure init;
var
i,j:integer;
vx,px,qx:array[1..60] of integer;
begin
readln(n,m); k:=0;
for i:=1 to m do
begin
readln(vx,px,qx);
if qx=0
then begin
k:=k+1; g:=k;
with w[k] do
begin
u:=0;
v[0]:=vx; p[0]:=px;
for j:=1 to 2 do begin v[j]:=0; p[j]:=0; end;
end;
end;
end;
for i:=1 to m do
if qx<>0
then begin
with w[g[qx]] do
begin
u:=u+1;
v:=vx; p:=px;
end;
end;
for i:=1 to k do
with w do
begin
for j:=0 to 2 do write('(',v[j],',',p[j],') ');
writeln;
end;
end;
procedure doit;
var
i,j:integer;
begin
fillchar(f,sizeof(f),0);
for i:=1 to k do
with w do
begin
for j:=1 to n do
begin
f[i,j]:=f[i-1,j];
if (j>=v[0]) and (f[i,j]then f[i,j]:=f[i-1,j-v[0]]+v[0]*p[0];
if (j>=v[0]+v[1]) and (f[i,j]then f[i,j]:=f[i-1,j-v[0]-v[1]]+v[0]*p[0]+v[1]*p[1];
if (j>=v[0]+v[2]) and (f[i,j]then f[i,j]:=f[i-1,j-v[0]-v[2]]+v[0]*p[0]+v[2]*p[2];
if (j>=v[0]+v[1]+v[2]) and (f[i,j]then f[i,j]:=f[i-1,j-v[0]-v[1]-v[2]]+v[0]*p[0]+v[1]*p[1]+v[2]*p[2];
end;
end;
end;
procedure print;
begin
writeln(f[k,n]);
end;
begin
init;
doit;
print;
end.
作业调度方案
　　对本题的评价：题目超长，超简单，失分率最高。
　　当我在考场上拿到这个题目的时候，考试的紧张的气氛压抑着……读了一遍，不知所云，又读了一遍，依然莫名其妙，读第三便，I give up !!!考试回来，一看，这样的题目竟然不会，一定是气的死去活来，我就是这样郁闷了整整的一个月的。
　　超简单的贪心算法。
　　简单的说：有n个工件要在m个机器上加工，每个工件都有m到工序，每个工序对应着相应的加工机器。一个工件的工序必须依次进行。同一台机器同时只能加工一个工件。每个工件的每个工序需要一定的加工时间。问：加工完所有的工件需要的最少时间是多少？
　　本题在题目中连算法都给出了，考察的是对题意的理解和数据结构，但本题的规模并没有对数据结构做过高的要求。应该可以说是本次考试的最简单的题目了，但不是送分题，很多人和我一样都望而止步了。
　　最简单，按部就班就可以了。
　　下面是题目中给我们的详尽算法：
　　“当一个操作插入到某台机器的某个空档时（机器上最后的尚未安排操作的部分也可以看作一个空档），可以靠前插入，也可以靠后或居中插入。为了使问题简单一些，我们约定：在保证约束条件（1）（2）的条件下，尽量靠前插入。并且，我们还约定，如果有多个空档可以插入，就在保证约束条件（1）（2）的条件下，插入到最前面的一个空档。”
　　建议大家在考试的时候使用数组，平时可以用指针写一写……
　　（附程序）；
program Qi(input,output);
var
m,n:integer;
a:array[1..400] of integer;
f:array[1..20,0..1000] of boolean;
wu,ti:array[1..20,1..20] of integer;
g,time:array[1..20] of integer;
procedure init;
var
i,j:integer;
begin
readln(m,n);
for i:=1 to n*m do read(a);
readln;
for i:=1 to n do
begin
for j:=1 to m do read(wu[i,j]);
readln;
end;
for i:=1 to n do
begin
for j:=1 to m do read(ti[i,j]);
readln;
end;
end;
procedure doit;
var
i,j,k,xtime:integer;
begin
fillchar(f,sizeof(f),true);
fillchar(time,sizeof(time),0);
fillchar(g,sizeof(g),0);
for i:=1 to n*m do
begin
inc(g[a]); j:=time[a]+1;
xtime:=0;
while xtimebegin
if f[wu[a,g[a]],j]
then inc(xtime)
else xtime:=0;
j:=j+1;
end;
time[a]:=j-1;
for k:=j-xtime to j-1 do f[wu[a,g[a]],k]:=false;
end;
end;
procedure print;
var
i,j,best:integer;
begin
best:=0;
for i:=1 to m do
for j:=1000 downto 0 do
if not f[i,j] then
begin
if bestbreak;
end;
writeln(best);
end;
begin
init;
doit;
print;
end.
备注：不知道为什么第6个数据我的答案是112.而提供的答案是116..
如果有错...欢迎牛人指出....呵呵.(我的qq:418539455);
备注：
2k进制数
　　这就是传说中的数学题吗 考试前曾沸沸扬扬的流传过这么一段：“今年的题目出于一数学教授，都是写超难的题目，四个题目有三个是数学题。”再加上今年的maths库函数登上历史舞台。更让人深信不移：今年要考数学题。
　　谣言不可信啊，冤死了多少牛们……
　　说本题是数学题，到不如说是个找规律的题目。
　　我们还是用标准的数学方法做一下好了。本题其实就是个很简单的组合数学问题。没上过高三做不出也就算了，上过高三的牛们没做出来，多为放弃的了。
　　从题中可以看出，w的值限制着首位的取值。所以我们要对与特殊考虑。比如样例中的w=7，就限制了首位只能取０和１。下面关心的就是位数的问题了，w决定了数的最大的位数，最少的位数要求是２位。k决定了数的位权。
　　抽象的是说了半天也不说不清楚，举个例子吧：就拿样例说，k=3。所以位权是2^k=8，w=7，决定了数的位数最大是３｛w div k+1｝，最多位的数是最高位最大只能是１｛2^((w+1) mod k-1)-1｝。所以我们分两种做讨论：1.位数是最多位，2.位数小于最多位。
　　1.位数为最多位（最多位为３）；
　　最高位位１：后面的两位只能在２－７之间取两个不同的数。显然取法的种数为c[2,6]。{c[n,m]=m!/(n!*(m-n)!)，就是组合数}
　　……　……
　　　　｛这里的最高位只能为１，所以只讨论一种情况｝。
　　2.位数小于最多位。
　　２位：这两位只能从１－７之间取数，为c[2,7]。
　　……　……
　　｛这里只有两位的情况，所以只讨论这一种情况｝。
　　从上面的例子，我们可以看出一般的情况：
　　位权：n=2^k。　位数：l=w div k+1;｛当w mod k=0时，最高为最大为０，结合下｝
　　最高位最大值：2^((w+1) mod k-1)-1。
　　　　｛这是我们要知道的几个基本的元素｝
　　下面就是统计满足的数的个数：
　　1.位数为最多：
　　　　最高为取值x (2<=x<=mhigh);
对于给定最高位x都有一些L位满足条件的数，这些数的个数为c[l-1,n-x-1]。
２：位数小于最多：
对于每一个给定的w位数都对应着c[w,n-1]个满足条件的数。
把这些数的个数全部加起来就可以了。
为了简化算法，我们引进一个组合公式：
　　c[n,m]=c[n-1,m-1]+c[n,m-1]; 其中c[n,m]=m!/(n!*(m-n)!
如果不用高精度，int64可以过７个点，高精度就可以全过了。
(附程序);
program Qi(input,output);
var
k,w,n,l,mhigh:integer;
answer:array[1..200] of integer;
c:array[1..512,1..512,1..100] of integer;
procedure init;
begin
readln(k,w);
end;
procedure ready;
var
i,j,l,jin,s:integer;
begin
for i:=1 to 512 do c[1,i,1]:=i;
for i:=2 to 512 do
begin
for j:=2 to i do
begin
jin:=0;
for l:=1 to 100 do
begin
s:=c[j-1,i-1,l]+c[j,i-1,l]+jin;
c[j,i,l]:=s mod 10;
jin:=s div 10;
end;
end;
end;
end;
procedure plus(n,m:integer);
var
i,jin,s:integer;
begin
jin:=0;
for i:=1 to 100 do
begin
s:=answer+c[n,m,i]+jin;
jin:=s div 10;
answer:=s mod 10;
end;
end;
procedure doit;
var
i:integer;
begin
ready;
n:=1;
for i:=1 to k do n:=n*2;
n:=n-1;
l:=w div k+1;
mhigh:=1;
for i:=1 to (w+1) mod k-1 do mhigh:=mhigh*2;
mhigh:=mhigh-1;
for i:=2 to l-1 do if i<=n then plus(i,n);
for i:=1 to mhigh do if l-1<=n-i then plus(l-1,n-i);
end;
procedure print;
var
i,j:integer;
begin
j:=100;
while answer[j]=0 do j:=j-1;
for i:=j downto 1 do write(answer);
writeln;
end;
begin
init;
doit;
print;
end.
申请加精！！！！！第二题 理想的正方形（square.pas/square.c)
有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。
输入文件square.in
第一行为3个整数，分别表示a,b,n的值
第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。
输出文件square.out
仅一个整数，为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值。
样例输入
5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
样例输出
1
问题规模
（1）矩阵中的所有数都不超过1,000,000,000
（2）20%的数据2<=a,b<=100,n<=a,n<=b,n<=10
（3）100%的数据2<=a,b<=1000,n<=a,n<=b,n<=100
【算法简析】
问题的规模相当大，O(abn)的算法都会超时，所以只能考虑O(ablogn)或者O(ab)的算法。
下面介绍O(ab)的算法：利用单调队列。
本题中枚举是必不可少的，而且最坏只能是O(ab)的，所以必须为这个O(ab)的枚举计算一些状态，即以(i,j)为左上角的n×n的正方形区域中的最大值和最小值。把这个二维的问题化简成一维，就是以(i,j)为左边的长度为n的序列的最大值max[i,j]和最小值min[i,j]，然后用同样的推算方法可以由这个一维的状态可以推算出二维的状态。现在我们的任务就是在O(b)的时间内计算出一行的max[i]和min[i]。这就需要借助单调队列了。
开两个队列，一个维护最大值，一个维护最小值。为了方便叙述，下文只讨论最大队，最小队的维护方式类似。
我们要保证队列中各个元素大小单调递减（注意，不是单调不上升），各个元素的下标单调递增。这样才可以保证队首元素最大，而且更新的时候队首永远是当前最大。因此，需要改造一下队列，让它变成能在两头删除，在队尾插入。
为了保证单调性，每次插入的时候，先判断队尾元素，如果不比待插入元素大就删除，不断删除队尾直到队尾元素大于待插入元素或者队空。删除的时候，判断队首，如果队首元素下标小于当前段左边界就删除，不断删除队首直到队首元素下标大于等于当前段左边界（注意：这时队列肯定不为空），队首元素就是当前段的最优解。
有了单调队列，计算max[i]和min[i]就方便了。初始的时候分别把当前行前n-1个元素插入队尾。从第1列开始，每次取队首最优值，从队首删除无效元素，并将当前列+n-1号元素插入队尾。由于每个元素最多入队出队各一次，时间复杂度就是O(b)。
用相同的方法可以在O(a)时间内根据max[i]和min[i]计算出正方形的最优解，时间复杂度为O(ab)。
附：O(ablogn)的算法可以转化为矩形的RMQ，用二维的Sparse Table解决。( http: / / www.oibh.org / bbs / misc.php action=viewratings&tid=11962&pid=126033" \o "评分 0 )NOIP考前知识大总结
作者：于俊超
ID:MiniDragonXG
2006年11月
数据类型
Type Range Size in bytes
Byte 0 .. 255 1
Shortint -128 .. 127 1
Smallint -32768 .. 32767 2
Word 0 .. 65535 2
Integer either smallint, longint or int64 size 2,4 or 8
Cardinal either word, longword or qword size 2,4 or 8
Longint -2147483648 .. 2147483647 4
Longword 0..4294967295 4
Int64 -9223372036854775808 .. 9223372036854775807 8
QWord 0 .. 18446744073709551615 8
Real 2.9E-39 .. 1.7E38 6
Single 1.5E-45 .. 3.4E38 4
Double 5.0E-324 .. 1.7E308 8
Comp -9.2E18 .. 9.2E18 8
Extended 3.4E-4932 .. 1.1E4932 10
算法思想:
1.搜索 (Search) 枚举(穷举) / 遍历 / 剪枝 / 产生式系统（估价函数）
查找(字典)：折半查找(二分法) / 树形查找(二叉排序树) / Hash
2.归纳 (To 数学方法) > 递推式 > DP (ex: 4 Hanoi Tower Problem)
3.分治 (Divided and Conquer)
4.贪心 (Greedy) 5.模拟
实现技巧: 循环
递推(顺推/倒推) > 博弈 / 动态规划
递归(栈/DFS)
滚动数组
幂：
x ^ y = exp(y*ln(x))
x ^ (1/n) = exp(1/n*ln(x))
math单元里的Power
数学方法:
1.数论: 质数 / 因数 / 约数个数（种数）/ 最大公约数 / 最小公倍数 / 回文数....
2.进制转换 注意负进制
3.高精度运算 (int64...)
4.排列组合: 全排列
5.经典递推关系:
Fibonacci: fib(n)=fib(n-1)+fib(n-2)
fib(1)=1 fib(2)=1
通项： 设g5=sqrt(5) 则fib(n)=(1/g5)*( ((1+g5)/2)^n-((1-g5)/2)^n )
f(n)=a1*f(n-1)+a2*f(n-2)+....+ak*f(n-k) (ai<>0 & n>k)叫
k阶常系数线性齐次递推关系
可以利用矩阵性质和快速幂在O(logn)内求解
错位排列: F(1)=0 F(2)=1
Fn=(x-1) * (Fn-1 +Fn-2)
Catalan数: Catalan(n)=C(n,2*n)/(n+1)
第二类Stirling数 s(n,k)= { s(n-1,k-1)+k*s(n-1,k) } (n>k>=1)
6.高斯消元
数据结构(Data Structure):
1.物理结构:
I: 数组 > 二维平面/字符串(Ansistring)及其操作
II: 指针 > 链表 （单链表 / 双向链表 / 环状链表）
抽象数据类型(Abstract Data Type)
2.初级ADT:
I: 集合
II: 线性结构
A: 栈(stack)
(LIFO) operation: push/pop
a: 后缀表达式
b: 进出站序列问题(Catalan 枚举 > 归纳)
c: 栈优化最长不下降(上升)序列
B: 队列(queue) > 循环队列
(FIFO) operation: push/pop
a: 广度优先搜索
b: 求和广义线性表
C: 字典 Dictionary
III: 非线性结构
A: 树Tree (二叉树Binary Tree)
树的遍历：前序/中序/后序 (递归)
最优二叉树(哈夫曼树Huffman tree）（贪心）
树形DP
B: 图Graph
a: 图的遍历:
Depth first Search (DFS / 回溯 / 递归)
Breadth first Search (BFS / 队列 / FloodFill 种子染色法 )
b: 最小生成树：（贪心）
Prim: 边集密
Kruskal: 边集疏（排序 + 并查集）
c: 最短路径
Dijkstra（ 单源 O(n^2) BFS ）
Floyed（ 所有点间 O(n^3) ）
Bellman-Ford（负权环）
d: 拓扑序列
e: 关键路径（AOV网）
f: 无向图传递闭包
有向图强连通分量SCC
(Strong Connected Component)
g: 路与回路
欧拉路(Euler Route)所有边
哈密尔顿路(Hamilton Route)所有点
h: 割顶和桥
去除之后图变得不连通的顶点和边
3.高级ADT:
I: 集合型
A: 并查集(disjoint-set)
operation: Find/Union/Insert
II: 字典型
哈希表(Hash) 哈希函数
opertaion: Find/Insert
III: 树型
A: 二叉堆(Heap) > Treap
operation: Insert/Delete(Pop)/GetMax/GetMin
B: Binary Search Tree(BST)
C: 平衡二叉树......
排序算法:
复杂度 思路 Insert Choose Exchange
O(n^2) 直接插入排序 直接选择排序 冒泡排序
(Inserting Sort) (Choosing Sort) (Bubble Sort)
O(nlogn) 希尔排序 堆排序 快速排序 归并
(Shell Sort) (Heap Sort) (Quick Sort) (Merge Sort)
O(n) 计数排序 桶排序 基数排序
(Counting Sort) (Bucket Sort) (Radix Sort)
Quick Sort: 分治
Merge Sort: 分治
Bucket Sort: 哈希表
Heap Sort: 堆
还有二叉排序树..........
动态规划(Dynamic programming)
=记忆化搜索+用Table记录免去重复计算
（解决 满足具有最优子结构 且 无后效性）
1.状态转移方程+边界条件
2.合适的实现方法(To 实现技巧)
3.要掌握最经典的动规题目
a: 最长不下降(上升)序列
b: 最大子段和 & 最大M子段和
c: 最长公共子序列(LCS)
d: 石子合并（链，环）
e: 背包问题
01背包-可重复(DP)
01背包-不可重复(DP)
部分背包(贪心)
博弈问题：
关键字：必胜态 / 必败态
2. 递推找规律
3. 归纳
计算几何
三角形面积 s=|x1y2+x2y3+x3y1-x3y2-x2y1-x1y3|
二维仿射变换 反射 / 镜像 / 旋转
计算二维凸包……这东西我直接听不懂……
网络流 & 匹配（二分图） & 线段树 & 树状数组 & NP完全 ……
∵九成不考 ∴略……
Copyright 2006 By MiniDragonXG. All rights reserved.PAGE
Size Balanced Tree
陈启峰 (Farmer John)
中国广东纪念中学
Email:344368722@
2006.12.29
摘要
这篇论文将展现一个独特巧妙的策略，动态地维护二叉搜索树（Binay Search Trees，缩写为BST），并且它在最坏的情况下也有着良好的期望运行速度。Size Balanced Tree，顾名思义，这是一棵通过大小（Size）域来维持平衡的二叉搜索树。
这是一种简单、高效并且在各方面都通用的数据结构。
这也是一种很容易被语言工具表述的数据结构，它有着简单明了的定义，和令人惊叹的运行速度，而且你会惊讶于它简单的证明。
这是目前为止速度最快的高级二叉搜索树[1]]。
此外，它比其它一些知名的高级二叉搜索树要快得多，并且在实践中趋于完美。
它不仅支持典型的二叉搜索树操作，而且也支持Select和Rank。
关键字
Size Balanced Tree
SBT
Maintain
翻译 By 竹子的叶子
文档经过处理，可以使用“视图”——“文档结构图”来方便阅读。
希望大家不要随便修改，谢谢！
1 介绍
在展现Size Balanced Tree之前，有必要详细说明一下二叉搜索树的旋转，左旋（Left-Ratote）和右旋（Right-Ratote）。
1.1 二叉搜索树
二叉搜索树是一种非常重要的高级数据结构，它支持很多动态操作，其中包括搜索（Search），取小（Minimum），取大（Maximun），前驱（Predecessor），后继（Successor），插入（Insert）和删除（Delete）。它能够同时被当作字典和优先队列使用。
二叉搜索树是按照二叉树结构来组织的，树中的每个节点最多只有两个儿子，二叉搜索树中关键字的储存方式总是满足以下二叉搜索树的性质：
设x是二叉搜索树中的一个结点，那么x的关键字不小于左子树中的关键字，并且不大于右子树中的关键字。
对于每一个结点t，我们使用left[t]和right[t]来储存它两个儿子的指针[2]，并且我们定义key[t]来表示结点t用来做比较的值。另外，我们增加s[t]，表示以t为根的子树的大小（Size），维持它成为这棵树上结点的个数。特别地，当我们使用0时，指针指向一棵空树，并且s[0]=0。
1.2 旋转
为了保持二叉搜索树的平衡（而不是退化成为链表），我们通常通过旋转改变指针结构，从而改变这种情况。并且，这种旋转是一种可以保持二叉搜索树特性的本地运算[3]。
图 1.1
图 1.1：左旋Left-Ratote(x)操作通过更改两个常数指针将左边两个结点的结构转变成右边的结构，右边的结构也可以通过相反的操作Right-Ratote(x)来转变成左边的结构。
1.2.1 右旋的伪代码
右旋操作假定左儿子存在。
Right-Rotate(t)
1 k ← left[t]
2 left[t] ← right[k]
3 right[k] ← t
4 s[k] ← s[t]
5 s[t] ← s[left[t]] + s[right[t]] + 1
6 t ← k
1.2.2 左旋的伪代码
左旋操作假定右儿子存在。
Left-Rotate (t)
1 k ← right[t]
2 right[t] ← left[k]
3 left[k] ← t
4 s[k] ← s[t]
5 s[t] ← s[left[t]] + s[right[t]] + 1
6 t ← k
2 Size Balanced Tree
Size Balanced Tree（SBT）是一种通过大小（Size）域来保持平衡的二叉搜索树。它支持许多运算时间级别为O(logn)的主要操作：
Insert(t,v) 在以t为根的SBT中插入一个关键字为v的结点。
Delete(t,v) 从以t为根的SBT中删除一个关键字为v的结点，如果树中没有一个这样的结点，删除搜索到的最后一个结点。
Find(t,v) 查找并返回结点关键字为v的结点。
Rank(t,v) 返回v在以t为根的树中的排名，也就是比v小的那棵树的大小（Size）加一。
Select(t,k) 返回在第k位置上的结点。显然它包括了取大（Maximum）和取小（Minimun），取大等价于Select(t,1)，取小等价于Select(t,s[t])。
Pred(t,v) 返回比v小的最大的数。
Succ(t,v) 返回比v大的最小的数。
通常SBT的每一个结点包含key，left，right和size等域。size是一个额外但是十分有用的数据域，它一直在更新，它在前面已经定义了。
每一个在SBT中的结点t，我们保证：
性质a：
性质b：
图 2.1
图2.1：结点L和R分别是结点T的左右儿子。子树A、B、C和D分别是结点L和R各自的左右子树。
符合性质a和性质b，
3 Maintain
如果我们要在一个BST插入一个关键字为v的结点，通常我们使用下列过程来完成任务。
Simple-Insert (t,v)
1 If t=0 then
2 t ← NEW-NODE(v)
3 Else
4 s[t] ← s[t]+1
5 If v6 Simple-Insert(left[t],v)
7 Else
8 Simple-Insert(right[t],v)
在执行完简单的插入之后，性质a或性质b可能就不满足了，于是我们需要调整SBT。
SBT中最具活力的操作是一个独特的过程，Maintain。
Maintain(t)用来调整以t为根的SBT。假设t的子树在使用之前已经都是SBT。
由于性质a和性质b是对称的，所以我们仅仅详细的讨论性质a。
情况1：
插入后发生正如图2.1，我们可以执行以下的指令来修复SBT。
（1）首先执行Right-Ratote(t)，这个操作让图2.1变成图3.1；
图3.1
图3.1：所有结点的描述都和图2.1一样
（2）在这之后，有时候这棵树还仍然不是一棵SBT，因为或者也是可能发生的。所以就有必要继续调用Maintian(t)。
（3）结点L的右子树有可能被连续调整，因为有可能由于性质的破坏需要再一次运行Maintain(t)。
情况2：
在执行完Insert(left[t],v)后发生，如图3.2，这种调整要比情况1复杂一些。我们可以执行下面的操作来修复。
图3.2
图3.2：除了E、B、F以外，其他结点都和图2.1种的定义一样。E、F是结点B的子树。
（1）在执行完Left-Ratote(L)后，图3.2就会变成下面图3.3那样了。
图3.3
图3.3：所有结点的定义都和图3.2相同
（2）然后执行Right-Ratote(T)，最后的结果就会由图3.3转变成为下面的图3.4。
图3.4
图3.4：所有结点的定义都和图3.2相同
（3）在第（1）步和第（2）步过后，整棵树就变得非常不可预料了。万幸的是，在图3.4中，子树A、E、F和R仍就是SBT，所以我们可以调用Maintain(L)和Maintain(T)来修复结点B的子树。
（4）在第（3）步之后，子树都已经是SBT了，但是在结点B上还可能不满足性质a或性质b，因此我们需要再一次调用Maintain(B)。
情况3：
与情况1正好相反。
情况4：
与情况2正好相反。
3.1 标准Maintain的伪代码
通过前面的分析，很容易写出一个普通的Maintain。
Maintain (t)
1 If s[left[left[t]]>s[right[t]] then
2 Right-Rotate(t)
3 Maintain(right[t])
4 Maintain(t)
5 Exit
6 If s[right[left[t]]>s[right[t]] then
7 Left-Rotate(left[t])
8 Right-Rotate(t)
9 Maintain(left[t])
10 Maintain(right[t])
11 Maintain(t)
12 Exit
13 If s[right[right[t]]>s[left[t]] then
14 Left-Rotate(t)
15 Maintain(left[t])
16 Maintain(t)
17 Exit
18 If s[left[right[t]]>s[left[t]] then
19 Right-Rotate(right[t])
20 Left-Rotate(t)
21 Maintain(left[t])
22 Maintain(right[t])
23 Maintain(t)
3.2 更快更简单的Maintain的伪代码
前面的标准过程的伪代码有一点复杂和缓慢。通常我们可以保证性质a和性质b的满足，因此我们只需要检查情况1和情况2或者情况3和情况4，这样可以提高速度。所以在那种情况下，我们需要增加一个布尔（boolean）型变量，flag，来避免毫无疑义的判断。
如果flag是false，那么检查情况1和情况2；否则检查情况3和情况4。
Maintain (t,flag)
1 If flag=false then
2 If s[left[left[t]]>s[right[t]] then
3 Right-Rotate(t)
4 Else
5 If s[right[left[t]]>s[right[t]] then
6 Left-Rotate(left[t])
7 Right-Rotate(t)
8 Else
9 Exit
10 Else
11 If s[right[right[t]]>s[left[t]] then
12 Left-Rotate(t)
13 Else
14 If s[left[right[t]]>s[left[t]] then
15 Right-Rotate(right[t])
16 Left-Rotate(t)
17 Else
18 Exit
19 Maintain(left[t],false)
20 Maintain(right[t],true)
21 Maintain(t,false)
22 Maintain(t,true)
为什么Maintain(left[t],true)和Maintain(right[t],false)被省略了呢？Maintain操作的运行时间是多少呢？你可以在第6部分 分析 中找到答案。
4 插入
SBT中的插入很简单，下面是SBT中插入的伪代码。
4.1 插入的伪代码
Insert (t,v)
1 If t=0 then
2 t ← NEW-NODE(v)
3 Else
4 s[t] ← s[t]+1
5 If v6 Simple-Insert(left[t],v)
7 Else
8 Simple-Insert(right[t],v)
9 Maintain(t,v≥key[t])
5 删除
我增加了删除的简易程度，如果在SBT中没有这么一个值让我们删除，我们就删除搜索到的最后一个结点，并且记录它。下面是标准删除过程的伪代码。
5.1 删除的伪代码
Delete (t,v)
1 If s[t]≤2 then
2 record ← key[t]
3 t ← left[t]+right[t]
4 Exit
5 s[t] ← s[t]－1
6 If v=key[t] then
7 Delete(left[t],v[t]+1)
8 Key[t] ← record
9 Maintain(t,true)
10 Else
11 If v12 Delete(left[t],v)
13 Else
14 Delete(right[t],v)
15 Maintain(t,v5.2 更快更简单的删除伪代码
实际上这是没有任何其他功能的，最简单的删除。这里的Delete(t,v)是函数，它的返回值是被删除的结点的值。虽然他会破坏SBT的结构，但是使用上面的插入，它还是一棵高度为O(logn*)的BST。这里的n*是所有插入结点的个数，而不是当前结点的个数！
Delete (t,v)
1 s[t] ← s[t]－1
2 If (v=key[t])or(vkey[t])and(right[t]=0) then
3 Delete ← key[t]
4 If (left[t]=0)or(right[t]=0) then
5 t ← left[t]+right[t]
6 Else
7 key[t] ← Delete(left[t],v[t]+1)
8 Else
9 If v10 Delete(left[t],v)
11 Else
12 Delete(right[t],v)
6 分析
很明显，Maintain是一个递归过程，也许你会担心它是否能够停止。其实不用担心，因为已经能够证明Maintain过程的平摊时间时间是O(1)。
6.1 高度分析
设f[h]是高度为h的结点个数最少的SBT的结点个数。则我们有：
6.1.1 证明
（1）易证和。
（2）首先，。
对于每个，设t指向一个高度为h的SBT，然后这个SBT包含一个高度为h-1的子树。不妨设它就是左子树。
通过前面对于f[h]的定义，我们得到。
并且在左子树上有一棵高为h-2的子树，或者说有一棵大小（size）至少为f[h-1]的子树在左子树上。由性质b我们可得。
因此我们得出结论： 。
我们可以构造一个有f[h]个结点的SBT，它的高度是h。我们把这种SBT叫做tree[h]。
因此，宗上二点所述可得：。
6.1.2 最坏高度
实际上f[h]是指数级函数，它的准确值能够被递归的计算。
其中，
一些f[h]的常数值
H 13 15 17 19 21 23 25 27 29 31
F[h] 986 2583 6764 17710 46367 121392 317810 832039 2178308 5702886
定理
一个有n个结点的SBT，它在最坏情况下的高度是满足的最大h。
假设Maxh是有n个结点的SBT的最坏高度，通过上面的定理，我们有
现在可以很清楚地看到SBT的高度是O(logn)。
6.2 分析Maintain
通过前面的结论，我们可以很容易的证明Maintain过程是非常有效的过程。
评价一棵BST时有一个非常重要的值，那就是结点的平均深度。它是通过所有结点深度和除以总结点个数n获得的。通常它会很小，而BST会更小[4]。因为对于每个常数n，我们都期望结点深度和（缩写为SD）尽可能的小。
现在我们的目的是削减结点深度和，而它就是用来约束Maintain的次数[5]。
回顾一下Maintain中执行旋转的条件，会惊奇的发现结点深度和在旋转后总是在减小。
在情况1中，举个例子来说，比较图2.1和图3.1，深度和增加的是一个负数，。再举个例子，比较图3.2和图3.4，深度和增加的值比1小，是。
所以高度为O(logn)的树，深度和总是保持在O(nlogn)。而且在SBT中插入后，深度和仅仅只增加O(logn)。因此
在这里，T是Maintain中旋转的次数。Maintain的执行总次数就是T加上除去旋转的Maintain次数。所以Maintain的平摊运行时间是：
6.3 分析其它操作
现在SBT的高度是O(logn)，Maintain是O(1)，所有主要操作都是O(logn)。
6.4 分析更快更简单的删除
我们声明命题P(n*)，若有一棵已经插入了n*个结点并且有快速简单删除方法的BST，则它的高度为O(logn)[6]。我们通过数学方法来证明，对于任意整数n*，P(n*)都是成立的。
6.4.1 证明
这里我只给出大概的证明。
假设结点t已经被Maintain(t,false)检查过，则有
因此如果一个结点到根的路径上的所有结点都已经被Maintain检查过，那么这个结点的深度就是O(logn)。
（1）对于n*=1，很明显P(n*)是真的；
（2）假设对于P(n*)在n*（3）因此，当n*=1,2,3…时，P(n*)是正确的。
这种方法证明出来的Maintain平摊时间依旧是O(1)。
6.5 分析更快更简单的Maintain
这里讨论有关为什么Maintain(left[t],true)和Maintain(right[t],false)被省略。
在情况1的图3.1[8]中，我们有
因此Maintain(right[t],false)相当于图3.1中的Maintain(T,false)，能够被省略。同样的，Maintain(left[t],true)明显的也不需要。
在情况2的图3.2中，我们有
这些不平衡也意味着E的子树大小要比s[A]小，F的子树大小要比s[R]小。因而Maintain(right[t],false)和Maintain(left[t],true)可以被省略。
7 优点
7.1 SBT跑得快
7.1.2 典型问题
写一个执行n个由输入给定的操作，他们分别是：
在有序集合中插入一个给定的数字；
从有序集合中删除一个给定的数字；
返回一个给定的数字是否在有序集合中；
返回一个给定的数字在有序集合中的排名；
返回有序集合中第k大的数字；
返回有序集合中一个给定数字前面的数字；
返回有序集合中一个给定数字后面的数字。
7.1.2 统计
在现实中，Size Balanced Tree运行优秀，从上面的图表就能看出，同样都在随机数据的情况下，SBT比其它平衡BST要快得多。此外，如果是有序数据，SBT将会是意想不到的快速。它仅仅花费2s就将200万个有序数据结点插入到SBT中。
7.2 SBT运行高效
当Maintain运行的时候平均深度一点也不会增加，因为SBT总是趋近于一个完美的BST。
插入200万个随机值结点
类型 SBT AVL Treap 随机BST Splay 完美的BST
平均深度 19.2415 19.3285 26.5062 25.5303 37.1953 18.9514
高度 24 24 50 53 78 20
旋转次数 1568017 1395900 3993887 3997477 25151532
插入200万个有序值结点
类型 SBT AVL Treap 随机BST Splay 完美的BST
平均深度 18.9514 18.9514 25.6528 26.2860 999999.5 18.9514
高度 20 20 51 53 1999999 20
旋转次数 1999979 1999979 1999985 1999991 0
7.3 SBT调试简单
首先我们可以输入一个简单的BST来保证不会出错，然后我们在插入过程中加入Maintain，并调试。如果发生错误也只需要调试和修改Maintain。此外，SBT不是基于随机性的数据结构，所以它要比Treap，跳跃表（Skip List），随机BST等更稳定。
7.4 SBT书写简单
SBT几乎是和BST同样简单。仅仅在插入过程中有一个附加的Maintain，它也仅仅比BST先旋转[9]。而且Maintain也是同样的相当容易。
7.5 SBT小巧玲珑
许许多多的平衡二叉搜索树，例如SBT，AVL，Treap，红黑树等等都需要额外的域去保持平衡。但是他们中的很多都有着毫无用处的域，像高度（height），随机因子（random factor）和颜色（color）。而相反的是SBT包含一个十分有用的额外域，大小（size）域。通过它我们可以让BST支持选择（Select）操作和排名（Rank）操作。
7.5 SBT用途广泛
现在SBT的高度是O(logn)，即便在最坏情况下我们也可以在O(logn)时间内完成Select过程。但是这一点伸展树（Splay）却不能很好的支持。因为它的高度很容易退化成O(n)。上面的图表已经显示出这一点[10]。
感谢
作者感谢他的英语老师Fiona热情的帮助。
参考
[1] G.M.Adelson-Velskii and E.M.Landis, “An algorithm for the Organization of Information”, Soviet.Mat.Doklady (1962)
[2] L.J.Guibas and R.Sedgewick, “A dichromatic Framework for Balanced Trees”, Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computer Science (1978)
[3] D. D. Sleator and R. E. Tarjan, ‘Self-adjusting binary search trees’, JACM, 32, 652–686 (1985).
[4] S.W.Bent and J.R.Driscoll, Randomly balanced searchtrees. Manuscript (1991).
[5] Raimund Seidel and Cecilia R. Aragony, Randomized Search Trees.(1996).
[6] M.A.Weiss, ‘‘Data Structures and Algorithm Analysis in C++’’, Third Edition, Addison Wesley, 2006.
[7] R.E. Tarjan, ‘‘Sequential access in splay trees takes linear time’’, Combinatorica 5(4), 1985, pp. 367-378.
[8] J. Nievergelt and E. M. Reingold, ‘Binary search trees of bounded balance’, SIAM J. Computing, 2, 33–43 (1973).
[9] K.Mehlhorn, and A.Tsakalidis, “Data Structures,” in Handbook of Theoretical Computer Science, Chapter 6, Vol.A, pp.303–341, Elsevier Science Publishers,(1990)
注释
以下是译者在文章中的注释。
[1] 高级二叉搜索树，Advance Binary Search Tree，或者也可以叫做附加二叉搜索树，都是在BST基础上作了一定改进的数据结构，譬如AVL，Treap，伸展树等。[回去1]
[2] 指针，在本文中作者使用的都是静态指针，也就是数组的下标。[回去2]
[3] 本地运算，local operation，也较原地运算，就是基本不依赖其他附加结构、空间的运算。[回去3]
[4] 原文为：“Generally the less it is, the better a BST is.”[回去4]
[5] 原文为：“Now we need to concentrate on SD. Its significance is the ability to restrict the times of Maintain.”SD是“the sum of the depths of all nodes”，即结点深度和。[回去5]
[6] 原文为：“We call the statement P(n*) that a BST with the faster and simpler Delete and n* standard Inserts is at the height of O(logn*).” [回去6]
[7] 原文为：“For every leaf of this tree, the subtree pointed by it does not be changed by Maintain.” [回去7]
[8] 原文中这里是图3.2，可是情况1中只有图3.1，图3.2是在情况2后面，于是将它改为了“图3.1”。原文为：“In case 1 in Figure 3.2” [回去8]
[9] 原文为：“Removing the only additional Maintain in Insert the former turns to be the latter.” [回去9]
[10] 原文为：“which is exposed by the char above”，其中char个人认为是输入错误，应该是“chart”。[回去10]
例1
[Copy to clipboard]
CODE:
var a:array [1..10] of byte;
begin
fillbyte(a,sizeof(a),3);
end.
其中sizeof(a)=10。结果是a全部为3。
例2
[Copy to clipboard]
CODE:
var a:array [1..10] of shortint;
begin
fillbyte(a,sizeof(a),233);
end.
233=(11101001)2，即fill后每8位的值都是(11101001)补=-106。
例3
[Copy to clipboard]
CODE:
var a:array [1..10] of integer;
begin
fillbyte(a,sizeof(a),2);
end.
2=(00000010)2，即a[ i ]=(0000001000000010)补=514
3、fillword
每2字节赋一次值。如果a数组是int类型（即有正负之分），第三个参数转化为二进制后作为补码。
4、filldword
每4字节赋一次值。如果a数组是int类型（即有正负之分），第三个参数转化为二进制后作为补码。
5、一点问题
在使用fillword/filldword的时候，有时候会出现各种各样奇怪的问题，因此建议大家尽量不要使用。
第一题 上升序列（lis.pas/c/cpp）
对于一个给定的S={a1,a2,a3,…,an},若有P={ax1,ax2,ax3,…,axm},满足(x1任务
给出S序列，给出若干询问。对于第i个询问，求出长度为Li的上升序列，如有多个，求出字典序最小的那个（即首先x1最小，如果不唯一，再看x2最小……），如果不存在长度为Li的上升序列，则打印Impossible.
输入
第一行一个N，表示序列一共有N个元素
第二行N个数，为a1,a2,…,an
第三行一个M，表示询问次数。下面接M行每行一个数Li，表示要询问长度为Li的上升序列。
输出
对于每个询问，如果对应的序列存在，则输出，否则打印Impossible.
样例
lis.in
6
3 4 1 2 3 6
3
6
4
5
lis.out
Impossible
1 2 3 6
Impossible
数据范围
N<=10000
M<=1000
【算法简析】
首先很容易发现，如果Li的长度大于这个序列的LIS的长度，那么一定无解，否则一定有解。为方便讨论，下文只考虑有解情况。
暂且抛开“字典序最小”这个限制条件，即任何长度为Li的上升序列Pi都可以看作符合要求，那么题目的所有要求都可以由LIS来满足。这样我们就可以直接求这个序列的LIS，然后对于所有m次询问，用O(n)的时间输出，这样算法总的时间复杂度就是O(nlogn+nm)。
那么如果要求字典序最小又如何处理呢？其实我们完全可以在相同的时间复杂度内解决问题，只是需要一些转化。
注意到在求LIS的过程中，实际上我们得到的不只是LIS，而是每个数作为子序列末尾的所有最长上升序列。把问题换一个角度，假设我们知道以每个数a[i]作为开头的最长上升序列的长度lis[i]，那么就很容易利用贪心思想构造出答案了。这个贪心成立的前提就是：只要以该元素为开头的LIS的长度大于等于Li，则一定有解。该结论是很显然的。
下面简述贪心的方法：
累加下标j，从左到右扫描序列，如果lis[j]≥Li，则答案序列的第Li个数就是a[j]，并且Li减1。重复上述过程直到Li=0。最后将答案序列倒着输出即可。
这个贪心显然是成立的。由于j是从小到大逐次增加，所以第一个符合lis[j]≥Li的必然就是最优解。每次找到一个符合的元素，所需要的LIS的长度就会减少1。这样重复下去得到的必然是最优解。
由于只需要对序列做一遍扫描，时间复杂度最坏O(n)。构造答案的时间为O(nm)，加上预处理求LIS的O(nlogn)的时间，总时间复杂度为O(nlogn+nm)。
细节：求以a[i]为开头的LIS比较麻烦，可以把序列反过来后求以a[i]为末尾的LDS（Longest Decreasing Subsequence），这样处理起来较方便。
第三题 分割矩阵（separation.pas/c）
将一个a*b的数字矩阵进行如下分割：将原矩阵沿某一条直线分割成两个矩阵，再将生成的两个矩阵继续如此分割（当然也可以只分割其中的一个），这样分割了（n-1)次后，原矩阵被分割成了n个矩阵。（每次分割都只能沿着数字间的缝隙进行）
原矩阵中每一位置上有一个分值，一个矩阵的总分为其所含各位置上分值之和。现在需要把矩阵按上述规则分割成n个矩阵，并使各矩阵总分的均方差最小。
均方差，其中平均值，xi为第i个矩阵的总分。
请编程对给出的矩阵及n，求出均方差的最小值。
输入文件（separation.in)
第一行为3个整数，表示a,b,n(1 第二行至第n+1行每行为b个小于100的非负整数，表示矩阵中相应位置上的分值。每行相邻两数之间用一个空格分开。
输出文件（separation.out）
仅一个数，为均方差的最小值（四舍五入精确到小数点后2位）
样例输入
5 4 4
2 3 4 6
5 7 5 1
10 4 0 5
2 0 2 3
4 1 1 1
样例输出
0.50
【算法简析】
这题和NOI99《棋盘分割》十分类似，可以完全仿照那题的方法来做。
由于n是确定的，预处理的时候可以直接求出
本题的状态和决策都是很明显的。用一个四元组(x1,y1,x2,y2)表示以(x1,y1)为左上角，(x2,y2)为右下角的矩阵的最优值，决策就是把该矩阵划分为两个相邻子矩阵的方法——“横切一刀”或者“竖切一刀”。但是单纯这样做本题的阶段就不明显了，原因是还有划分个数这一限制。这样，我们就需要在状态中再加一维k表示分割成k个子矩阵。
设f[x1,y1,x2,y2,k]表示以(x1,y1)为左上角，(x2,y2)为右下角的矩阵分割成k个子矩阵的最优值，则：
sum(x1,y1,x2,y2) k=1
f[x1,y1,x2,y2,k]= min{f[x1,y1,x’,y2,k]+f[x’+1,y1,x2,y2,k]} (k>1) and (x1min{f[x1,y1,x2,y’,k]+f[x1,y’+1,x2,y2,k]} (k>1) and (y1其中sum(x1,y1,x2,y2)表示矩形(x1,y1,x2,y2)的权和减去后求二次幂的值。
状态是五维的，所以空间复杂度为O(105)，由于决策是O(n2)的，时间复杂度为O(107)。但是实际上有效状态很少，加上本身题目规模并不大，可以用记忆化搜索实现，时间复杂度远远达不到上限。
第二题 修筑绿化带（parterre.pas/c/cpp）
为了增添公园的景致，现在需要在公园中修筑一个花坛，同时在画坛四周修建一片绿化带，让花坛被绿化带围起来。
如果把公园看成一个M*N的矩形，那么花坛可以看成一个C*D的矩形，绿化带和花坛一起可以看成一个A*B的矩形。
如果将花园中的每一块土地的“肥沃度”定义为该块土地上每一个小块肥沃度之和，那么，
绿化带的肥沃度=A*B块的肥沃度-C*D块的肥沃度
为了使得绿化带的生长得旺盛，我们希望绿化带的肥沃度最大。
输入
第一行有6个正整数M,N,A,B,C,D
接下来一个M*N的数字矩阵，其中矩阵的第i行j列元素为一个整数Xij,表示该花园的第i行第j列的土地“肥沃度”。
输出
一个正整数，表示绿化带的最大肥沃程度。
样例
parterre.in
4 5 4 4 2 2
20 19 18 17 16
15 14 13 12 11
10 9 8 7 6
5 4 3 2 1

parterre.out
132
数据范围
30%的数据，1<=M,N<=50
100%的数据，1<=M,N<=1000,1<=A<=M,1<=B<=N,1<=C<=A-2,1<=D<=B-2，1<=“肥沃度”<=100
【算法简析】
和day1-2《理想的正方形》的方法极其相似。
首先我们可以利用迭代的思想在O(nm)的时间内求出所有a*b和c*d的矩形的权和。
我们的目标是求出所有a*b的矩形中对应的最小的c*d的矩形。现在我们将所有的c*d的矩形看作一个点，则问题就转化为和《理想的正方形》一模一样的形式，可以完全仿照那题的方法来做。
最后用O(nm)的枚举找到所有a*b的矩形减去其中最小的c*d的矩形的权和的差的最大值。
算法总时间复杂度为O(nm)。
第二题 理想的正方形（square.pas/square.c)
有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。
输入文件square.in
第一行为3个整数，分别表示a,b,n的值
第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。
输出文件square.out
仅一个整数，为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整数的差值”的最小值。
样例输入
5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
样例输出
1
问题规模
（1）矩阵中的所有数都不超过1,000,000,000
（2）20%的数据2<=a,b<=100,n<=a,n<=b,n<=10
（3）100%的数据2<=a,b<=1000,n<=a,n<=b,n<=100
【算法简析】
问题的规模相当大，O(abn)的算法都会超时，所以只能考虑O(ablogn)或者O(ab)的算法。
下面介绍O(ab)的算法：利用单调队列。
本题中枚举是必不可少的，而且最坏只能是O(ab)的，所以必须为这个O(ab)的枚举计算一些状态，即以(i,j)为左上角的n×n的正方形区域中的最大值和最小值。把这个二维的问题化简成一维，就是以(i,j)为左边的长度为n的序列的最大值max[i,j]和最小值min[i,j]，然后用同样的推算方法可以由这个一维的状态可以推算出二维的状态。现在我们的任务就是在O(b)的时间内计算出一行的max[i]和min[i]。这就需要借助单调队列了。
开两个队列，一个维护最大值，一个维护最小值。为了方便叙述，下文只讨论最大队，最小队的维护方式类似。
我们要保证队列中各个元素大小单调递减（注意，不是单调不上升），各个元素的下标单调递增。这样才可以保证队首元素最大，而且更新的时候队首永远是当前最大。因此，需要改造一下队列，让它变成能在两头删除，在队尾插入。
为了保证单调性，每次插入的时候，先判断队尾元素，如果不比待插入元素大就删除，不断删除队尾直到队尾元素大于待插入元素或者队空。删除的时候，判断队首，如果队首元素下标小于当前段左边界就删除，不断删除队首直到队首元素下标大于等于当前段左边界（注意：这时队列肯定不为空），队首元素就是当前段的最优解。
有了单调队列，计算max[i]和min[i]就方便了。初始的时候分别把当前行前n-1个元素插入队尾。从第1列开始，每次取队首最优值，从队首删除无效元素，并将当前列+n-1号元素插入队尾。由于每个元素最多入队出队各一次，时间复杂度就是O(b)。
用相同的方法可以在O(a)时间内根据max[i]和min[i]计算出正方形的最优解，时间复杂度为O(ab)。
附：O(ablogn)的算法可以转化为矩形的RMQ，用二维的Sparse Table解决。
[分享][KMP]串匹配的高效算法-KMP
[Copy to clipboard]
CODE:
对于两个串，我们设一个串为主串S,一个串为模式串s,即要求s在S中的位置。
当两串匹配到s的位置i时发现不匹配，这时不需要从头来匹配，可以从s的位置k来匹配(k>=1)，这就是KMP算法的精华之处。
S1,S2,S3,S4..SN
s1,s2,s3,s4..sn
由已知匹配可知
S(i-k+1),S(i-k)..S(i-1)=s(i-k+1),s(i-k)..s(i-1)
由k的解释可知
S(i-k+1),S(i-k)..S(i-1)=s1,s2..s(k-1)
所以有
s1,s2..s(k-1)=s(i-k+1),s(i-k)..s(i-1)
可以发现k的值与主串S无关，关键在于求出s中每个位置j对应的k。
设f(j)为j所对应的k，则有：
f(j)=0 (j=1)
f(j)=max{k(0以上是推导过程，下面介绍求k的方法：
s,k:array[1..n]of integer;
开始设k[1]:=0;
for i:=2 to n do
begin
j:=i-1;{初始j}
while not((s[i-1]=s[k[j]]) or (j=1)) do
j:=k[j];
{直到找到一个j，使得s[i-1]=s[k[j]],则k[j]+1为所求}
k[i]:=j+1;
end;
求出k以后，接下来的事情就好办多了，用m,n记录S和s中的位置，从左到右扫一遍就行了。
这个算法的复杂度是多项式的
写得有点抽象...........
刚刚翻到的，zqy写的
[Copy to clipboard]
CODE:
[原创]KMP算法总结
关于模式匹配(KMP)的解题报告
by zqy
引言:模式匹配是串的操作中最重要的一种,而KMP算法是一种相当高效的模式匹配算法(下文中将提到它的时间复杂度为O(m+n)).所以,KMP算法是我们必须掌握的一种基本方法.
正文:
1. 朴素的模式匹配算法.
朴素的模式匹配算法的核心思想是:一旦某个字符匹配失败,从头开始(即从本次匹配起点后一个字符开始).因此朴素的模式匹配算法的时间复杂度为O(mn),它的时间无法让人们满意,于是新的模式匹配算法也就孕育而生了.
在介绍KMP算法之前,我们先来看一下为什么朴素的模式匹配算法无法令人满意.
主串:ababcabcacbab 模式串:abcac
第一次比较:主串第三个位置出错,起点向后一位.
第二次比较:主串第二个位置出错,起点向后一位.
第三次比较:主串第七个位置出错,起点向后一位.
第四次比较:主串第四个位置出错,起点向后一位.
第五次比较:主串第五个位置出错,起点向后一位.
第六次比较:成功!
仔细观察我们可以发现,第一次比较错误以后,完全可以把起点放到主串的第三位,而不是第二位(因为根据已有的判断,第二位去比较肯定不会成功).因此第二次比较是无效比较.正是因为诸如上例中第二次比较的无效比较,使得算法不够理想.
2. KMP算法
2.1Next的函数的引出:
通过上述分析我们可以知道,要想改进模式匹配的算法,必须减少无效比较,让起点自动移到当前认为的最理想的位置,而不是仅仅只移一位.但是,计算机怎么知道要移几位呢 这就需要一个先开始就制定好的函数.于是我们就引出了next函数.
2.2Next的函数的定义和计算:
next的函数到底是什么呢 根据我的理解,next[i]表示当模式串中第i个字符与主串某个字符比较失败后,起点应该向后移几位.那么,next函数的值怎么求呢
显然,如果模式串第一位就比较错了,只能移动一位.为了和后面以示区别,我们定义next[1]=0.那么,其他的next怎么求呢
我们回过头来仔细分析next函数的定义,发现它就是在求最大的k使得’P1..Pk’=’Pi-k+1..Pi’,因此,next[i]的求法如下
若i=1,则next[i]=0;
若Pi=Pnext[i-1]+1,则next[i]=next[i-1]+1;
其它情况则next[i]=1;
因此计算next函数的过程如下:
procedure count_next;
var i,j:integer;
begin
i:=1;j:=0;next[1]:=0;
while ibegin
if (j=0)or(t[i]=t[j]) then
begin
inc(i);
inc(j);
next[i]:=j;
end
else j:=next[j];
end;
end;
效率分析:这个过程的时间复杂度为O(n),其中n为模式串的长度.由于n通常比主串的长度小得多,因此整个过程花不了多少时间,是值得的.
2.3主程序
有了next的函数,KMP算法的主程序就容易编了.还是顺次匹配,一旦不成功,起点向后移动next[j]位,程序如下:
procedure KMP_index;
var i,j:integer;
changed:boolean;
begin
count_next;
i:=1;j:=1;
changed:=false;
while (i<=length(s))and(j<=length(t)) do
begin
if (j=0)or(s[i]=t[j]) then
begin
inc(i);
inc(j);
end
else j:=next[j];
if j>length(t) then begin writeln('Place:',i-length(t));changed:=true;j:=1;end;
end;
if not changed then writeln('No Answer');
end;
注明:这个主程序可以找出模式串在主串中的所有位置.
效率分析:这个过程的时间复杂度位O(m),m为主串的长度,加上前面计算next函数所用的时间,整个算法的复杂度为O(m+n),确实优于朴素的模式匹配.
3. 总结:KMP算法首先抓住普通模式匹配算法之所以不优秀的原因,然后分析怎样才能解决,因此我们最常用的模式匹配的算法也就产生了.因此,KMP算法是一个相当优秀的模式匹配算法.
附录:
程序清单:
program KMP;
var s,t:string;
next:array[1..100] of longint;
procedure count_next;
var i,j:integer;
begin
i:=1;j:=0;next[1]:=0;
while ibegin
if (j=0)or(t[i]=t[j]) then
begin
inc(i);
inc(j);
next[i]:=j;
end
else j:=next[j];
end;
end;
procedure KMP_index;
var i,j:integer;
changed:boolean;
begin
count_next;
i:=1;j:=1;
changed:=false;
while (i<=length(s))and(j<=length(t)) do
begin
if (j=0)or(s[i]=t[j]) then
begin
inc(i);
inc(j);
end
else j:=next[j];
if j>length(t) then begin writeln('Place:',i-length(t));changed:=true;j:=1;end;
end;
if not changed then writeln('No Answer');
end;
begin
readln(s);
readln(t);
KMP_index;
end.
noip2006解题报告［绝对原创］
　　消耗了一个星期的是时间，躲过了班主任的眼睛，呵呵，终于完成的了０６的解题报告
呵呵．．．
　　本人的处女作了，也是对论坛的第一次贡献吧．．．．
　　　　　　
　　由于附件不能上传．．只能贴了．．呵呵
能量项链
本题是一道很经典的dp题目，其实质就是“石子合并问题”的变形，有谈不上什么变形，倒不如说复制更好一点。我想很多的牛人在这个题目失分的原因多为没弄懂题目的意思就下手做了，把题目看简单了。
简单的说：给你一项链，项链上有n颗珠子。相邻的两颗珠子可以合并(两个合并成一个)。合并的同时会放出一定的能量。不同的珠子的合并所释放的能量是不同的。问：按照怎样的次序合并才能使释放的能量最多？
　　我们用top表示第i颗珠子的头标记，用wei表示第i颗珠子的尾标记，合并两颗相邻珠子所释放的能量是：
　　Q=top*wei*wei[i+1]或top*top[i+1]*wei[i+1]; （一个样的）
　　合并不一定按顺序的，本题所提供的样例也是导致出错的一大原因。
　　n个珠子进行一次合并的后，就归结到了n-1个珠子的合并的问题。所以我们想到了动态规划。
　　既然是dp题目，必然要满足dp的两大条件：、
　　1.最优子结构性质；
　　设Q[i,j]表示第i颗珠子到第j颗珠子合并所产生的能量。显然Q[1,n]表示的是合并产生的总的能量。给定一种标号方法，maxQ[1,n]就是所要求的。设最后一次合并在k处进行，则有Q[1,n]＝Q[1,k]＋Q[k+1,n]＋top[1]*wei[k]*wei[n]。要Q[1,n]最大，必然要Q[1,k]，Q[k+1,n]最大。
　　证明：假设Q[1,k]不是最大，则必然存在一Q'[1,k]>Q[1,k]。
那么就有Q'[1,n]＝Q'[1,k]＋Q[k+1,n]＋top[1]*wei[k]*wei[n]>Q[1,k]。这与Q[1,n]的最优性矛盾。
　　最优子结构性质得证。
2.无后效性；
　　 无后效性是显然的，进行某次合并，合并前与合并后状态是相对独立，不相关联，互不影响的。
　　
　　算法已经定了下来了，关键是怎么实现了。
　　项链是一个环，而我们处理是对一个串进行的。所以我们要把项链从某处割断展开，不同处的割断对应着不同的展开方法，也就是对应着不同的标号方法。产生的maxQ[1,n]也就不同的。所以我们要对这些maxQ[1,n]进行打擂，取其最大的一个，即为解了。
dp的转移方程是：
Best=maxQ[1,n] 1<=i<=n (i表示从第i颗珠子处展开，顺次标号）；
Q[i,j]=max{Q[i,k]+Q[k+1,j]+top*wei[k]*wei[j] 1<=i<=k其中Q[i,i]=0 1<=i<=n;
dp的时间复杂度为O(n^3)，n种的展开方法对应需要n次的dp，所以时间复杂度为O(n^4)。空间为O(n^2)。
显然O(n^4)过这个题目是有点欠缺的，对的大的数据貌似很容易超时的。
　　如果仔细想想，我们还是做了很不重复的工作的，不同的展开方式中必然存在着很多的大量的重复运算。于是还有很大的优化空间，既然展开做了很多的重复的工作，那么就合并起来吧。回到起点，开始的时候为什么我们要对项链做n次的展开呢，基于我们在运算的时候不能够实现第一颗珠子与第n颗珠子的相邻性。为了一次dp就实现所以的的珠子的相邻性，我们做如下处理：
　　　　a[1],a[2],a[3]...a[n],a[1],a[2]...a[n-1]　
（原来的）　 （延伸的）
　　也就是：
　　　　a[1],a[2],a[3]...a[n],a[n+1],a[n+2]...a[m]　　　
　　显然m=2n-1;
　我们对这一串珠子dp一次即可得解；dp方程为：
　　　Best=max{Q[i,i+n-1] 1<=i<=n}
　Q[i,j]=max{Q[i,k]+Q[k+1,j]+top*wei[k]*wei[j] 1<=i<=k其中Q[i,i]=0 1<=i<=m;
显然时间复杂度为O(n^3)，空间为O(n^2)。min(i+n-1,m)已经对dp进行了优化。
　　（附程序）
　　到这里我们可以很完美的过这个题目的所以数据了；但还是觉得不够快，想用四边形优化，但想了想显然是不可以的，W函数不是单调的。
　　用树的知识可以更多的优化为（O(n^2*log2n)）。这里就不多说了，写起来挺烦的。
program Qi(inout,output);
var
n,m:integer;
top,wei:array[1..200] of integer;
f:array[1..200,1..200] of longint;
procedure init;
var
i:integer;
begin
readln(n);
for i:=1 to n do read(top);
readln;
for i:=1 to n-1 do wei:=top[i+1];
wei[n]:=top[1];
m:=n*2-1;
for i:=n+1 to m do begin top:=top[i-n]; wei:=wei[i-n]; end;
end;
procedure doit;
var
p,i,j,k:integer;
begin
fillchar(f,sizeof(f),0);
for p:=1 to n-1 do
for i:=1 to m-1 do
begin
j:=i+p;
if j>m then break;
for k:=i to j-1 do
if f[i,j]then f[i,j]:=f[i,k]+f[k+1,j]+top*wei[k]*wei[j]
end;
end;
procedure print;
var
i:integer; best:longint;
begin
best:=0;
for i:=1 to n do
if bestwriteln(best);
end;
begin
init;
doit;
print;
end.
金明的预算方案
　　如果看过普及组试卷就会发现，对应的第二个题目，也是一个样的背景，提高组只是多了个“主件附件”的的关系，如果去掉这一点，就全没区别了。也就成了经典的背包问题了。也就是多了这么一点，考试的时候就晕了。不知道怎么做了。后来才发现是个很简单的dp题目。可惜我当时没做出来。
　　草率的审题，可能会得到这样的算法：dp，对每一个物品做两种决策，取与不取。如果取，满足两个条件：1.要么它是主件，要么它所属的主件已经在包里了。2.放进去后的重要度与价格的成绩的总和要比没放进时的大。这两个条件缺一不可的。于是呼，得到如下的动规方程：
　　　f[i,j]:=f[i-1,j];
if (i为主件or i的附件在包中）and (f[i,j]then f[i,j]:=f[i,j-v]+v*w;
　　我们来分析一下复杂度，空间：dp的阶段为n^2,对与每一个阶段都要记录该状态下在包中的物品有哪些（因为要确定附件的主件是否在包中)，每个阶段的记录都要O(n)的空间，所以总的就是O(n^3)。时间，一个dp，n^2的外层循环，内部用布尔量加个主附件的对应数组，为O(1)，和起来就为O(n^2)的复杂度。
　　可以看的出，时间的需求为32000*60，不成问题。空间32000*60*60，大约要7.5M的空间，在64M的要求下是完全可以的过的。如果用上题目中的一个很隐秘的条件：“每件物品都是10元的整数倍”，就可以把速度在提高十倍。
　　细细的看题目，还一个很重要的条件我们还没用：“每个主件可以有０个，１个或２个附件”。这貌似不起眼的一句话，却给我们降低复杂度提供了条件。想一想，为什么题目要对附件的个数做限制呢，明显是在降低难度。
　　对于一套物品（包含主件，所以的附件），我们称为一个属类，对一个属类的物品的购买方法，有以下５种：
　　　　１.一个都不买
　　　　２.主件
　　　　３.主件＋附件１
　　　　４.主件＋附件２
　　　　５.主件＋附件１＋附件２
　　这五种购买方法也是唯一的五种方法，也就是说对一属类的物品，我们只有上述的５种购买方法。
　　于是我们很自然的就会想到把物品按物品的属类捆在一起考虑。这样我们把物品的属类作为dp的状态。可以得到如下的dp方程：
　　f[i,j]=max{f[i-1,j];
f[i-1,j-v[i,0]]+v[i,0]*w[i,0];
f[i-1,j-v[i,0]-v[i,1]]+v[i,0]*w[i,0]+v[i,1]*w[i,1];
f[i-1,j-v[i,0]-v[i,2]]+v[i,0]*w[i,0]+v[i,2]*w[i,2];
f[i-1,j-v[i,0]-v[i,1]-v[i,2]]+v[i,0]*w[i,0]+v[i,1]*w[i,1]+v[i,2]*w[i,2];}
很显然时间复杂度为O(n^2)，空间复杂度为O(n^2)，加上利用“每件物品都是10元的整数倍”除以10的优化，本题就很完美的解决了。
　　（附程序）；
program Qi(input,output);
type
node=record
u:integer;
v:array[0..2] of integer;
p:array[0..2] of integer;
end;
var
n,m,k:integer;
w:array[1..60] of node;
f:array[0..60,0..3200] of longint;
g:array[1..60] of integer;
procedure init;
var
i,j:integer;
vx,px,qx:array[1..60] of integer;
begin
readln(n,m); k:=0;
for i:=1 to m do
begin
readln(vx,px,qx);
if qx=0
then begin
k:=k+1; g:=k;
with w[k] do
begin
u:=0;
v[0]:=vx; p[0]:=px;
for j:=1 to 2 do begin v[j]:=0; p[j]:=0; end;
end;
end;
end;
for i:=1 to m do
if qx<>0
then begin
with w[g[qx]] do
begin
u:=u+1;
v:=vx; p:=px;
end;
end;
for i:=1 to k do
with w do
begin
for j:=0 to 2 do write('(',v[j],',',p[j],') ');
writeln;
end;
end;
procedure doit;
var
i,j:integer;
begin
fillchar(f,sizeof(f),0);
for i:=1 to k do
with w do
begin
for j:=1 to n do
begin
f[i,j]:=f[i-1,j];
if (j>=v[0]) and (f[i,j]then f[i,j]:=f[i-1,j-v[0]]+v[0]*p[0];
if (j>=v[0]+v[1]) and (f[i,j]then f[i,j]:=f[i-1,j-v[0]-v[1]]+v[0]*p[0]+v[1]*p[1];
if (j>=v[0]+v[2]) and (f[i,j]then f[i,j]:=f[i-1,j-v[0]-v[2]]+v[0]*p[0]+v[2]*p[2];
if (j>=v[0]+v[1]+v[2]) and (f[i,j]then f[i,j]:=f[i-1,j-v[0]-v[1]-v[2]]+v[0]*p[0]+v[1]*p[1]+v[2]*p[2];
end;
end;
end;
procedure print;
begin
writeln(f[k,n]);
end;
begin
init;
doit;
print;
end.
作业调度方案
　　对本题的评价：题目超长，超简单，失分率最高。
　　当我在考场上拿到这个题目的时候，考试的紧张的气氛压抑着……读了一遍，不知所云，又读了一遍，依然莫名其妙，读第三便，I give up !!!考试回来，一看，这样的题目竟然不会，一定是气的死去活来，我就是这样郁闷了整整的一个月的。
　　超简单的贪心算法。
　　简单的说：有n个工件要在m个机器上加工，每个工件都有m到工序，每个工序对应着相应的加工机器。一个工件的工序必须依次进行。同一台机器同时只能加工一个工件。每个工件的每个工序需要一定的加工时间。问：加工完所有的工件需要的最少时间是多少？
　　本题在题目中连算法都给出了，考察的是对题意的理解和数据结构，但本题的规模并没有对数据结构做过高的要求。应该可以说是本次考试的最简单的题目了，但不是送分题，很多人和我一样都望而止步了。
　　最简单，按部就班就可以了。
　　下面是题目中给我们的详尽算法：
　　“当一个操作插入到某台机器的某个空档时（机器上最后的尚未安排操作的部分也可以看作一个空档），可以靠前插入，也可以靠后或居中插入。为了使问题简单一些，我们约定：在保证约束条件（1）（2）的条件下，尽量靠前插入。并且，我们还约定，如果有多个空档可以插入，就在保证约束条件（1）（2）的条件下，插入到最前面的一个空档。”
　　建议大家在考试的时候使用数组，平时可以用指针写一写……
　　（附程序）；
program Qi(input,output);
var
m,n:integer;
a:array[1..400] of integer;
f:array[1..20,0..1000] of boolean;
wu,ti:array[1..20,1..20] of integer;
g,time:array[1..20] of integer;
procedure init;
var
i,j:integer;
begin
readln(m,n);
for i:=1 to n*m do read(a);
readln;
for i:=1 to n do
begin
for j:=1 to m do read(wu[i,j]);
readln;
end;
for i:=1 to n do
begin
for j:=1 to m do read(ti[i,j]);
readln;
end;
end;
procedure doit;
var
i,j,k,xtime:integer;
begin
fillchar(f,sizeof(f),true);
fillchar(time,sizeof(time),0);
fillchar(g,sizeof(g),0);
for i:=1 to n*m do
begin
inc(g[a]); j:=time[a]+1;
xtime:=0;
while xtimebegin
if f[wu[a,g[a]],j]
then inc(xtime)
else xtime:=0;
j:=j+1;
end;
time[a]:=j-1;
for k:=j-xtime to j-1 do f[wu[a,g[a]],k]:=false;
end;
end;
procedure print;
var
i,j,best:integer;
begin
best:=0;
for i:=1 to m do
for j:=1000 downto 0 do
if not f[i,j] then
begin
if bestbreak;
end;
writeln(best);
end;
begin
init;
doit;
print;
end.
备注：不知道为什么第6个数据我的答案是112.而提供的答案是116..
如果有错...欢迎牛人指出....呵呵.(我的qq:418539455);
备注：
2k进制数
　　这就是传说中的数学题吗 考试前曾沸沸扬扬的流传过这么一段：“今年的题目出于一数学教授，都是写超难的题目，四个题目有三个是数学题。”再加上今年的maths库函数登上历史舞台。更让人深信不移：今年要考数学题。
　　谣言不可信啊，冤死了多少牛们……
　　说本题是数学题，到不如说是个找规律的题目。
　　我们还是用标准的数学方法做一下好了。本题其实就是个很简单的组合数学问题。没上过高三做不出也就算了，上过高三的牛们没做出来，多为放弃的了。
　　从题中可以看出，w的值限制着首位的取值。所以我们要对与特殊考虑。比如样例中的w=7，就限制了首位只能取０和１。下面关心的就是位数的问题了，w决定了数的最大的位数，最少的位数要求是２位。k决定了数的位权。
　　抽象的是说了半天也不说不清楚，举个例子吧：就拿样例说，k=3。所以位权是2^k=8，w=7，决定了数的位数最大是３｛w div k+1｝，最多位的数是最高位最大只能是１｛2^((w+1) mod k-1)-1｝。所以我们分两种做讨论：1.位数是最多位，2.位数小于最多位。
　　1.位数为最多位（最多位为３）；
　　最高位位１：后面的两位只能在２－７之间取两个不同的数。显然取法的种数为c[2,6]。{c[n,m]=m!/(n!*(m-n)!)，就是组合数}
　　……　……
　　　　｛这里的最高位只能为１，所以只讨论一种情况｝。
　　2.位数小于最多位。
　　２位：这两位只能从１－７之间取数，为c[2,7]。
　　……　……
　　｛这里只有两位的情况，所以只讨论这一种情况｝。
　　从上面的例子，我们可以看出一般的情况：
　　位权：n=2^k。　位数：l=w div k+1;｛当w mod k=0时，最高为最大为０，结合下｝
　　最高位最大值：2^((w+1) mod k-1)-1。
　　　　｛这是我们要知道的几个基本的元素｝
　　下面就是统计满足的数的个数：
　　1.位数为最多：
　　　　最高为取值x (2<=x<=mhigh);
对于给定最高位x都有一些L位满足条件的数，这些数的个数为c[l-1,n-x-1]。
２：位数小于最多：
对于每一个给定的w位数都对应着c[w,n-1]个满足条件的数。
把这些数的个数全部加起来就可以了。
为了简化算法，我们引进一个组合公式：
　　c[n,m]=c[n-1,m-1]+c[n,m-1]; 其中c[n,m]=m!/(n!*(m-n)!
如果不用高精度，int64可以过７个点，高精度就可以全过了。
(附程序);
program Qi(input,output);
var
k,w,n,l,mhigh:integer;
answer:array[1..200] of integer;
c:array[1..512,1..512,1..100] of integer;
procedure init;
begin
readln(k,w);
end;
procedure ready;
var
i,j,l,jin,s:integer;
begin
for i:=1 to 512 do c[1,i,1]:=i;
for i:=2 to 512 do
begin
for j:=2 to i do
begin
jin:=0;
for l:=1 to 100 do
begin
s:=c[j-1,i-1,l]+c[j,i-1,l]+jin;
c[j,i,l]:=s mod 10;
jin:=s div 10;
end;
end;
end;
end;
procedure plus(n,m:integer);
var
i,jin,s:integer;
begin
jin:=0;
for i:=1 to 100 do
begin
s:=answer+c[n,m,i]+jin;
jin:=s div 10;
answer:=s mod 10;
end;
end;
procedure doit;
var
i:integer;
begin
ready;
n:=1;
for i:=1 to k do n:=n*2;
n:=n-1;
l:=w div k+1;
mhigh:=1;
for i:=1 to (w+1) mod k-1 do mhigh:=mhigh*2;
mhigh:=mhigh-1;
for i:=2 to l-1 do if i<=n then plus(i,n);
for i:=1 to mhigh do if l-1<=n-i then plus(l-1,n-i);
end;
procedure print;
var
i,j:integer;
begin
j:=100;
while answer[j]=0 do j:=j-1;
for i:=j downto 1 do write(answer);
writeln;
end;
begin
init;
doit;
print;
end.
( http: / / www.oibh.org / bbs / misc.php action=viewratings&tid=11962&pid=126033" \o "评分 0 )NOIP考前知识大总结
作者：于俊超
ID:MiniDragonXG
2006年11月
数据类型
Type Range Size in bytes
Byte 0 .. 255 1
Shortint -128 .. 127 1
Smallint -32768 .. 32767 2
Word 0 .. 65535 2
Integer either smallint, longint or int64 size 2,4 or 8
Cardinal either word, longword or qword size 2,4 or 8
Longint -2147483648 .. 2147483647 4
Longword 0..4294967295 4
Int64 -9223372036854775808 .. 9223372036854775807 8
QWord 0 .. 18446744073709551615 8
Real 2.9E-39 .. 1.7E38 6
Single 1.5E-45 .. 3.4E38 4
Double 5.0E-324 .. 1.7E308 8
Comp -9.2E18 .. 9.2E18 8
Extended 3.4E-4932 .. 1.1E4932 10
算法思想:
1.搜索 (Search) 枚举(穷举) / 遍历 / 剪枝 / 产生式系统（估价函数）
查找(字典)：折半查找(二分法) / 树形查找(二叉排序树) / Hash
2.归纳 (To 数学方法) > 递推式 > DP (ex: 4 Hanoi Tower Problem)
3.分治 (Divided and Conquer)
4.贪心 (Greedy) 5.模拟
实现技巧: 循环
递推(顺推/倒推) > 博弈 / 动态规划
递归(栈/DFS)
滚动数组
幂：
x ^ y = exp(y*ln(x))
x ^ (1/n) = exp(1/n*ln(x))
math单元里的Power
数学方法:
1.数论: 质数 / 因数 / 约数个数（种数）/ 最大公约数 / 最小公倍数 / 回文数....
2.进制转换 注意负进制
3.高精度运算 (int64...)
4.排列组合: 全排列
5.经典递推关系:
Fibonacci: fib(n)=fib(n-1)+fib(n-2)
fib(1)=1 fib(2)=1
通项： 设g5=sqrt(5) 则fib(n)=(1/g5)*( ((1+g5)/2)^n-((1-g5)/2)^n )
f(n)=a1*f(n-1)+a2*f(n-2)+....+ak*f(n-k) (ai<>0 & n>k)叫
k阶常系数线性齐次递推关系
可以利用矩阵性质和快速幂在O(logn)内求解
错位排列: F(1)=0 F(2)=1
Fn=(x-1) * (Fn-1 +Fn-2)
Catalan数: Catalan(n)=C(n,2*n)/(n+1)
第二类Stirling数 s(n,k)= { s(n-1,k-1)+k*s(n-1,k) } (n>k>=1)
6.高斯消元
数据结构(Data Structure):
1.物理结构:
I: 数组 > 二维平面/字符串(Ansistring)及其操作
II: 指针 > 链表 （单链表 / 双向链表 / 环状链表）
抽象数据类型(Abstract Data Type)
2.初级ADT:
I: 集合
II: 线性结构
A: 栈(stack)
(LIFO) operation: push/pop
a: 后缀表达式
b: 进出站序列问题(Catalan 枚举 > 归纳)
c: 栈优化最长不下降(上升)序列
B: 队列(queue) > 循环队列
(FIFO) operation: push/pop
a: 广度优先搜索
b: 求和广义线性表
C: 字典 Dictionary
III: 非线性结构
A: 树Tree (二叉树Binary Tree)
树的遍历：前序/中序/后序 (递归)
最优二叉树(哈夫曼树Huffman tree）（贪心）
树形DP
B: 图Graph
a: 图的遍历:
Depth first Search (DFS / 回溯 / 递归)
Breadth first Search (BFS / 队列 / FloodFill 种子染色法 )
b: 最小生成树：（贪心）
Prim: 边集密
Kruskal: 边集疏（排序 + 并查集）
c: 最短路径
Dijkstra（ 单源 O(n^2) BFS ）
Floyed（ 所有点间 O(n^3) ）
Bellman-Ford（负权环）
d: 拓扑序列
e: 关键路径（AOV网）
f: 无向图传递闭包
有向图强连通分量SCC
(Strong Connected Component)
g: 路与回路
欧拉路(Euler Route)所有边
哈密尔顿路(Hamilton Route)所有点
h: 割顶和桥
去除之后图变得不连通的顶点和边
3.高级ADT:
I: 集合型
A: 并查集(disjoint-set)
operation: Find/Union/Insert
II: 字典型
哈希表(Hash) 哈希函数
opertaion: Find/Insert
III: 树型
A: 二叉堆(Heap) > Treap
operation: Insert/Delete(Pop)/GetMax/GetMin
B: Binary Search Tree(BST)
C: 平衡二叉树......
排序算法:
复杂度 思路 Insert Choose Exchange
O(n^2) 直接插入排序 直接选择排序 冒泡排序
(Inserting Sort) (Choosing Sort) (Bubble Sort)
O(nlogn) 希尔排序 堆排序 快速排序 归并
(Shell Sort) (Heap Sort) (Quick Sort) (Merge Sort)
O(n) 计数排序 桶排序 基数排序
(Counting Sort) (Bucket Sort) (Radix Sort)
Quick Sort: 分治
Merge Sort: 分治
Bucket Sort: 哈希表
Heap Sort: 堆
还有二叉排序树..........
动态规划(Dynamic programming)
=记忆化搜索+用Table记录免去重复计算
（解决 满足具有最优子结构 且 无后效性）
1.状态转移方程+边界条件
2.合适的实现方法(To 实现技巧)
3.要掌握最经典的动规题目
a: 最长不下降(上升)序列
b: 最大子段和 & 最大M子段和
c: 最长公共子序列(LCS)
d: 石子合并（链，环）
e: 背包问题
01背包-可重复(DP)
01背包-不可重复(DP)
部分背包(贪心)
博弈问题：
关键字：必胜态 / 必败态
2. 递推找规律
3. 归纳
计算几何
三角形面积 s=|x1y2+x2y3+x3y1-x3y2-x2y1-x1y3|
二维仿射变换 反射 / 镜像 / 旋转
计算二维凸包……这东西我直接听不懂……
网络流 & 匹配（二分图） & 线段树 & 树状数组 & NP完全 ……
∵九成不考 ∴略……
Y
X
C
B
A
Y
X
C
B
A
左旋（Left-Ratote）
右旋（Right-Ratote）
T
L
R
A
B
C
D
L
A
T
R
B
C
D
T
L
R
A
B
C
D
E
F
T
B
R
L
F
C
D
A
E
B
L
T
A
E
F
D
C
D
插入200万个随机值结点
单位：秒
16
14
12
10
8
6
4
2
0
SBT
7.13
AVL
8.34
Treap
11.36
Random BST
13.61
200万个操作，66%为插入，33%为删除，全部随机
单位：秒
16
14
12
10
8
6
4
2
0
SBT
5．59
AVL
7．42
Treap
8．86
Random BST
10．47
200万个操作，20%为插入，10%为删除，60%查询，全部随机
单位：秒
8
7
6
5
4
3
2
1
0
SBT
3．39
AVL
4．42
Treap
5．67
Random BST
6．21Fill*简介
本来想写“详解”的，但是发现真正的详解在这里：
http://oibh./newcomer/fillchar.HTM
关于原码、反码、补码：
http://dev.csdn.net/develop/article/17/17680.shtm
0、fill*函数
fill*函数是Pascal中自带的函数，用于对数组的赋值。在FreePascal中，有
[Copy to clipboard]
CODE:
fillchar
fillbyte
fillword
filldword
共4种。
1、参数
fill*(var a:array; count:word; value:*);
a就是你要fill的数组；count就是需fill的内存段的大小，以字节为单位；vale就是要赋的值。
为什么count一般写sizeof(a)呢？因为sizeof函数就是返回其参数所占字节数-_-
2、fillchar/fillbyte
这两个基本上是一样的（在下没有发现差别）：每一字节赋一次值，大小为第三个参数。如果a数组是int类型（即有正负之分），第三个参数转化为二进制后作为补码。
例1
[Copy to clipboard]
CODE:
var a:array [1..10] of byte;
begin
fillbyte(a,sizeof(a),3);
end.
其中sizeof(a)=10。结果是a全部为3。
例2
[Copy to clipboard]
CODE:
var a:array [1..10] of shortint;
begin
fillbyte(a,sizeof(a),233);
end.
233=(11101001)2，即fill后每8位的值都是(11101001)补=-106。
例3
[Copy to clipboard]
CODE:
var a:array [1..10] of integer;
begin
fillbyte(a,sizeof(a),2);
end.
2=(00000010)2，即a[ i ]=(0000001000000010)补=514
3、fillword
每2字节赋一次值。如果a数组是int类型（即有正负之分），第三个参数转化为二进制后作为补码。
4、filldword
每4字节赋一次值。如果a数组是int类型（即有正负之分），第三个参数转化为二进制后作为补码。
5、一点问题
在使用fillword/filldword的时候，有时候会出现各种各样奇怪的问题，因此建议大家尽量不要使用。PAGE
陈启峰 WC2007论文 数据结构 Size Balanced Tree 第11页
Size Balanced Tree
陈启峰 (Farmer John)
中国广东纪念中学
Email:344368722@
2006.12.29
摘要
这篇论文将展现一个独特巧妙的策略，动态地维护二叉搜索树（Binay Search Trees，缩写为BST），并且它在最坏的情况下也有着良好的期望运行速度。Size Balanced Tree，顾名思义，这是一棵通过大小（Size）域来维持平衡的二叉搜索树。
这是一种简单、高效并且在各方面都通用的数据结构。
这也是一种很容易被语言工具表述的数据结构，它有着简单明了的定义，和令人惊叹的运行速度，而且你会惊讶于它简单的证明。
这是目前为止速度最快的高级二叉搜索树[1]]。
此外，它比其它一些知名的高级二叉搜索树要快得多，并且在实践中趋于完美。
它不仅支持典型的二叉搜索树操作，而且也支持Select和Rank。
关键字
Size Balanced Tree
SBT
Maintain
翻译 By 竹子的叶子
文档经过处理，可以使用“视图”——“文档结构图”来方便阅读。
希望大家不要随便修改，谢谢！
1 介绍
在展现Size Balanced Tree之前，有必要详细说明一下二叉搜索树的旋转，左旋（Left-Ratote）和右旋（Right-Ratote）。
1.1 二叉搜索树
二叉搜索树是一种非常重要的高级数据结构，它支持很多动态操作，其中包括搜索（Search），取小（Minimum），取大（Maximun），前驱（Predecessor），后继（Successor），插入（Insert）和删除（Delete）。它能够同时被当作字典和优先队列使用。
二叉搜索树是按照二叉树结构来组织的，树中的每个节点最多只有两个儿子，二叉搜索树中关键字的储存方式总是满足以下二叉搜索树的性质：
设x是二叉搜索树中的一个结点，那么x的关键字不小于左子树中的关键字，并且不大于右子树中的关键字。
对于每一个结点t，我们使用left[t]和right[t]来储存它两个儿子的指针[2]，并且我们定义key[t]来表示结点t用来做比较的值。另外，我们增加s[t]，表示以t为根的子树的大小（Size），维持它成为这棵树上结点的个数。特别地，当我们使用0时，指针指向一棵空树，并且s[0]=0。
1.2 旋转
为了保持二叉搜索树的平衡（而不是退化成为链表），我们通常通过旋转改变指针结构，从而改变这种情况。并且，这种旋转是一种可以保持二叉搜索树特性的本地运算[3]。
图 1.1
图 1.1：左旋Left-Ratote(x)操作通过更改两个常数指针将左边两个结点的结构转变成右边的结构，右边的结构也可以通过相反的操作Right-Ratote(x)来转变成左边的结构。
1.2.1 右旋的伪代码
右旋操作假定左儿子存在。
Right-Rotate(t)
1 k ← left[t]
2 left[t] ← right[k]
3 right[k] ← t
4 s[k] ← s[t]
5 s[t] ← s[left[t]] + s[right[t]] + 1
6 t ← k
1.2.2 左旋的伪代码
左旋操作假定右儿子存在。
Left-Rotate (t)
1 k ← right[t]
2 right[t] ← left[k]
3 left[k] ← t
4 s[k] ← s[t]
5 s[t] ← s[left[t]] + s[right[t]] + 1
6 t ← k
2 Size Balanced Tree
Size Balanced Tree（SBT）是一种通过大小（Size）域来保持平衡的二叉搜索树。它支持许多运算时间级别为O(logn)的主要操作：
Insert(t,v) 在以t为根的SBT中插入一个关键字为v的结点。
Delete(t,v) 从以t为根的SBT中删除一个关键字为v的结点，如果树中没有一个这样的结点，删除搜索到的最后一个结点。
Find(t,v) 查找并返回结点关键字为v的结点。
Rank(t,v) 返回v在以t为根的树中的排名，也就是比v小的那棵树的大小（Size）加一。
Select(t,k) 返回在第k位置上的结点。显然它包括了取大（Maximum）和取小（Minimun），取大等价于Select(t,1)，取小等价于Select(t,s[t])。
Pred(t,v) 返回比v小的最大的数。
Succ(t,v) 返回比v大的最小的数。
通常SBT的每一个结点包含key，left，right和size等域。size是一个额外但是十分有用的数据域，它一直在更新，它在前面已经定义了。
每一个在SBT中的结点t，我们保证：
性质a：
性质b：
图 2.1
图2.1：结点L和R分别是结点T的左右儿子。子树A、B、C和D分别是结点L和R各自的左右子树。
符合性质a和性质b，
3 Maintain
如果我们要在一个BST插入一个关键字为v的结点，通常我们使用下列过程来完成任务。
Simple-Insert (t,v)
1 If t=0 then
2 t ← NEW-NODE(v)
3 Else
4 s[t] ← s[t]+1
5 If v6 Simple-Insert(left[t],v)
7 Else
8 Simple-Insert(right[t],v)
在执行完简单的插入之后，性质a或性质b可能就不满足了，于是我们需要调整SBT。
SBT中最具活力的操作是一个独特的过程，Maintain。
Maintain(t)用来调整以t为根的SBT。假设t的子树在使用之前已经都是SBT。
由于性质a和性质b是对称的，所以我们仅仅详细的讨论性质a。
情况1：
插入后发生正如图2.1，我们可以执行以下的指令来修复SBT。
（1）首先执行Right-Ratote(t)，这个操作让图2.1变成图3.1；
图3.1
图3.1：所有结点的描述都和图2.1一样
（2）在这之后，有时候这棵树还仍然不是一棵SBT，因为或者也是可能发生的。所以就有必要继续调用Maintian(t)。
（3）结点L的右子树有可能被连续调整，因为有可能由于性质的破坏需要再一次运行Maintain(t)。
情况2：
在执行完Insert(left[t],v)后发生，如图3.2，这种调整要比情况1复杂一些。我们可以执行下面的操作来修复。
图3.2
图3.2：除了E、B、F以外，其他结点都和图2.1种的定义一样。E、F是结点B的子树。
（1）在执行完Left-Ratote(L)后，图3.2就会变成下面图3.3那样了。
图3.3
图3.3：所有结点的定义都和图3.2相同
（2）然后执行Right-Ratote(T)，最后的结果就会由图3.3转变成为下面的图3.4。
图3.4
图3.4：所有结点的定义都和图3.2相同
（3）在第（1）步和第（2）步过后，整棵树就变得非常不可预料了。万幸的是，在图3.4中，子树A、E、F和R仍就是SBT，所以我们可以调用Maintain(L)和Maintain(T)来修复结点B的子树。
（4）在第（3）步之后，子树都已经是SBT了，但是在结点B上还可能不满足性质a或性质b，因此我们需要再一次调用Maintain(B)。
情况3：
与情况1正好相反。
情况4：
与情况2正好相反。
3.1 标准Maintain的伪代码
通过前面的分析，很容易写出一个普通的Maintain。
Maintain (t)
1 If s[left[left[t]]>s[right[t]] then
2 Right-Rotate(t)
3 Maintain(right[t])
4 Maintain(t)
5 Exit
6 If s[right[left[t]]>s[right[t]] then
7 Left-Rotate(left[t])
8 Right-Rotate(t)
9 Maintain(left[t])
10 Maintain(right[t])
11 Maintain(t)
12 Exit
13 If s[right[right[t]]>s[left[t]] then
14 Left-Rotate(t)
15 Maintain(left[t])
16 Maintain(t)
17 Exit
18 If s[left[right[t]]>s[left[t]] then
19 Right-Rotate(right[t])
20 Left-Rotate(t)
21 Maintain(left[t])
22 Maintain(right[t])
23 Maintain(t)
3.2 更快更简单的Maintain的伪代码
前面的标准过程的伪代码有一点复杂和缓慢。通常我们可以保证性质a和性质b的满足，因此我们只需要检查情况1和情况2或者情况3和情况4，这样可以提高速度。所以在那种情况下，我们需要增加一个布尔（boolean）型变量，flag，来避免毫无疑义的判断。
如果flag是false，那么检查情况1和情况2；否则检查情况3和情况4。
Maintain (t,flag)
1 If flag=false then
2 If s[left[left[t]]>s[right[t]] then
3 Right-Rotate(t)
4 Else
5 If s[right[left[t]]>s[right[t]] then
6 Left-Rotate(left[t])
7 Right-Rotate(t)
8 Else
9 Exit
10 Else
11 If s[right[right[t]]>s[left[t]] then
12 Left-Rotate(t)
13 Else
14 If s[left[right[t]]>s[left[t]] then
15 Right-Rotate(right[t])
16 Left-Rotate(t)
17 Else
18 Exit
19 Maintain(left[t],false)
20 Maintain(right[t],true)
21 Maintain(t,false)
22 Maintain(t,true)
为什么Maintain(left[t],true)和Maintain(right[t],false)被省略了呢？Maintain操作的运行时间是多少呢？你可以在第6部分 分析 中找到答案。
4 插入
SBT中的插入很简单，下面是SBT中插入的伪代码。
4.1 插入的伪代码
Insert (t,v)
1 If t=0 then
2 t ← NEW-NODE(v)
3 Else
4 s[t] ← s[t]+1
5 If v6 Simple-Insert(left[t],v)
7 Else
8 Simple-Insert(right[t],v)
9 Maintain(t,v≥key[t])
5 删除
我增加了删除的简易程度，如果在SBT中没有这么一个值让我们删除，我们就删除搜索到的最后一个结点，并且记录它。下面是标准删除过程的伪代码。
5.1 删除的伪代码
Delete (t,v)
1 If s[t]≤2 then
2 record ← key[t]
3 t ← left[t]+right[t]
4 Exit
5 s[t] ← s[t]－1
6 If v=key[t] then
7 Delete(left[t],v[t]+1)
8 Key[t] ← record
9 Maintain(t,true)
10 Else
11 If v12 Delete(left[t],v)
13 Else
14 Delete(right[t],v)
15 Maintain(t,v5.2 更快更简单的删除伪代码
实际上这是没有任何其他功能的，最简单的删除。这里的Delete(t,v)是函数，它的返回值是被删除的结点的值。虽然他会破坏SBT的结构，但是使用上面的插入，它还是一棵高度为O(logn*)的BST。这里的n*是所有插入结点的个数，而不是当前结点的个数！
Delete (t,v)
1 s[t] ← s[t]－1
2 If (v=key[t])or(vkey[t])and(right[t]=0) then
3 Delete ← key[t]
4 If (left[t]=0)or(right[t]=0) then
5 t ← left[t]+right[t]
6 Else
7 key[t] ← Delete(left[t],v[t]+1)
8 Else
9 If v10 Delete(left[t],v)
11 Else
12 Delete(right[t],v)
6 分析
很明显，Maintain是一个递归过程，也许你会担心它是否能够停止。其实不用担心，因为已经能够证明Maintain过程的平摊时间时间是O(1)。
6.1 高度分析
设f[h]是高度为h的结点个数最少的SBT的结点个数。则我们有：
6.1.1 证明
（1）易证和。
（2）首先，。
对于每个，设t指向一个高度为h的SBT，然后这个SBT包含一个高度为h-1的子树。不妨设它就是左子树。
通过前面对于f[h]的定义，我们得到。
并且在左子树上有一棵高为h-2的子树，或者说有一棵大小（size）至少为f[h-1]的子树在左子树上。由性质b我们可得。
因此我们得出结论： 。
我们可以构造一个有f[h]个结点的SBT，它的高度是h。我们把这种SBT叫做tree[h]。
因此，宗上二点所述可得：。
6.1.2 最坏高度
实际上f[h]是指数级函数，它的准确值能够被递归的计算。
其中，
一些f[h]的常数值
H 13 15 17 19 21 23 25 27 29 31
F[h] 986 2583 6764 17710 46367 121392 317810 832039 2178308 5702886
定理
一个有n个结点的SBT，它在最坏情况下的高度是满足的最大h。
假设Maxh是有n个结点的SBT的最坏高度，通过上面的定理，我们有
现在可以很清楚地看到SBT的高度是O(logn)。
6.2 分析Maintain
通过前面的结论，我们可以很容易的证明Maintain过程是非常有效的过程。
评价一棵BST时有一个非常重要的值，那就是结点的平均深度。它是通过所有结点深度和除以总结点个数n获得的。通常它会很小，而BST会更小[4]。因为对于每个常数n，我们都期望结点深度和（缩写为SD）尽可能的小。
现在我们的目的是削减结点深度和，而它就是用来约束Maintain的次数[5]。
回顾一下Maintain中执行旋转的条件，会惊奇的发现结点深度和在旋转后总是在减小。
在情况1中，举个例子来说，比较图2.1和图3.1，深度和增加的是一个负数，。再举个例子，比较图3.2和图3.4，深度和增加的值比1小，是。
所以高度为O(logn)的树，深度和总是保持在O(nlogn)。而且在SBT中插入后，深度和仅仅只增加O(logn)。因此
在这里，T是Maintain中旋转的次数。Maintain的执行总次数就是T加上除去旋转的Maintain次数。所以Maintain的平摊运行时间是：
6.3 分析其它操作
现在SBT的高度是O(logn)，Maintain是O(1)，所有主要操作都是O(logn)。
6.4 分析更快更简单的删除
我们声明命题P(n*)，若有一棵已经插入了n*个结点并且有快速简单删除方法的BST，则它的高度为O(logn)[6]。我们通过数学方法来证明，对于任意整数n*，P(n*)都是成立的。
6.4.1 证明
这里我只给出大概的证明。
假设结点t已经被Maintain(t,false)检查过，则有
因此如果一个结点到根的路径上的所有结点都已经被Maintain检查过，那么这个结点的深度就是O(logn)。
（1）对于n*=1，很明显P(n*)是真的；
（2）假设对于P(n*)在n*（3）因此，当n*=1,2,3…时，P(n*)是正确的。
这种方法证明出来的Maintain平摊时间依旧是O(1)。
6.5 分析更快更简单的Maintain
这里讨论有关为什么Maintain(left[t],true)和Maintain(right[t],false)被省略。
在情况1的图3.1[8]中，我们有
因此Maintain(right[t],false)相当于图3.1中的Maintain(T,false)，能够被省略。同样的，Maintain(left[t],true)明显的也不需要。
在情况2的图3.2中，我们有
这些不平衡也意味着E的子树大小要比s[A]小，F的子树大小要比s[R]小。因而Maintain(right[t],false)和Maintain(left[t],true)可以被省略。
7 优点
7.1 SBT跑得快
7.1.2 典型问题
写一个执行n个由输入给定的操作，他们分别是：
在有序集合中插入一个给定的数字；
从有序集合中删除一个给定的数字；
返回一个给定的数字是否在有序集合中；
返回一个给定的数字在有序集合中的排名；
返回有序集合中第k大的数字；
返回有序集合中一个给定数字前面的数字；
返回有序集合中一个给定数字后面的数字。
7.1.2 统计
在现实中，Size Balanced Tree运行优秀，从上面的图表就能看出，同样都在随机数据的情况下，SBT比其它平衡BST要快得多。此外，如果是有序数据，SBT将会是意想不到的快速。它仅仅花费2s就将200万个有序数据结点插入到SBT中。
7.2 SBT运行高效
当Maintain运行的时候平均深度一点也不会增加，因为SBT总是趋近于一个完美的BST。
插入200万个随机值结点
类型 SBT AVL Treap 随机BST Splay 完美的BST
平均深度 19.2415 19.3285 26.5062 25.5303 37.1953 18.9514
高度 24 24 50 53 78 20
旋转次数 1568017 1395900 3993887 3997477 25151532
插入200万个有序值结点
类型 SBT AVL Treap 随机BST Splay 完美的BST
平均深度 18.9514 18.9514 25.6528 26.2860 999999.5 18.9514
高度 20 20 51 53 1999999 20
旋转次数 1999979 1999979 1999985 1999991 0
7.3 SBT调试简单
首先我们可以输入一个简单的BST来保证不会出错，然后我们在插入过程中加入Maintain，并调试。如果发生错误也只需要调试和修改Maintain。此外，SBT不是基于随机性的数据结构，所以它要比Treap，跳跃表（Skip List），随机BST等更稳定。
7.4 SBT书写简单
SBT几乎是和BST同样简单。仅仅在插入过程中有一个附加的Maintain，它也仅仅比BST先旋转[9]。而且Maintain也是同样的相当容易。
7.5 SBT小巧玲珑
许许多多的平衡二叉搜索树，例如SBT，AVL，Treap，红黑树等等都需要额外的域去保持平衡。但是他们中的很多都有着毫无用处的域，像高度（height），随机因子（random factor）和颜色（color）。而相反的是SBT包含一个十分有用的额外域，大小（size）域。通过它我们可以让BST支持选择（Select）操作和排名（Rank）操作。
7.5 SBT用途广泛
现在SBT的高度是O(logn)，即便在最坏情况下我们也可以在O(logn)时间内完成Select过程。但是这一点伸展树（Splay）却不能很好的支持。因为它的高度很容易退化成O(n)。上面的图表已经显示出这一点[10]。
感谢
作者感谢他的英语老师Fiona热情的帮助。
参考
[1] G.M.Adelson-Velskii and E.M.Landis, “An algorithm for the Organization of Information”, Soviet.Mat.Doklady (1962)
[2] L.J.Guibas and R.Sedgewick, “A dichromatic Framework for Balanced Trees”, Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computer Science (1978)
[3] D. D. Sleator and R. E. Tarjan, ‘Self-adjusting binary search trees’, JACM, 32, 652–686 (1985).
[4] S.W.Bent and J.R.Driscoll, Randomly balanced searchtrees. Manuscript (1991).
[5] Raimund Seidel and Cecilia R. Aragony, Randomized Search Trees.(1996).
[6] M.A.Weiss, ‘‘Data Structures and Algorithm Analysis in C++’’, Third Edition, Addison Wesley, 2006.
[7] R.E. Tarjan, ‘‘Sequential access in splay trees takes linear time’’, Combinatorica 5(4), 1985, pp. 367-378.
[8] J. Nievergelt and E. M. Reingold, ‘Binary search trees of bounded balance’, SIAM J. Computing, 2, 33–43 (1973).
[9] K.Mehlhorn, and A.Tsakalidis, “Data Structures,” in Handbook of Theoretical Computer Science, Chapter 6, Vol.A, pp.303–341, Elsevier Science Publishers,(1990)
注释
以下是译者在文章中的注释。
[1] 高级二叉搜索树，Advance Binary Search Tree，或者也可以叫做附加二叉搜索树，都是在BST基础上作了一定改进的数据结构，譬如AVL，Treap，伸展树等。[回去1]
[2] 指针，在本文中作者使用的都是静态指针，也就是数组的下标。[回去2]
[3] 本地运算，local operation，也较原地运算，就是基本不依赖其他附加结构、空间的运算。[回去3]
[4] 原文为：“Generally the less it is, the better a BST is.”[回去4]
[5] 原文为：“Now we need to concentrate on SD. Its significance is the ability to restrict the times of Maintain.”SD是“the sum of the depths of all nodes”，即结点深度和。[回去5]
[6] 原文为：“We call the statement P(n*) that a BST with the faster and simpler Delete and n* standard Inserts is at the height of O(logn*).” [回去6]
[7] 原文为：“For every leaf of this tree, the subtree pointed by it does not be changed by Maintain.” [回去7]
[8] 原文中这里是图3.2，可是情况1中只有图3.1，图3.2是在情况2后面，于是将它改为了“图3.1”。原文为：“In case 1 in Figure 3.2” [回去8]
[9] 原文为：“Removing the only additional Maintain in Insert the former turns to be the latter.” [回去9]
[10] 原文为：“which is exposed by the char above”，其中char个人认为是输入错误，应该是“chart”。[回去10]
译者的话
因为网上和朋友那里四处都找不到陈启峰Size Balanced Tree中文版的论文，当然也就不知道怎么翻译SBT更好一些了，于是就这么写上去了，相信有点OI常识的人看了都知道SBT是怎么一回事。
关于这篇翻译过来的中文版的论文，目前还没有给陈启峰本人看过，希望他和各位大牛看过之后不要鄙视，能尽量挑出一些错误来，我就很感激了。还有其中的一些语言，特别是分析证明的那一部分，由于叶子我英语和OI水平有限，怕翻译出错，把可能认为理解有误，或者不好用中文表达，或者自己表达得不够清晰的部分在后面加了注释。
翻译陈启峰这篇论文的原动力是因为英语版看着太费劲，我是这样，相信大多数人都应该是这样，都是中国人，推广以下新东西，是十分必要的，当然最好能够语言本土化，于是我就花了两三天功夫翻译了一下。
还有论文中原来的图片、图表，我都经过了再加工，相信看起来更漂亮（^-^）。关于文字大小，小五是宋体看得清楚的最小字体，也很清秀，如果看不清楚，可以放大，但希望您能不要修改，都是排好版的，很容易乱的。
尽管是翻译，也是我的劳动成果，如果发现翻译错误，或文字错误，请联系我。
也请您不要修改本文，Word文档是为了大家更好的使用、查看。
我的E-Mail：combooleaf@21cn.com
我的QQ：541206837
我的Blog：竹叶小店 http://combooleaf.blog.hexun.com ( http: / / combooleaf.blog.hexun.com ) 欢迎观光
最后再崇拜一下陈启峰大牛，谢谢。
Y
X
C
B
A
Y
X
C
B
A
左旋（Left-Ratote）
右旋（Right-Ratote）
T
L
R
A
B
C
D
L
A
T
R
B
C
D
T
L
R
A
B
C
D
E
F
T
B
R
L
F
C
D
A
E
B
L
T
A
E
F
D
C
D
插入200万个随机值结点
单位：秒
16
14
12
10
8
6
4
2
0
SBT
7.13
AVL
8.34
Treap
11.36
Random BST
13.61
200万个操作，66%为插入，33%为删除，全部随机
单位：秒
16
14
12
10
8
6
4
2
0
SBT
5．59
AVL
7．42
Treap
8．86
Random BST
10．47
200万个操作，20%为插入，10%为删除，60%查询，全部随机
单位：秒
8
7
6
5
4
3
2
1
0
SBT
3．39
AVL
4．42
Treap
5．67
Random BST
6．21QUOTE:
Sorry,iRabbit，我修改改了你的帖子，你用了HTML代码，似乎不是很美观，还是用纯文本吧
By Wasltone
1258
Agri-Net
USACO 102
1944
Fiber Communications
USACO 2002 February
1945
Power Hungry Cows
USACO 2002 February
1946
Cow Cycling
USACO 2002 February
1947
Rebuilding Roads
USACO 2002 February
1948
Triangular Pastures
USACO 2002 February
1949
Chores
USACO 2002 February
1950
Dessert
USACO 2002 February
1951
Extra Krunch
USACO 2002 February
1952
BUY LOW, BUY LOWER
USACO 2002 February
2184
Cow Exhibition
USACO 2003 Fall
2185
Milking Grid
USACO 2003 Fall
2186
Popular Cows
USACO 2003 Fall
2187
Beauty Contest
USACO 2003 Fall
2188
Cow Laundry
USACO 2003 Fall Orange
2189
Romeo Meets Juliet
USACO 2003 Fall Orange
2190
ISBN
USACO 2003 Fall Orange
2132
Cow Math
USACO 2003 February Green
2133
Cow Imposters
USACO 2003 February Green
2134
Traffic Lights
USACO 2003 February Green
2135
Farm Tour
USACO 2003 February Green
2136
Vertical Histogram
USACO 2003 February Orange
2137
Cowties
USACO 2003 February Orange
2138
Travel Games
USACO 2003 February Orange
2018
Best Cow Fences
USACO 2003 March Green
2019
Cornfields
USACO 2003 March Green
2139
Six Degrees of Cowvin Bacon
USACO 2003 March Orange
2140
Herd Sums
USACO 2003 March Orange
2141
Message Decowding
USACO 2003 March Orange
2110
Mountain Walking
USACO 2003 U S Open
2111
Millenium Leapcow
USACO 2003 U S Open
2112
Optimal Milking
USACO 2003 U S Open
2180
Bale Figures
USACO 2003 U S Open Orange
2181
Jumping Cows
USACO 2003 U S Open Orange
2182
Lost Cows
USACO 2003 U S Open Orange
2183
Bovine Math Geniuses
USACO 2003 U S Open Orange
2373
Dividing the Path
USACO 2004 December Gold
2374
Fence Obstacle Course
USACO 2004 December Gold
2375
Cow Ski Area
USACO 2004 December Gold
2376
Cleaning Shifts
USACO 2004 December Silver
2377
Bad Cowtractors
USACO 2004 December Silver
2378
Tree Cutting
USACO 2004 December Silver
1984
Navigation Nightmare
USACO 2004 February
1985
Cow Marathon
USACO 2004 February
1986
Distance Queries
USACO 2004 February
1987
Distance Statistics
USACO 2004 February
2008
Moo University - Team Tryouts
USACO 2004 March Green
2009
Moo University - Emergency Pizza Order
USACO 2004 March Green
2010
Moo University - Financial Aid
USACO 2004 March Green
2385
Apple Catching
USACO 2004 November
2386
Lake Counting
USACO 2004 November
2387
Til the Cows Come Home
USACO 2004 November
2388
Who's in the Middle
USACO 2004 November
2389
Bull Math
USACO 2004 November
2390
Bank Interest
USACO 2004 November
1988
Cube Stacking
USACO 2004 U S Open
1989
The Cow Lineup
USACO 2004 U S Open
1990
MooFest
USACO 2004 U S Open
1991
Turning in Homework
USACO 2004 U S Open
2454
Jersey Politics
USACO 2005 February Gold
2455
Secret Milking Machine
USACO 2005 February Gold
2456
Aggressive cows
USACO 2005 February Gold
2457
Part Acquisition
USACO 2005 February Silver
2458
Rigging the Bovine Election
USACO 2005 February Silver
2459
Feed Accounting
USACO 2005 February Silver
2226
Muddy Fields
USACO 2005 January Gold
2227
The Wedding Juicer
USACO 2005 January Gold
2228
Naptime
USACO 2005 January Gold
2229
Sumsets
USACO 2005 January Silver
2230
Watchcow
USACO 2005 January Silver
2231
Moo Volume
USACO 2005 January Silver
2391
Ombrophobic Bovines
USACO 2005 March Gold
2392
Space Elevator
USACO 2005 March Gold
2393
Yogurt factory
USACO 2005 March Gold
2394
Checking an Alibi
USACO 2005 March Silver
2395
Out of Hay
USACO 2005 March Silver
2430
Lazy Cows
USACO 2005 U S Open Gold
2431
Expedition
USACO 2005 U S Open Gold
2432
Around the world
USACO 2005 U S Open Gold
2433
Landscaping
USACO 2005 U S Open Gold
2434
Waves
USACO 2005 U S Open Silver
2435
Navigating the City
USACO 2005 U S Open Silver
2436
Disease Manangement
USACO 2005 U S Open Silver
2437
Muddy roads
USACO 2005 U S Open Silver
1274
The Perfect Stall
USACO 40
1273
Drainage Ditches
USACO 93
1630
Max Separation
福建OI2001
1714
The Cave
CEOI 1997
1715
Hexadecimal Numbers
CEOI 1997
1716
Integer Intervals
CEOI 1997
1717
Dominoes
CEOI 1997
1718
River Crossing
CEOI 1997
1719
Shooting Contest
CEOI 1997
1720
SQUARES
CEOI 1998
1721
CARDS
CEOI 1998
1722
SUBTRACT
CEOI 1998
1723
SOLDIERS
CEOI 1998
1724
ROADS
CEOI 1998
1725
BALL
CEOI 1998
1731
Orders
CEOI 1999
1732
Phone numbers
CEOI 1999
1733
Parity game
CEOI 1999
1734
Sightseeing trip
CEOI 1999
1735
A Game on the Chessboard
CEOI 1999
1736
Block Town
CEOI 1999
1661
Help Jimmy
CEOI 2000
1037
A decorative fence
CEOI 2002
1038
Bugs Integrated, Inc.
CEOI 2002
1912
A highway and the seven dwarfs
CEOI 2002
1920
Towers of Hanoi
CEOI 2003
1934
Trip
CEOI 2003
2274
The Race
CEOI 2003
1935
Journey
CEOI 2004 sample task
1839
Cattle
Croatia OI 2002
1841
Meadow
Croatia OI 2002
1842
Parking
Croatia OI 2002
1149
PIGS
Croatia OI 2002 Final Exam - First day
1153
SAFE
Croatia OI 2002 Final Exam - First day
1155
TELE
Croatia OI 2002 Final Exam - Second Day
1849
Two
Croatia OI 2002 national – second day, seniors
1847
Tram
Croatia OI 2002 Regional - Juniors
1154
LETTERS
Croatia OI 2002 Regional Competition - Juniors
1163
The Triangle
IOI 1994
1164
The Castle
IOI 1994
1165
The Primes
IOI 1994
1166
The Clocks
IOI 1994
1167
The Buses
IOI 1994
1168
The Circle
IOI 1994
1169
Packing Rectangles
IOI 1995
1170
Shopping Offers
IOI 1995
1171
Letter Game
IOI 1995
1172
Street Race
IOI 1995
1173
Bar Codes
IOI 1995
1236
Network of Schools
IOI 1996
1174
Contact
IOI 1998
1175
Starry Night
IOI 1998
1176
Party Lamps
IOI 1998
1177
Picture
IOI 1998
1178
Camelot
IOI 1998
1179
Polygon
IOI 1998
1156
A STRIP OF LAND
IOI 1999
1157
LITTLE SHOP OF FLOWERS
IOI 1999
1158
TRAFFIC LIGHTS
IOI 1999
1194
HIDDEN CODES
IOI 1999
1159
Palindrome
IOI 2000
1160
Post Office
IOI 2000
1161
Walls
IOI 2000
1162
Building with Blocks
IOI 2000
1195
Mobile phones
IOI 2001
1196
Twofive
IOI 2001
1197
Depot
IOI 2001
1147
Binary codes
IOI 2001 备选题
1054
The Troublesome Frog
IOI 2002
1148
Utopia Divided
IOI 2002
1180
Batch Scheduling
IOI 2002
1181
Bus Terminals
IOI 2002
1655
Balancing Act
IOI 2003 sample task
1067
取石子游戏
NOI
1182
食物链
Noi 01
1183
反正切函数的应用
Noi 01
1184
聪明的打字员
Noi 01
1185
炮兵阵地
Noi 01
1186
方程的解数
Noi 01
1187
陨石的秘密
Noi 01
1189
钉子和小球
Noi 99
1190
生日蛋糕
Noi 99
1191
棋盘分割
Noi 99
1192
最优连通子集
Noi 99
1193
内存分配
Noi 99
1283
Moving Computer
NOIP 2001
1602
Zip
浙江OI 2001
1271
Nice Milk
OIBH Online Programming Contest(OOPC)#1
1090
Chain
POI 2001
1089
Intervals
POI VIII Stage 1 Problem 2
1818
ATP
Romania OI 2002
1819
Disks
Romania OI 2002
1820
Expression
Romania OI 2002
1821
Fence
Romania OI 2002
1822
Fence2
Romania OI 2002
1823
Hotel
Romania OI 2002
1824
TwoFour
Romania OI 2002
1825
Young
Romania OI 2002
1836
Alignment
Romania OI 2002
1837
Balance
Romania OI 2002
1838
Banana
Romania OI 2002
1840
Eqs
Romania OI 2002
1843
Shire
Romania OI 2002
1844
Sum
Romania OI 2002
1845
Sumdiv
Romania OI 2002
1846
System
Romania OI 2002
1848
Tree
Romania OI 2002
1850
Code
Romania OI 2002[分享][KMP]串匹配的高效算法-KMP
[Copy to clipboard]
CODE:
对于两个串，我们设一个串为主串S,一个串为模式串s,即要求s在S中的位置。
当两串匹配到s的位置i时发现不匹配，这时不需要从头来匹配，可以从s的位置k来匹配(k>=1)，这就是KMP算法的精华之处。
S1,S2,S3,S4..SN
s1,s2,s3,s4..sn
由已知匹配可知
S(i-k+1),S(i-k)..S(i-1)=s(i-k+1),s(i-k)..s(i-1)
由k的解释可知
S(i-k+1),S(i-k)..S(i-1)=s1,s2..s(k-1)
所以有
s1,s2..s(k-1)=s(i-k+1),s(i-k)..s(i-1)
可以发现k的值与主串S无关，关键在于求出s中每个位置j对应的k。
设f(j)为j所对应的k，则有：
f(j)=0 (j=1)
f(j)=max{k(0以上是推导过程，下面介绍求k的方法：
s,k:array[1..n]of integer;
开始设k[1]:=0;
for i:=2 to n do
begin
j:=i-1;{初始j}
while not((s[i-1]=s[k[j]]) or (j=1)) do
j:=k[j];
{直到找到一个j，使得s[i-1]=s[k[j]],则k[j]+1为所求}
k[i]:=j+1;
end;
求出k以后，接下来的事情就好办多了，用m,n记录S和s中的位置，从左到右扫一遍就行了。
这个算法的复杂度是多项式的
写得有点抽象...........
刚刚翻到的，zqy写的
[Copy to clipboard]
CODE:
[原创]KMP算法总结
关于模式匹配(KMP)的解题报告
by zqy
引言:模式匹配是串的操作中最重要的一种,而KMP算法是一种相当高效的模式匹配算法(下文中将提到它的时间复杂度为O(m+n)).所以,KMP算法是我们必须掌握的一种基本方法.
正文:
1. 朴素的模式匹配算法.
朴素的模式匹配算法的核心思想是:一旦某个字符匹配失败,从头开始(即从本次匹配起点后一个字符开始).因此朴素的模式匹配算法的时间复杂度为O(mn),它的时间无法让人们满意,于是新的模式匹配算法也就孕育而生了.
在介绍KMP算法之前,我们先来看一下为什么朴素的模式匹配算法无法令人满意.
主串:ababcabcacbab 模式串:abcac
第一次比较:主串第三个位置出错,起点向后一位.
第二次比较:主串第二个位置出错,起点向后一位.
第三次比较:主串第七个位置出错,起点向后一位.
第四次比较:主串第四个位置出错,起点向后一位.
第五次比较:主串第五个位置出错,起点向后一位.
第六次比较:成功!
仔细观察我们可以发现,第一次比较错误以后,完全可以把起点放到主串的第三位,而不是第二位(因为根据已有的判断,第二位去比较肯定不会成功).因此第二次比较是无效比较.正是因为诸如上例中第二次比较的无效比较,使得算法不够理想.
2. KMP算法
2.1Next的函数的引出:
通过上述分析我们可以知道,要想改进模式匹配的算法,必须减少无效比较,让起点自动移到当前认为的最理想的位置,而不是仅仅只移一位.但是,计算机怎么知道要移几位呢 这就需要一个先开始就制定好的函数.于是我们就引出了next函数.
2.2Next的函数的定义和计算:
next的函数到底是什么呢 根据我的理解,next[i]表示当模式串中第i个字符与主串某个字符比较失败后,起点应该向后移几位.那么,next函数的值怎么求呢
显然,如果模式串第一位就比较错了,只能移动一位.为了和后面以示区别,我们定义next[1]=0.那么,其他的next怎么求呢
我们回过头来仔细分析next函数的定义,发现它就是在求最大的k使得’P1..Pk’=’Pi-k+1..Pi’,因此,next[i]的求法如下
若i=1,则next[i]=0;
若Pi=Pnext[i-1]+1,则next[i]=next[i-1]+1;
其它情况则next[i]=1;
因此计算next函数的过程如下:
procedure count_next;
var i,j:integer;
begin
i:=1;j:=0;next[1]:=0;
while ibegin
if (j=0)or(t[i]=t[j]) then
begin
inc(i);
inc(j);
next[i]:=j;
end
else j:=next[j];
end;
end;
效率分析:这个过程的时间复杂度为O(n),其中n为模式串的长度.由于n通常比主串的长度小得多,因此整个过程花不了多少时间,是值得的.
2.3主程序
有了next的函数,KMP算法的主程序就容易编了.还是顺次匹配,一旦不成功,起点向后移动next[j]位,程序如下:
procedure KMP_index;
var i,j:integer;
changed:boolean;
begin
count_next;
i:=1;j:=1;
changed:=false;
while (i<=length(s))and(j<=length(t)) do
begin
if (j=0)or(s[i]=t[j]) then
begin
inc(i);
inc(j);
end
else j:=next[j];
if j>length(t) then begin writeln('Place:',i-length(t));changed:=true;j:=1;end;
end;
if not changed then writeln('No Answer');
end;
注明:这个主程序可以找出模式串在主串中的所有位置.
效率分析:这个过程的时间复杂度位O(m),m为主串的长度,加上前面计算next函数所用的时间,整个算法的复杂度为O(m+n),确实优于朴素的模式匹配.
3. 总结:KMP算法首先抓住普通模式匹配算法之所以不优秀的原因,然后分析怎样才能解决,因此我们最常用的模式匹配的算法也就产生了.因此,KMP算法是一个相当优秀的模式匹配算法.
附录:
程序清单:
program KMP;
var s,t:string;
next:array[1..100] of longint;
procedure count_next;
var i,j:integer;
begin
i:=1;j:=0;next[1]:=0;
while ibegin
if (j=0)or(t[i]=t[j]) then
begin
inc(i);
inc(j);
next[i]:=j;
end
else j:=next[j];
end;
end;
procedure KMP_index;
var i,j:integer;
changed:boolean;
begin
count_next;
i:=1;j:=1;
changed:=false;
while (i<=length(s))and(j<=length(t)) do
begin
if (j=0)or(s[i]=t[j]) then
begin
inc(i);
inc(j);
end
else j:=next[j];
if j>length(t) then begin writeln('Place:',i-length(t));changed:=true;j:=1;end;
end;
if not changed then writeln('No Answer');
end;
begin
readln(s);
readln(t);
KMP_index;
end.第三题 分割矩阵（separation.pas/c）
将一个a*b的数字矩阵进行如下分割：将原矩阵沿某一条直线分割成两个矩阵，再将生成的两个矩阵继续如此分割（当然也可以只分割其中的一个），这样分割了（n-1)次后，原矩阵被分割成了n个矩阵。（每次分割都只能沿着数字间的缝隙进行）
原矩阵中每一位置上有一个分值，一个矩阵的总分为其所含各位置上分值之和。现在需要把矩阵按上述规则分割成n个矩阵，并使各矩阵总分的均方差最小。
均方差，其中平均值，xi为第i个矩阵的总分。
请编程对给出的矩阵及n，求出均方差的最小值。
输入文件（separation.in)
第一行为3个整数，表示a,b,n(1 第二行至第n+1行每行为b个小于100的非负整数，表示矩阵中相应位置上的分值。每行相邻两数之间用一个空格分开。
输出文件（separation.out）
仅一个数，为均方差的最小值（四舍五入精确到小数点后2位）
样例输入
5 4 4
2 3 4 6
5 7 5 1
10 4 0 5
2 0 2 3
4 1 1 1
样例输出
0.50
【算法简析】
这题和NOI99《棋盘分割》十分类似，可以完全仿照那题的方法来做。
由于n是确定的，预处理的时候可以直接求出
本题的状态和决策都是很明显的。用一个四元组(x1,y1,x2,y2)表示以(x1,y1)为左上角，(x2,y2)为右下角的矩阵的最优值，决策就是把该矩阵划分为两个相邻子矩阵的方法——“横切一刀”或者“竖切一刀”。但是单纯这样做本题的阶段就不明显了，原因是还有划分个数这一限制。这样，我们就需要在状态中再加一维k表示分割成k个子矩阵。
设f[x1,y1,x2,y2,k]表示以(x1,y1)为左上角，(x2,y2)为右下角的矩阵分割成k个子矩阵的最优值，则：
sum(x1,y1,x2,y2) k=1
f[x1,y1,x2,y2,k]= min{f[x1,y1,x’,y2,k]+f[x’+1,y1,x2,y2,k]} (k>1) and (x1min{f[x1,y1,x2,y’,k]+f[x1,y’+1,x2,y2,k]} (k>1) and (y1其中sum(x1,y1,x2,y2)表示矩形(x1,y1,x2,y2)的权和减去后求二次幂的值。
状态是五维的，所以空间复杂度为O(105)，由于决策是O(n2)的，时间复杂度为O(107)。但是实际上有效状态很少，加上本身题目规模并不大，可以用记忆化搜索实现，时间复杂度远远达不到上限。DB不完全手册
GDB即GNU Debug,是GNU下的调试器.主要是用在linux下面。但是也有人把它移植到Win32平台上面,这样我们常常在Windows下面的人也有机会接触到这个非常优秀的调试器。
Free Pascal 一直都是调用GDB来调试程序，FP 2.0.2版本中间的GDB版本为6.2.1。然而Free Pascal的IDE在Windows下面一直饱受不稳定的责难，因此很多人都不喜欢在IDE里面直接调试程序。但是做为调试器GDB还是非常优秀，但是很多人在直接面对命令行调试程序时非常不习惯，更重要的是不会使用GDB的指令.对此,我给出我在使用GDB时的心得，希望大家能够喜欢，从中受益。
由于水平有限，时间仓促（一天内写的），错误之处在所难免，不足之处敬请大家批评指正！如若有所更正，我会在我的WebSite公布，而不会到处声明咯，希望大家见谅。
特别鸣谢：jyy等帮助我的人。
发布的Page:http://www./ p=95
By Devil
暂定版本号Ver 0.1吧。希望LZ能早日更新版本，改正错误和增加新的内容！！！http://starforever.blog.hexun.com/list.aspx tag=NOIP第二题 修筑绿化带（parterre.pas/c/cpp）
为了增添公园的景致，现在需要在公园中修筑一个花坛，同时在画坛四周修建一片绿化带，让花坛被绿化带围起来。
如果把公园看成一个M*N的矩形，那么花坛可以看成一个C*D的矩形，绿化带和花坛一起可以看成一个A*B的矩形。
如果将花园中的每一块土地的“肥沃度”定义为该块土地上每一个小块肥沃度之和，那么，
绿化带的肥沃度=A*B块的肥沃度-C*D块的肥沃度
为了使得绿化带的生长得旺盛，我们希望绿化带的肥沃度最大。
输入
第一行有6个正整数M,N,A,B,C,D
接下来一个M*N的数字矩阵，其中矩阵的第i行j列元素为一个整数Xij,表示该花园的第i行第j列的土地“肥沃度”。
输出
一个正整数，表示绿化带的最大肥沃程度。
样例
parterre.in
4 5 4 4 2 2
20 19 18 17 16
15 14 13 12 11
10 9 8 7 6
5 4 3 2 1

parterre.out
132
数据范围
30%的数据，1<=M,N<=50
100%的数据，1<=M,N<=1000,1<=A<=M,1<=B<=N,1<=C<=A-2,1<=D<=B-2，1<=“肥沃度”<=100
【算法简析】
和day1-2《理想的正方形》的方法极其相似。
首先我们可以利用迭代的思想在O(nm)的时间内求出所有a*b和c*d的矩形的权和。
我们的目标是求出所有a*b的矩形中对应的最小的c*d的矩形。现在我们将所有的c*d的矩形看作一个点，则问题就转化为和《理想的正方形》一模一样的形式，可以完全仿照那题的方法来做。
最后用O(nm)的枚举找到所有a*b的矩形减去其中最小的c*d的矩形的权和的差的最大值。
算法总时间复杂度为O(nm)。

展开更多......

收起↑