前言

編程競賽介紹

隨著計算機逐步深入人類生活的各個方面，利用計算機及其程序設計來分析、解決問題的算法在計算機科學領域乃至于整個科學界的作用日益明顯。相應地，各類以算法為主的編程競賽也層出不窮：在國內，有全國青少年信息學奧林匹克聯賽（National Olympiad in Informatics in Provinces，NOIP），該聯賽與全國中學生生物學聯賽、全國中學生物理競賽、全國高中數學聯賽、全國高中學生化學競賽，并稱為國內影響力最大的“五大奧賽”；在國際上，有面向中學生的國際信息學奧林匹克競賽（International Olympiad in Informatics，IOI），面向亞太地區在校中學生的信息學科競賽，即亞洲與太平洋地區信息學奧林匹克（Asia-Pacific Informatics Olympiad，APIO）以及由國際計算機學會（Association for Computing Machinery，ACM）主辦的面向大學生的國際大學生程序設計競賽（International Collegiate Programming Contest， ICPC）等。

各類編程競賽的參賽選手不僅要具有深厚的計算機算法功底、快速并準確編程的能力以及創造性的思維，還要有團隊合作精神和抗壓能力，因此編程競賽在高校、IT公司和其他領域中獲得越來越多的認同與重視。編程競賽的優勝者更是Microsoft、Google、百度、Meta（原Facebook）等全球知名IT公司爭相高薪招募的對象。因此，除了參加各類編程競賽的選手外，很多不參加此類競賽的研究工作者和IT行業的從業人士，也都希望能進行這方面的專業訓練，并從中得到一定的收獲。

為什么要學習算法？

經常有人說：“我不學算法也照樣可以通過編程開發軟件。”那么，為什么我們還要學習算法呢？

首先，算法（algorithm）一詞源于算術（algorism），具體地說，算法是指由已知推求未知的運算過程。后來，人們把它推廣為一般過程，即把完成某一工作的方法和步驟稱為算法。一個程序要完成一個任務，多會涉及算法的實現，算法的優劣直接決定了程序的優劣。因此，算法是程序的“靈魂”。學好了算法，就能夠設計出更加優異的軟件，以非常有效的方式實現復雜的功能。例如，要設計一個具有較強人工智能的人機對弈棋類游戲，程序員沒有深厚的算法功底是很難實現的。 

其次，算法是對事物本質的數學抽象，是初等數學、高等數學、線性代數、計算幾何、離散數學、概率論、數理統計和計算方法等知識的具體運用。真正懂計算機的人（不是“編程匠”）通常都在數學上有相當高的造詣，他們既能用科學家的嚴謹思維來求證，也能用工程師的務實手段來解決問題——這種思維和手段的最佳演繹之一就是“算法”。學習算法，能鍛煉我們的思維，使思維變得更清晰、更有邏輯，更有深度和廣度。學習算法更是培養邏輯推理能力的非常好的方法之一。因此，學習算法，其意義不僅在于算法本身，更重要的是，對我們日后的學習、生活和思維方式也會產生深遠的影響。 

最后，學習算法很有意思、很有趣味。所謂“技術做到極致就是藝術”，當一個人真正沉浸到算法研究中時，他既會感受到精妙絕倫的算法的藝術之美，也會為它“巧奪天工”的構思而深深震撼，并從中體會到一種不可言喻的美感和愉悅。雖然算法的那份“優雅”與“精巧”很吸引人，但也令很多人望而生畏。事實證明，對很多人來說，學習算法的確是一件非常有難度的事情。

本書的特色及用法

為了提高讀者的學習效率，本書直接以各類競賽真題入手，以精練而準確的語言，全面細致地介紹了編程競賽中經常用到的各類基礎算法；為了幫助讀者更深刻地理解和掌握算法的思想內涵，本書還通過精挑細選，由淺入深地安排了相關習題。考慮到讀者的接受水平，一般引入新知識點的題目時，書中會提供該題目的完整參考代碼以供讀者參考，但隨著讀者對知識點的理解逐步加深，后續的同類型題目將逐步向僅提供算法思路、提供偽代碼或無任何提示的方式轉變。此外，對于一些思維跨度較大的題目，本書會酌情給予讀者一定的提示。

本書每章分為普及組和提高組兩部分。通常，普及組所涉及的內容對應NOIP普及組難度，提高組所涉及的內容對應NOIP提高組難度。一個合理的學習安排是將本書的內容分為兩個階段學習，即第一個階段學習各章的普及組內容，初步掌握每種算法的思想和用法，第二個階段學習各章的提高組內容，作為之前學習的算法內容的復習和提高。

配套資源

為了幫助讀者通過本書更好地掌握算法知識，本書提供了豐富的配套資源，包括源碼、題目講解視頻、PPT。讀者可通過以下方式獲取配套資源。

● 源碼和PPT的下載地址為https://box.ptpress.com.cn/y/59659

● 題目講解視頻可在線觀看。

方法一：在異步社區網站搜索本書書名，進入本書頁面，單擊【在線課程】，可在線觀看講解視頻。

方式二：“內容市場”微信小程序或App中搜索本書書名，即可在線觀看視頻。

適合閱讀本書的讀者

本書可作為NOIP復賽的教材和ICPC的參考與學習用書，也可作為計算機專業學生、IT工程師、科研人員、算法愛好者的參考和學習用書。

本書既可以作為學習完《編程競賽寶典：C++語言和算法入門》的讀者繼續學習的教材，也可以作為有一定編程基礎的讀者學習算法的獨立用書。

致謝

感謝全國各省市中學、大學的信息學奧賽指導老師，他們給本書提了許多真誠而有益的建議，并對編者在寫書過程中遇到的一些困惑和問題給予了熱心的解答。

在本書編寫過程中，編者使用了NOIP的部分原題、在線評測網站的部分題目，并參考和收集了其他創作者發表在互聯網、雜志等媒體上的相關資料，無法一一列舉，在此一并表示衷心感謝。

感謝卷積文化傳媒（北京）有限公司CEO高博先生和他的同事。

最后要說的話

由于編者水平所限，書中難免存在不妥之處，歡迎各位同人或讀者賜正。讀者如果在閱讀中發現任何問題，請發送電子郵件到hiapollo@sohu.com。也希望讀者對本書提出建設性意見，以便修訂再版時改進。

本書對應的題庫網址為www.magicoj.com，題庫正在不斷完善中。

希望本書的出版，能夠給學有余力的中學生、計算機專業的大學生、程序算法愛好者以及IT從業者提供學習算法有價值的參考。

廣州市第六中學強基計劃基地教材編委會

2023年1月