發(fā)布時間：2016-05-19 18:02

  本文關(guān)鍵詞：挑戰(zhàn)程序設計競賽，由筆耕文化傳播整理發(fā)布。

《挑戰(zhàn)程序設計競賽(第2版)》

基本信息

作者： (日)秋葉拓哉 巖田陽一 北川宜稔

譯者： 巫澤俊 莊俊元 李津羽

叢書名： 圖靈程序設計叢書

出版社：人民郵電出版社

ISBN：9787115320100

上架時間：2013-6-14

出版日期：2013 年6月

開本：16開

頁碼：1

版次：2-1

所屬分類：計算機 > 軟件與程序設計 > 綜合 > 綜合

更多關(guān)于 》》》《挑戰(zhàn)程序設計競賽(第2版) 》

內(nèi)容簡介

計算機書籍

　　《挑戰(zhàn)程序設計競賽(第2版)》對程序設計競賽中的基礎(chǔ)算法和經(jīng)典問題進行了匯總，，分為準備篇、初級篇、中級篇與高級篇4章。作者結(jié)合自己豐富的參賽經(jīng)驗，對嚴格篩選的110 多道各類試題進行了由淺入深、由易及難的細致講解，并介紹了許多實用技巧。每章后附有習題，供讀者練習，鞏固所學。

　　 《挑戰(zhàn)程序設計競賽(第2版)》適合程序設計人員、程序設計競賽愛好者以及高校計算機專業(yè)師生閱讀。

目錄

《挑戰(zhàn)程序設計競賽(第2版)》

第1章　蓄勢待發(fā)——準備篇　　1

1.1 　何謂程序設計競賽　　2

1.2 　最負盛名的程序設計競賽　　5

1.2.1 　世界規(guī)模的大賽——google code jam（gcj）　　5

1.2.2 　向高排名看齊！——topcoder　　5

1.2.3 　歷史最悠久的競賽—— acm-icpc　　6

1.2.4 　面向中學生的信息學奧林匹克競賽——joi-ioi　　6

1.2.5 　通過網(wǎng)絡自動評測——online judge（oj）　　6

1.3 　本書的使用方法　　7

1.3.1 　本書所涉及的內(nèi)容　　7

1.3.2 　所用的編程語言　　7

1.3.3 　題目描述的處理　　7

1.3.4 　程序結(jié)構(gòu)　　7

1.3.5 　練習題　　8

1.3.6 　讀透本書后更上一層樓的練習方法　　8

1.4 　如何提交解答　　9

1.4.1 　poj的提交方法　　9

1.4.2 　gcj的提交方法　　11

1.5 　以高效的算法為目標　　15

.1.5.1 　什么是復雜度　　15

1.5.2 　關(guān)于運行時間　　15

1.6 　輕松熱身　　16

1.6.1 　先從簡單題開始　　16

1.6.2 　poj的題目ants　　18

1.6.3 　難度增加的抽簽問題　　20

第2章　初出茅廬——初級篇　　25

2.1 　最基礎(chǔ)的“窮竭搜索”　　26

2.1.1 　遞歸函數(shù)　　26

2.1.2 　�！　�27

2.1.3 　隊列　　28

2.1.4 　深度優(yōu)先搜索　　29

2.1.5 　寬度優(yōu)先搜索　　33

2.1.6 　特殊狀態(tài)的枚舉　　37

2.1.7 　剪枝　　38

2.2 　一往直前！貪心法　　39

2.2.1 　硬幣問題　　39

2.2.2 　區(qū)間問題　　40

2.2.3 　字典序最小問題　　43

2.2.4 　其他例題　　45

2.3 　記錄結(jié)果再利用的“動態(tài)規(guī)劃”　　51

2.3.1 　記憶化搜索與動態(tài)規(guī)劃　　51

2.3.2 　進一步探討遞推關(guān)系　　57

2.3.3 　有關(guān)計數(shù)問題的dp　　66

2.4 　加工并存儲數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)　　70

2.4.1 　樹和二叉樹　　70

2.4.2 　優(yōu)先隊列和堆　　71

2.4.3 　二叉搜索樹　　77

2.4.4 　并查集　　84

2.5 　它們其實都是“圖”　　91

2.5.1 　圖是什么　　91

2.5.2 　圖的表示　　94

2.5.3 　圖的搜索　　97

2.5.4 　最短路問題　　99

2.5.5 　最小生成樹　　105

2.5.6 　應用問題　　107

2.6 　數(shù)學問題的解題竅門　　113

2.6.1 　輾轉(zhuǎn)相除法　　113

2.6.2 　有關(guān)素數(shù)的基礎(chǔ)算法　　117

2.6.3 　模運算　　121

2.6.4 　快速冪運算　　122

2.7 　一起來挑戰(zhàn)gcj的題目（1）　　125

2.7.1 　minimum scalar product　　125

2.7.2 　crazy rows　　127

2.7.3 　bribe the prisoners　　129

2.7.4 　millionaire　　132

第3章　出類拔萃——中級篇　　137

3.1 　不光是查找值！“二分搜索”　　138

3.1.1 　從有序數(shù)組中查找某個值　　138

3.1.2 　假定一個解并判斷是否可行　　140

3.1.3 　最大化最小值　　142

3.1.4 　最大化平均值　　143

3.2 　常用技巧精選（一）　　146

3.2.1 　尺取法　　146

3.2.2 　反轉(zhuǎn)（開關(guān)問題）　　150

3.2.3 　彈性碰撞　　158

3.2.4 　折半枚舉（雙向搜索）　　160

3.2.5 　坐標離散化　　164

3.3 　活用各種數(shù)據(jù)結(jié)構(gòu)　　167

3.3.1 　線段樹　　167

3.3.2 　binary indexed tree　　174

3.3.3 　分桶法和平方分割　　183

3.4 　熟練掌握動態(tài)規(guī)劃　　191

3.4.1 　狀態(tài)壓縮dp　　191

3.4.2 　矩陣的冪　　199

3.4.3 　利用數(shù)據(jù)結(jié)構(gòu)高效求解　　206

3.5 　借助水流解決問題的網(wǎng)絡流　　209

3.5.1 　最大流　　209

3.5.2 　最小割　　212

3.5.3 　二分圖匹配　　217

3.5.4 　一般圖匹配　　220

3.5.5 　匹配、邊覆蓋、獨立集和頂點覆蓋　　221

3.5.6 　最小費用流　　222

3.5.7 　應用問題　　228

3.6 　與平面和空間打交道的計算幾何　　250

3.6.1 　計算幾何基礎(chǔ)　　250

3.6.2 　極限情況　　255

3.6.3 　平面掃描　　258

3.6.4 　凸包　　260

3.6.5 　數(shù)值積分　　263

3.7 　一起來挑戰(zhàn)gcj的題目（2）　　267

3.7.1 　numbers　　267

3.7.2 　no cheating　　269

3.7.3 　stock charts　　271

3.7.4 　watering plants　　273

3.7.5 　number sets　　278

3.7.6 　wi-fi towers　　280

第4章　登峰造極——高級篇　　285

4.1 　更加復雜的數(shù)學問題　　286

4.1.1 　矩陣　　286

4.1.2 　模運算的世界　　291

4.1.3 　計數(shù)　　295

4.1.4 　具有對稱性的計數(shù)　　300

4.2 　找出游戲的必勝策略　　305

4.2.1 　游戲與必勝策略　　305

4.2.2 　nim　　311

4.2.3 　grundy數(shù)　　315

4.3 　成為圖論大師之路　　320

4.3.1 　強連通分量分解　　320

4.3.2 　2-sat　　324

4.3.3 　lca　　328

4.4 　常用技巧精選（二）　　335

4.4.1 　棧的運用　　335

4.4.2 　雙端隊列的運用　　337

4.4.3 　倍增法　　345

4.5 　開動腦筋智慧搜索　　350

4.5.1 　剪枝　　350

4.5.2 　a*與ida*　　356

4.6 　劃分、解決、合并：分治法　　359

4.6.1 　數(shù)列上的分治法　　359

4.6.2 　樹上的分治法　　360

4.6.3 　平面上的分治法　　364

4.7 　華麗地處理字符串　　368

4.7.1 　字符串上的動態(tài)規(guī)劃算法　　368

4.7.2 　字符串匹配　　373

4.7.3 　后綴數(shù)組　　378

4.8 　一起來挑戰(zhàn)gcj的題目（3）　　387

4.8.1 　mine layer　　387

4.8.2 　year of more code jam　　392

4.8.3 　football team　　395

4.8.4 　endless knight　　399

4.8.5 　the year of code jam　　403

本書中未涉及的拓展主題　　408

書中例題列表　　411

參考文獻　　413

本圖書信息來源：互動出版網(wǎng)

  本文關(guān)鍵詞：挑戰(zhàn)程序設計競賽，由筆耕文化傳播整理發(fā)布。

本文編號：47232