 |
-- 會員 / 註冊 --
|
 |
|
|
|
算法競賽入門經典——習題與解答 ( 簡體 字) |
| 作者：陳鋒 | 類別：1. -> 程式設計 -> 演算法 |
| 譯者： |
| 出版社：清華大學出版社 |  3dWoo書號： 48323
詢問書籍請說出此書號！【缺書】
NT售價： 350 元 |
| 出版日：1/1/2018 |
| 頁數：429 |
| 光碟數：0 |
|
站長推薦：   |
| 印刷：黑白印刷 | 語系： ( 簡體 版 ) |
| |
加入購物車  │加到我的最愛
(請先登入會員) |
| ISBN：9787302476580 |
| 作者序 | 譯者序 | 前言 | 內容簡介 | 目錄 | 序 |
| (簡體書上所述之下載連結耗時費功, 恕不適用在台灣, 若讀者需要請自行嘗試, 恕不保證) |
| 作者序： |
| 譯者序： |
前言： 前 言
“請問《算法競賽入門經典（第2版）》有沒有配套題解啊？很多練習題好難，真希望能有一本簡單、易懂的參考解答！”經常有讀者追問類似的問題。筆者在進行訓練學習時，也經常會有這樣的想法。雖然很多題目可以在網上搜到對應題解，但這些題解多數是解題者為方便自己做題而隨手記錄的，解答過程未必嚴密、系統，語言表達上也比較隨意，初學者理解起來就有一定的難度。
多年之前，筆者曾有幸參與了《算法競賽入門經典—訓練指南》一書的編寫工作，收獲頗大。也正是那次，我深刻感受到了自己在算法領域的不足，以及思維能力的亟待提升。私下里，我曾和劉汝佳老師商量，就以《算法競賽入門經典（第2版）》的習題為訓練題目，強迫自己在解出每道題之后，再對自己的思路進行嚴密、仔細的剖析，通過大量的訓練，使自己得到一次系統的訓練和提升。這次訓練，使我記了厚厚一大本的筆記，而這本筆記就是本書的緣起。
希望本書能幫助更多跟我一樣迫切需要提升算法思維能力的初學者！
算法有什么用
我大學學的是機械專業，但由于對數學非常熱愛，加之畢業后發現軟件行業貌似比較好“混”，且工資待遇比其他行業高些，所以就進入了開發領域。經過一段時間的工作后，我發現自己經常會遇到以下一些問題：
? 程序稍微復雜一些，代碼就會寫的很亂。
? 程序出了問題，不知道該如何調試，只會到處修改，然后再看效果。
? 用戶需求稍作改變，就想罵街。
? 特別重要的一點是，如果你想跳到外企去工作，面試時肯定會讓你編一些很難的算法程序。
后來，我進入到了微軟上海全球技術支持中心做外包技術支持，接觸到了許多嚴謹、求是、好學的工程師前輩。從他們身上，我學到了一些非常有效的解決問題的思路，以及那種“活到老學到老”的人生態度。
我逐漸明白：程序是要設計的。為了設計得清晰，需要學習數據結構、操作系統原理等非常多的基礎知識，而這些體系本質上是前輩人思維方法的結晶。
另外，令很多程序員頭疼的調試過程，給我印象最深的是一句話：調試的本質實際上就是在定位。大多數時候，調試的過程（并發程序的調試可能就更復雜些）其實就是一個二分查找：假如有 100行程序結果不對，就可以在第50行看看結果是否符合預期，如果OK，說明問題出在后50行，否則前50行一定有問題。如此遞歸下去，很快就能精準定位到有問題的代碼。了解二分查找的朋友都知道，這個算法復雜度是O(logn)。
用C#開發服務端程序時，我經常會遇到內存問題，需要對垃圾收集（GC）的過程進行分析調試。深入學習之后我發現，其實GC模型的本質就是有向圖。抱著這個思路再來分析解決內存問題，思路瞬間清晰了很多。
這樣的例子還有很多。
在不斷解決各類問題的過程中，我逐漸明白了—算法在本質上是諸多計算機學術以及實踐領域積累下來的分析解決各種問題的思維方法。它不是象牙塔內的純學術研究，更不是一堆僅能用來解決特定領域性能問題的高精尖技術。這個行業的技術人員，本質上正是以這些思維方法為武器，高效解決著不同行業領域不斷涌現出的各類紛繁問題和挑戰。
說到這里，我想到其他很多行業：京劇藝人每天早上要練嗓子，相聲演員每天要練貫口，軍人在戰斗之余要進行大量訓練，中醫在繁忙之余要天天鉆研《傷寒論》《黃帝內經》等經典……類似這樣，需要認真對待并把基本功訓練作為生活一部分的行業還有很多。對于筆者來說，算法思維就是IT相關行業的技術人員需要用同樣態度持續不斷進行訓練的一項基本功。
所以，就有了這些年的學習過程，以及以本書作為省察的一個小小總結。
內容安排
本書內容分為以下5章。
第1章是各種編程訓練技巧以及C++11語法特性的簡單介紹。
第2章精選了一部分《算法競賽入門經典（第2版）》的習題進行分析、解答，主要是讀者反映較多的第3~11章的課后習題部分。
第3章是ACM/ICPC比賽真題分類選解，挑選了近些年ACM/ICPC比賽中較有價值的題目進行分析并解答。
第4章是比賽真題選譯，整理并翻譯了近幾年來各大區域比賽中筆者認為值得學習訓練的比賽真題。
第5章是比賽難題選譯，內容類似于第4章，只是題目難度更上一個臺階。
關于C++語言的使用
本書在解答各類算法題目時，使用C++作為主要的編程語言，盡量使用STL中提供的現成數據結構，同時也盡量使用C++11的新特性。因為筆者認為，算法訓練最關鍵的是訓練解決問題的思維能力，包括抽象能力、分析能力、調試能力等，應該充分利用語言提供的語法特性使得程序更加簡潔清晰，從而使解題者更專注于問題的抽象和分析本身。
關于題目代碼
本書中的所有題目，筆者都是先完成代碼并在線提交AC（Accepted），然后才開始編寫對應的分析題解。有些需要附上代碼的題目，筆者會盡可能把代碼的主要部分（去掉模板代碼以及C++的namespace導入部分）附在題目后面，但由于篇幅原因，實在無法全部放入書中。還有些題目，雖然已經在線提交AC，但由于無法嚴格證明題目的正確性，也沒有在書中提供題解。
書中的所有代碼，讀者朋友們如有需要，可以通過如下網站進行下載：https://github.com/sukhoeing/aoapc-bac2nd-keys。
勘誤和支持
雖然筆者已竭盡全力，力求減少紕漏，但由于水平有限，書中難免仍存在錯漏之處，懇請廣大讀者朋友們批評指正。歡迎您將學習過程中遇到的各類問題、您對本書的想法以及寶貴意見，通過本書網站的issues部分一起交流。
致謝
首先要感謝劉汝佳老師，是他把我帶進了算法藝術的大門，并且在工作極其繁忙的情況下一直耐心地指導著我的算法學習。
從小父親就告訴我，對的事情一定要堅持。這句話支撐著我渡過了很多艱難的日子。同時，也要感謝我的太太梁明珠和女兒陳婉之。這三年來，我犧牲了大量本該陪伴他們的時間，投入到了本書的創作中。沒有你們的支持和包容，我不可能完成這本書。
還要感謝微軟工作期間經常指導我的老師張羿，從他那里，我第一次知道了世界上還有ACM/ICPC這回事。在如何做好一個程序員這件事上，他給了我非常多有價值的指導和幫助。
本書初稿完成之后，許多同學和朋友踴躍參與到了本書的試讀中，并且提出了許多有價值的意見和反饋，他們的名字（排名不分先后）是陳飛、崔晨、楊恒杰、林永康、陳坤澤、孫博昊等。另外，書中的部分題目也參考了許多網友的在線題解，在此一并表示感謝。
最后要感謝清華大學出版社的賈小紅編輯，用極大的耐心容忍著我把交稿時間一拖再拖，希望本書不會讓您失望。
陳鋒
|
內容簡介：《算法競賽入門經典——習題與解答》是在《算法競賽入門經典（第2 版）》的基礎上，延伸出來的一本習題與解答圖書，它把C++語言、算法和解題有機地結合在一起，淡化理論，注重學習方法和實踐技巧，是一本算法競賽的入門和提高教材。
《算法競賽入門經典——習題與解答》分為5 章。第1 章是各種編程訓練技巧以及C++11 語法特性的簡單介紹。第2 章精選了一部分《算法競賽入門經典（第2 版）》的習題進行分析、解答。第3 章是ACM/ICPC 比賽真題分類選解，挑選了近些年ACM/ICPC 比賽中較有價值的題目進行分析并解答。第4∼5 章是比賽真題選譯，整理并翻譯了近幾年來各大區域比賽中筆者認為值得學習訓練的比賽真題。
如果你對算法感興趣，如果你是一名程序員或即將成為一名程序員，如果你想大幅提升自己的算法思維能力，如果你有志于參加ACM/ICPC、NOIP、NOI 等競賽，那就來吧！《算法競賽入門經典——習題與解答》將為你推開一扇算法世界的大門！
法競賽入門經典（第2 版）》的習題進行分析、解答。第3 章是ACM/ICPC 比賽真題分類選解，挑選了近
些年ACM/ICPC 比賽中較有價值的題目進行分析并解答。第4∼5 章是比賽真題選譯，整理并翻譯了近幾
年來各大區域比賽中筆者認為值得學習訓練的比賽真題。
如果你對算法感興趣，如果你是一名程序員或即將成為一名程序員，如果你想大幅提升自己的算法思維能
力，如果你有志于參加ACM/ICPC、NOIP、NOI 等競賽，那就來吧！本書將為你推開一扇算法世界的大門！ |
目錄：第1章編程技巧與C++11語法特性介紹1
1.1編程技巧1
1.1.1排序性能問題1
1.1.2整數輸入3
1.1.3循環宏定義3
1.1.4STL容器內容調試輸出3
1.1.5二維幾何運算類4
1.1.6內存池5
1.1.7泛型參數的使用5
1.1.8位運算操作封裝6
1.1.9編譯腳本7
1.2C++11語言特性介紹7
1.2.1類型推導（auto）8
1.2.2空指針值（nullptr）8
1.2.3容器的for循環遍歷8
1.2.4匿名函數（Lambda）9
1.2.5統一的初始化語法10
1.2.6哈希容器11
第2章《算法競賽入門經典（第2版）》習題選解13
2.1數組和字符串13
2.2函數和遞歸26
2.3C++與STL入門37
2.4數據結構基礎76
2.5暴力求解法108
2.6高效算法設計139
2.7動態規劃初步166
2.8數學概念與方法190
2.9圖論模型與算法214
2.10高級專題237
第3章比賽真題分類選解248
3.1搜索248
3.2模擬257
3.3動態規劃319
3.4組合遞推324
3.5圖論331
3.6正則表達式333
第4章比賽真題選譯341
ACM/ICPCNorthAmerica-GreaterNY341
ACM/ICPCAfrica/MiddleEast-Arab342
ACM/ICPCNorthAmerica-Mid-AtlanticUSA344
ACM/ICPCNorthAmerica-RockyMountain345
ACM/ICPCNorthAmerica-EastCentralNA347
ACM/ICPCNorthAmerica-Mid-CentralUSA363
ACM/ICPCLatinAmerica364
ACM/ICPCSWERC（SouthwesternEuropeRegionals）367
ACM/ICPCEurope-Central372
ACM/ICPCEurope-Northwestern372
ACM/ICPCSouthPacific373
ACM/ICPCAsia–Tokyo（東京賽區）373
ACM/ICPCAsia–Aizu（愛知賽區）375
ACM/ICPCAsia–Fukuoka（福岡賽區）.375
ACM/ICPCAsia–Tehran（德黑蘭）376
ACM/ICPCAsia–Daejeon（韓國大田）378
ACM/ICPCAsia–Harbin（哈爾濱賽區）381
ACM/ICPCAsia–Changchun（長春賽區）381
ACM/ICPCAsia–Shenyang（沈陽賽區）382
ACM/ICPCAsia–Dalian（大連賽區）最后的謎題（TheLastPuzzle,Asia-Dalian2011,LA5695）386
ACM/ICPCAsia–Tianjin（天津賽區）388
ACM/ICPCAsia–Changsha（長沙賽區）389
ACM/ICPCAsia–Nanjing（南京賽區）389
ACM/ICPCAsia–Guangzhou（廣州賽區）391
ACM/ICPCAsia–Shanghai（上海賽區）392
ACM/ICPCAsia–Chengdu（成都賽區）393
ACM/ICPCAsia–Hangzhou（杭州賽區）396
ACM/ICPCAsia–Jinhua（金華賽區）396
ACM/ICPCAsia–Taichung（臺中賽區）398
ACM/ICPCAsia–Kaohsiung（高雄賽區）398
ACM/ICPCAsia–Amritapuri（印度Amritapuri）400
ACM/ICPCAsia–Hatyai（泰國合艾）405
ACM/ICPCAsia–Bangkok（泰國曼谷）407
ACM/ICPCAsia–Phuket（普吉島賽區）409
ACM/ICPCWorldFinals410
CCPC（中國大學生程序設計競賽）412
第5章比賽難題選譯415
ACM/ICPCEurope–Central415
ACM/ICPCEurope–Northeastern416
ACM/ICPCAsia–Taichung（臺中）420
ACM/ICPCAsia–Daejeon422
ACM/ICPCAsia–Shanghai（上海）422
ACM/ICPCAsia–Dhaka（達卡）423
ACM/ICPCAsia–Mudanjiang（牡丹江）424
ACM/ICPCAsia–Tehran（德黑蘭）427
ACM/ICPCAsia–Xian（西安）427
ACM/ICPCAsia–Anshan427
ACM/ICPCAsia–Beijing（北京）429
ACM/ICPCAsia–Guangzhou（廣州）431
ACM/ICPCAsia–Tokyo（東京）432
ACM/ICPCAsia–Bangkok（曼谷）433
|
| 序： |
|
