ACM國際大學生程式設計競賽：題目與解讀

《ACM國際大學生程式設計競賽：題目與解讀》是2012年12月1日出版的一本圖書，作者是俞勇。

基本介紹

• 書名：ACM國際大學生程式設計競賽：題目與解讀
• 作者：俞勇
• ISBN：9787302294924
• 出版時間：2012.12.01

書籍信息

作者：俞勇 主編
定價：69元
印次：1-3
ISBN：9787302294924
出版日期：2012.12.01
印刷日期：2015.07.30

內容簡介

ACM國際大學生程式設計競賽（ACM-ICPC）是國際上公認的水平最高、規模最大、影響最深的計算機專業競賽，目前全球參與人數達20多萬。本書作者將16年的教練經驗與積累撰寫成本系列叢書，全面、深入而系統地將ACM-ICPC展現給讀者。本系列叢書包括《ACM國際大學生程式設計競賽：知識與入門》、《ACM國際大學生程式設計競賽：算法與實現》、《ACM國際大學生程式設計競賽：題目與解讀》、《ACM國際大學生程式設計競賽：比賽與思考》等4冊，其中《ACM國際大學生程式設計競賽：知識與入門》介紹了ACM-ICPC的知識及其分類、進階與角色、線上評測系統；《ACM國際大學生程式設計競賽：算法與實現》介紹了ACM-ICPC算法分類、實現及索引

目錄

第一部分 例 題 精 講

第1章 數學 3

1.1 機率 3

Coupons 3

Generator 3

1.2 代數 4

1.2.1 Polya 4

Arif in Dhaka (First Love

Part 2) 4

1.2.2 矩陣 5

Tower 5

XX Language 6

1.2.3 線性方程組 7

Ars Longa 7

1.2.4 線性規劃 8

Expensive Drink 8

1.3 組合 9

1.3.1 基本排列組合 9

The Unreal Tournament 9

1.3.2 容斥原理 10

Jackpot 10

The Almost Lucky Numbers 11

1.3.3 生成函式 12

Vasya’s Dad 12

1.3.4 生成樹計數 13

Organising the Organisation 13

1.3.5 綜合 14

Hero of Our Time 14

Permutation 15

1.4 博弈 17

Battle for the Ring 17

Fool’s Game 17

Points Game 18

1.5 數論 20

1.5.1 模線性方程 20

Integer Sequences 20

1.5.2 歐幾里得 20

Wizards 20

1.5.3 歐拉定理 21

Strange Limit 21

1.5.4 歐拉函式 22

GCD Determinant 22

1.5.5 平方剩餘 23

Square Root 23

1.5.6 原根 24

Fermat’s Last Theorem 24

1.5.7 整除與剩餘 26

Brute-Force Algorithm 26

Integral Roots 26

Vivian’s Problem 27

1.5.8 中國剩餘定理 28

Voyager 1 28

1.6 分析 29

Bridge 29

第2章 數據結構 31

2.1 優先佇列 31

The Lazy Programmer 31

2.2 線性表 32

Book Pile 32

2.3 散列表 32

Language Recognition 32

2.4 並查集 33

Feel Good 33

Parity 34

2.5 排序 35

Inversions 35

All for Love 35

2.6 ST表 37

Lubenica 37

2.7 樹狀數組 38

Elections 38

Stars 39

2.8 線段樹 40

Dynamic Rankings 40

Wild West 41

2.9 可並堆 41

Monkey King 41

2.10 平衡樹 42

Treediff 42

維護數列 43

2.11 動態樹 44

OTOCI 44

第3章 圖論 46

3.1 路徑 46

3.1.1 連通性 46

Network Attack 46

Synchrograph 47

3.1.2 歐拉路 48

Strange Graph 48

3.1.3 基本最短路 49

Animal Run 49

New Islands 50

Recover Path 51

Suffix-Replacement

Grammars 52

3.1.4 有負權的最短路 53

Layout 53

Sightseeing Cows 53

Word Rings 54

3.2 匹配 55

3.2.1 二分圖匹配 55

Double NP-hard 55

Emergency Pizza Order 56

Number Graph 56

Rooks 58

3.2.2 二分圖最優匹配 59

Railway Communication 59

The Great Wall Game 60

Warehouse 61

3.2.3 穩定婚姻 61

Ladies’ Choice 61

3.3 樹 62

3.3.1 最小生成樹 62

Confidential 62

Island Explorer 63

3.3.2 最優比率生成樹 64

Portkey Network 64

3.4 網路流 65

3.4.1 最大流（最小割） 65

Bomb, Divide and Conquer 65

Buy one, get the rest free 66

Destroying The Graph 67

Dual Core CPU 68

Network Wars 68

Rectangle of Permutation 69

The Glorious Karlutka River 71

3.4.2 有上下界的網路流 72

Flow construction 72

Reactor Cooling 72

3.4.3 費用流 73

Highway Patrol 73

Insurrection 74

Paint the Roads 75

Shortest pair of paths 76

第4章 計算幾何 77

4.1 多邊形 77

Areas 77

Cave Crisis 78

Chocolate 79

Ancient vending machine 80

Fool’s Day 81

4.2 圓 82

Sweet Dream 82

Malfatti Circles 83

Get Out! 84

Biscuits 85

4.3 凸包 85

Mixed Juice 85

Fuel 86

4.4 半平面交 87

Fairies’ Defense 87

Largest Circle 88

4.5 離散化 89

Phone cell 89

Shy Polygons 90

降雨量 91

月下檸檬樹 92

4.6 立體幾何 94

3D Triangles 94

Lowest Pyramid 94

The Return of Carl 96

第5章 求解策略 97

5.1 搜尋 97

Holedox Moving 97

Insecure in Prague 98

Mines For Diamonds 99

Power Calculus 101

智破連環陣 102

5.2 貪心 103

Beijing Guards 103

Body Check 104

Cow Acrobats 104

Keep the Customer

Satisfied 105

5.3 遞推 106

Dispute 106

Dropping water balloons 107

Questions 108

管道取珠 109

5.4 分治 110

Friendly Points 110

Mokia 111

Tree 112

5.5 動態規劃 113

5.5.1 經典問題 113

Boxes of Chocolates

Again 113

Greatest Common Increasing

Subsequence 114

Inheritance 114

Long Live the Queen 115

Prince and Princess 116

5.5.2 樸素動態規劃 116

Clock 116

Damn Couples 117

Decrypt the Dragon

Scroll 118

Dice contest 120

Drive through MegaCity 120

Facer’s Chocolate Dream 122

Incredible! 123

Lights 124

Network Connection 124

Painting the balls 125

Persephone 126

Post offices 127

Salary for Robots 128

Salesman 130

Shoveling Snow 131

Strange Dream 132

The Best Name for Your

Baby 133

The Bookcase 134

Think Positive 134

Wildcards 136

Yet Another Answer 137

二叉查找樹 137

5.5.3 樹形 138

Apple Transportation 138

Chandelier 140

Counting heaps 141

Succession 142

Tribe Council 143

Vaccination Centers 144

網路收費 145

5.5.4 按位動態規劃 146

Almost Lucky Numbers 146

Amount Of Degrees 147

Hotel in Ves Lagos 147

Password Remembering 148

5.5.5 狀態壓縮 149

Controlled Tournament 149

Easter Eggs 149

Fun Game 150

Integer Transmission 151

5.5.6 連通性 152

Connect 152

Channel 153

Manhattan Wiring 155

Paint Me Less 156

Pipes 157

Tour in the Castle 159

5.5.7 最佳化 160

Euro 160

Fibonacci Subsequence 163

Nice Prefixes 164

Quadratic Functions 166

Two Sawmills 167

Frogs 169

詩人小G 171

5.6 模擬 172

Archery 172

Exiting Time 173

Flip and Turn 175

Water Tanks 175

5.7 構造 177

Airline Company 177

Funny Language 178

Payment System 178

Square country 3 179

Train Car Sorting 180

5.8 二分 180

Array Transformations 180

Doors 182

Food Competition 183

5.9 三分 184

Fire Station Building 184

5.10 離散化 184

Crop circles 184

5.11 遺傳算法 186

Sherlock Holmes 186

第6章 論題選編 188

6.1 字元串 188

6.1.1 KMP 188

Cow Patterns 188

6.1.2 Trie樹 189

Billing Table 189

6.1.3 後綴數組 189

Stammering Aliens 189

Common Substrings 190

Connecting the

Segments 191

6.1.4 自動機 192

Censored! 192

6.1.5 Rabin-Karp 193

Square Palindrome 193

6.2 最近公共祖先 195

The Merchant 195

Transportation Network 196

Design the city 196

6.3 2-SAT 197

Game with cards 197

Cipher 198

6.4 快速傅立葉變換 199

K-neighbor substrings 199

第二部分 題 庫