【筆記】名題精選百則-心得

我非常喜歡這本書、可惜google網上少有對這本書的討論
從高中資訊競賽的角度來說，這可能不是一本最有效率的書
(畢竟沒有專章講解DP、圖論這些)
但是從寫程式的角度，不管以後走學術研究、軟體設計，這本書具有很棒的全面性

最難能可貴的是這本書不只是收集題目、提供答案，
更有一種把讀者當成學生、循循善誘、悉心引導的品質
提示我們觀察的角度、如何從樸素做法進階到有效的作法等等

而每題解答後附上的習題，多可分為三類：

A.對題解算法的精髓作檢討：例如原題從正整數改成整數是否成立？圓形能不能推廣到橢圓形？

B.提出原題的特例：例如當所求集合不存在時

C.提出對原題擴展的問題：例如印出所有解、改變部分題設

我想，如果今後期許自己作完一道問題能問出這三種問題、也就看得更高更遠了吧！

--

筆記一些在競賽中出現的名題(多是DP、貪心)
16.連續整數的固定和：NPSC變形(電腦出租公司)
22.整數的所有不同分割數目：PKU上某DP題
34.最大方塊區域：經典DP、IOI2008噁心變形
49.包含在其他區間中間的區間：各種區間時間類貪心的始祖
57.最長共同部分序列：經典DP、今年北市賽出了要求一模一樣的題目

66.找零錢問題、67.背包問題、86.最大連續元素和：經典DP
68.最佳矩陣相乘順序：北市賽出了類似形狀的DP
69.最短路徑問題、77.環遊世界、78.一筆畫：經典圖論
71.穩定伴侶問題：貪心，校內賽考了一樣的
92.最長遞增部分序列：經典DP，USACO Training有一道求LIS總數的變形