資源簡介

最后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)?？臻g為O(n^2)。
顯然O(n^4)過這個題目是有點欠缺的，對的大的數據貌似很容易超時的。
　　如果仔細想想，我們還是做了很不重復的工作的，不同的展開方式中必然存在著很多的大量的重復運算。于是還有很大的優化空間，既然展開做了很多的重復的工作，那么就合并起來吧?；氐狡瘘c，開始的時候為什么我們要對項鏈做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進行了優化。
　?。ǜ匠绦颍?br/>　　到這里我們可以很完美的過這個題目的所以數據了；但還是覺得不夠快，想用四邊形優化，但想了想顯然是不可以的，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題目?？上耶敃r沒做出來。
　　草率的審題，可能會得到這樣的算法：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的狀態?？梢缘玫饺缦碌膁p方程：
　　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）的條件下，插入到最前面的一個空檔?！?br/>　　建議大家在考試的時候使用數組，平時可以用指針寫一寫……
　　（附程序）；
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進制數
　　這就是傳說中的數學題嗎 考試前曾沸沸揚揚的流傳過這么一段：“今年的題目出于一數學教授，都是寫超難的題目，四個題目有三個是數學題?！痹偌由辖衲甑膍aths庫函數登上歷史舞臺。更讓人深信不移：今年要考數學題。
　　謠言不可信啊，冤死了多少牛們……
　　說本題是數學題，到不如說是個找規律的題目。
　　我們還是用標準的數學方法做一下好了。本題其實就是個很簡單的組合數學問題。沒上過高三做不出也就算了，上過高三的牛們沒做出來，多為放棄的了。
　　從題中可以看出，w的值限制著首位的取值。所以我們要對與特殊考慮。比如樣例中的w=7，就限制了首位只能?。昂停薄Ｏ旅骊P心的就是位數的問題了，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]，然后用同樣的推算方法可以由這個一維的狀態可以推算出二維的狀態?，F在我們的任務就是在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，顧名思義，這是一棵通過大?。⊿ize）域來維持平衡的二叉搜索樹。
這是一種簡單、高效并且在各方面都通用的數據結構。
這也是一種很容易被語言工具表述的數據結構，它有著簡單明了的定義，和令人驚嘆的運行速度，而且你會驚訝于它簡單的證明。
這是目前為止速度最快的高級二叉搜索樹[1]]。
此外，它比其它一些知名的高級二叉搜索樹要快得多，并且在實踐中趨于完美。
它不僅支持典型的二叉搜索樹操作，而且也支持Select和Rank。
關鍵字
Size Balanced Tree
SBT
Maintain
翻譯 By 竹子的葉子
文檔經過處理，可以使用“視圖”——“文檔結構圖”來方便閱讀。
希望大家不要隨便修改，謝謝！
1 介紹
在展現Size Balanced Tree之前，有必要詳細說明一下二叉搜索樹的旋轉，左旋（Left-Ratote）和右旋（Right-Ratote）。
1.1 二叉搜索樹
二叉搜索樹是一種非常重要的高級數據結構，它支持很多動態操作，其中包括搜索（Search），取?。∕inimum），取大（Maximun），前驅（Predecessor），后繼（Successor），插入（Insert）和刪除（Delete）。它能夠同時被當作字典和優先隊列使用。
二叉搜索樹是按照二叉樹結構來組織的，樹中的每個節點最多只有兩個兒子，二叉搜索樹中關鍵字的儲存方式總是滿足以下二叉搜索樹的性質：
設x是二叉搜索樹中的一個結點，那么x的關鍵字不小于左子樹中的關鍵字，并且不大于右子樹中的關鍵字。
對于每一個結點t，我們使用left[t]和right[t]來儲存它兩個兒子的指針[2]，并且我們定義key[t]來表示結點t用來做比較的值。另外，我們增加s[t]，表示以t為根的子樹的大?。⊿ize），維持它成為這棵樹上結點的個數。特別地，當我們使用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）是一種通過大?。⊿ize）域來保持平衡的二叉搜索樹。它支持許多運算時間級別為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）和取?。∕inimun），取大等價于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的子樹，或者說有一棵大?。╯ize）至少為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包含一個十分有用的額外域，大?。╯ize）域。通過它我們可以讓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)?？臻g為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題目?？上耶敃r沒做出來。
　　草率的審題，可能會得到這樣的算法：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，不成問題?？臻g32000*60*60，大約要7.5M的空間，在64M的要求下是完全可以的過的。如果用上題目中的一個很隱秘的條件：“每件物品都是10元的整數倍”，就可以把速度在提高十倍。
　　細細的看題目，還一個很重要的條件我們還沒用：“每個主件可以有０個，１個或２個附件”。這貌似不起眼的一句話，卻給我們降低復雜度提供了條件。想一想，為什么題目要對附件的個數做限制呢，明顯是在降低難度。
　　對于一套物品（包含主件，所以的附件），我們稱為一個屬類，對一個屬類的物品的購買方法，有以下５種：
　　　?。?一個都不買
　　　?。?主件
　　　　３.主件＋附件１
　　　　４.主件＋附件２
　　　?。?主件＋附件１＋附件２
　　這五種購買方法也是唯一的五種方法，也就是說對一屬類的物品，我們只有上述的５種購買方法。
　　于是我們很自然的就會想到把物品按物品的屬類捆在一起考慮。這樣我們把物品的屬類作為dp的狀態?？梢缘玫饺缦碌膁p方程：
　　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）的條件下，插入到最前面的一個空檔。”
　　建議大家在考試的時候使用數組，平時可以用指針寫一寫……
　?。ǜ匠绦颍?br/>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?！∥粩担簂=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，顧名思義，這是一棵通過大?。⊿ize）域來維持平衡的二叉搜索樹。
這是一種簡單、高效并且在各方面都通用的數據結構。
這也是一種很容易被語言工具表述的數據結構，它有著簡單明了的定義，和令人驚嘆的運行速度，而且你會驚訝于它簡單的證明。
這是目前為止速度最快的高級二叉搜索樹[1]]。
此外，它比其它一些知名的高級二叉搜索樹要快得多，并且在實踐中趨于完美。
它不僅支持典型的二叉搜索樹操作，而且也支持Select和Rank。
關鍵字
Size Balanced Tree
SBT
Maintain
翻譯 By 竹子的葉子
文檔經過處理，可以使用“視圖”——“文檔結構圖”來方便閱讀。
希望大家不要隨便修改，謝謝！
1 介紹
在展現Size Balanced Tree之前，有必要詳細說明一下二叉搜索樹的旋轉，左旋（Left-Ratote）和右旋（Right-Ratote）。
1.1 二叉搜索樹
二叉搜索樹是一種非常重要的高級數據結構，它支持很多動態操作，其中包括搜索（Search），取?。∕inimum），取大（Maximun），前驅（Predecessor），后繼（Successor），插入（Insert）和刪除（Delete）。它能夠同時被當作字典和優先隊列使用。
二叉搜索樹是按照二叉樹結構來組織的，樹中的每個節點最多只有兩個兒子，二叉搜索樹中關鍵字的儲存方式總是滿足以下二叉搜索樹的性質：
設x是二叉搜索樹中的一個結點，那么x的關鍵字不小于左子樹中的關鍵字，并且不大于右子樹中的關鍵字。
對于每一個結點t，我們使用left[t]和right[t]來儲存它兩個兒子的指針[2]，并且我們定義key[t]來表示結點t用來做比較的值。另外，我們增加s[t]，表示以t為根的子樹的大?。⊿ize），維持它成為這棵樹上結點的個數。特別地，當我們使用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）是一種通過大?。⊿ize）域來保持平衡的二叉搜索樹。它支持許多運算時間級別為O(logn)的主要操作：
Insert(t,v) 在以t為根的SBT中插入一個關鍵字為v的結點。
Delete(t,v) 從以t為根的SBT中刪除一個關鍵字為v的結點，如果樹中沒有一個這樣的結點，刪除搜索到的最后一個結點。
Find(t,v) 查找并返回結點關鍵字為v的結點。
Rank(t,v) 返回v在以t為根的樹中的排名，也就是比v小的那棵樹的大?。⊿ize）加一。
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的子樹，或者說有一棵大?。╯ize）至少為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包含一個十分有用的額外域，大?。╯ize）域。通過它我們可以讓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：[email protected]
我的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個矩陣。（每次分割都只能沿著數字間的縫隙進行）
原矩陣中每一位置上有一個分值，一個矩陣的總分為其所含各位置上分值之和?，F在需要把矩陣按上述規則分割成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的矩形?，F在我們將所有的c*d的矩形看作一個點，則問題就轉化為和《理想的正方形》一模一樣的形式，可以完全仿照那題的方法來做。
最后用O(nm)的枚舉找到所有a*b的矩形減去其中最小的c*d的矩形的權和的差的最大值。
算法總時間復雜度為O(nm)。

展開更多......

收起↑