ACM国际大学生程序设计竞赛 题目与解读PDF电子书下载

第一部分 例题精讲 3

第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

Confiidential 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 Satisfiied 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

第二部分 题库 203

4 Values Whose Sum is 0 203

8G Island 203

A Binary Apple Tree 204

A Dinner with Schwarzenegger!!! 204

A Foldy but a Goody 205

A Game with Colored Balls 206

A Line Painting 207

A Secret Book 207

A Simple Pendulum 208

Abelian Groups 209

Aerodynamic 209

Again Palindrome 210

Against Mammoths 210

Air Conditioning Machinery 211

All Your Bases Belong to Us 212

Alphabet 213

Alternating Sum of Digits 214

Always an Integer 215

Amphiphilic Carbon Molecules 216

Anansi’s Cobweb 216

Ancient decoration 217

Angry Teacher 218

Anniversary Party 218

Another Chocolate Maniac 219

Another Minimum Spanning Tree 220

Ants II 221

Ants 221

Apple or Doughnut 222

Archipelago 222

Area 51 223

Arrays 224

Art of War 225

Asteroids 226

Astronomy 226

Autocompletion 227

Automaton 228

B-Station 229

Balance 229

Barisal Stadium 233

Battle 234

Battle of the Triangle 234

Battle 235

Be a Smart Raftsman 236

Be Wary of Roses 237

Beloved Sons 238

Best Cow Line， Gold 238

Bigger is Better 239

Binary Lexicographic Sequence 239

Bingo 240

Bishops 241

Bit Compressor 242

Bitmap 242

Black & White 243

Black Box 243

Black Vienna 244

Black-white king 245

Blind Walk 246

Bone Sort 247

Boring Sequence Operations 248

Boring.Hot.Summer 249

Breadtree 249

Bridges 250

Broken Chessboard 251

Bubble Sort 251

Business Center 252

Buttons 253

Buy or Build 254

Cactus 254

Cake Share 255

Camera in the Museum 255

Card Game 256

Casino 257

Castles 259

Cave Exploration 260

Centers Of Symmetry 261

Central Heating 261

Centroid 262

Challenge of Bravery 262

Challenge of Wisdom 263

Chameleons All Around 263

Changing Digits 265

Chapayev 265

Chemist’s Math 266

Chessmaster 267

ChiBi 268

Chinese Hockey 268

Choose The Best 269

Choreographer Problem 269

Circle Drawing 270

Circular Railway 271

Clever’s Problem 272

Cliquers strike back 272

Cocktail 273

Collecting Bugs 274

Collecting Luggage 275

Collector’s Problem 276

Color a Tree 276

Colorful Decoration 277

Combinations 278

Compositions 278

Compressed String 279

Concatenation of 280

Languages 280

Conduit Packing 281

Confectionery 281

Connect It， If You Can！ 282

Connecting People 283

Connections in Galaxy War 284

Consecutive Ones 284

Constructive Plan 285

Cookie Choice Ⅱ 286

Cookie Choice 286

Cover an Arc 287

Coverage 287

Crack 288

Cracking RSA 289

Crazy Professor 289

Crazy Thairs 290

Cross Counting 291

Cross Stitch 292

Crossing Streets 293

Crossing 294

Cryptography 294

Cube Root 295

Cubes 296

Cyclic Polygons 297

Dangerous Pattern 297

Darkterror’s Combos 298

｛Sum+=i++｝ to Reach N 299

Darts 299

Deciphering 300

Dendrograms 301

DFA 302

Dice Compare 302

Difference Is Beautiful 303

Different Digits 304

Dig or Climb 304

Digit Counting 306

Digit Puzzle 307

Dinner’s Ready 308

Dirt 308

Discrete Roots 309

Distinct Substrings 310

Divide and conquer 311

Divisibility by 15 311

Divisibility Testing！ Wow！ 312

Document Indexing 313

Dog Distance 314

Domestic Networks 314

Domino Sorting 315

Door painting 315

Double Cyclic 316

Double Patience 317

Driving Directions 317

Droid Formation 319

Dueue’s Quiz 320

Dungeon 321

Duopoly 321

dwarfs 322

Edison 323

Editor Nottobad 324

Electrician 325

Elementary symmetric functions 325

Elevator 326

Ellipse 327

Equal Squares 327

Equation 329

Escape From Enemy Territory 329

Evacuation Plan 330

Exclusive Access 2. 330

Expectation 331

Expedition 331

Exploring Pyramids 332

Expression Evaluation 333

Eyeball Benders 334

Fall the Brick 334

Farey Sequence 335

Fast Typing 337

Fence 338

Feng Shui 338

Ferry Lanes 339

Fibonacci System 339

File System Travel 340

Find a Multiple 341

Find the Border 341

Find the Latitude 342

Find the Number 343

Finding Treasure 344

Fixing the Great wall 345

Flight Safety 345

Fliptile 347

Flying Right 348

Fold Paper Strips 349

Foot Notes 350

Formula 350

From G to H and back 351

Full Steiner Topologies 352

Fund Management 353

Funny Feature 354

Funny Strings 354

Gaby Ivanushka 355

Game for Little Johnny 357

Game 358

Garbling Game 358

Garlands 359

Gena’s Soul Cake 360

Geometrical Dreams 361

Geometry Problem 362

Given a string 362

Go Downstairs 362

Gold Balanced Lineup 363

Gold Bars 364

Google Book 364

Gourmet Grazers 365

Great Berland Wall 366

Greatest Greatest Common Divisor 367

Greedy Path 367

Guards 367

Gunman 369

Hanoi Tower 369

Hard Life 371

Harder Sokoban Problem 371

Hardwood Cutting 372

Harmony Forever 373

Haybale Guessing 373

H eapsort 374

Heavy Disc 375

Height， Bisector and Median 376

Hell on the Markets 376

Help Bubu 377

Help Little Laura 378

Here’s a Product Which Will Make You Tensor 378

Heroes 379

Hexagon Coin Toss 380

Hexagonal Parcels 382

Hills 382

Holey Square Tiling 383

Horn Clauses 385

Hour Glass 386

How Many bases？ 387

How many ones needed 387

Huffman Codes 388

Hyperrook 389

I-country 389

Ice-cream Tycoon 390

Ideal Frame 391

Illuminated Planet 392

Illumination of Buildings 392

Ilya Murometz 393

Immaterial and Missing Power 393

Impudent Thief 394

In the army now 395

Increasing Subsequences 395

Infected Land 396

Infiinite Fraction 397

Inheritance 397

Inner Vertices 398

Inspection 399

Intelligent Cats 399

Interconnect 400

Interesting Yang Hui Triangle 401

Irrelevant Element 402

Islands and Bridges 402

It’s Never Too Late 403

Jacks Socks 404

Jacquard Circuits 404

Jam’s Store 405

Japanese Puzzle 405

Java Certification 406

Jenny’s First Exam 407

Joke with Turtles 407

Journey 408

Journey with Pigs 409

Jumping Joe 409

K Best 410

K-based Numbers. Version 3 411

K-th Number 411

Kadj Squares 412

Kaka’s Matrix Travels 412

Key Insertion 413

Key Substrings 414

Key Task 415

Keyword 416

Khepel’s Problem 416

Kindergarten Graduation 417

King Berl Ⅵ 417

Kingdom Partitioning 418

Kingdom Map 419

Knapsack Ⅱ 420

Knights of the Round Table 420

Knowledge for the masses 421

Landscaping 422

Lap time in a racing circuit 423

Largest Rectangle in a Histogram 424

Laser Ball 424

Lattice Animals 425

Lattice Squares 426

Lazy Cows 426

Lazy Susan 427

Leonardo’s Notebook 428

Let’s play a game 429

Liar or Not Liar that is the 429

Lifting the stone 430

Light 430

Lights 431

Line Chart 432

Lineland’s Airport 433

Link 434

Little Jumper 435

Longest Repeated 435

Substring 435

Lottery 436

Love for Pizza 437

Lucky cities 437

Lucky numbers 438

Lucky Tickets 438

Machine Schedule 439

Magic Car 440

Magic Pairs 440

Magic Rings 441

Magic Seven 442

Mahjong 443

Map Generator 444

Marble Game 445

March of the Penguins 446

Martian Mining 446

Mathematics Ⅱ 447

Mathematics 448

Matrix Processing 448

Matrix 449

Maximal Clique 450

Maximum Ⅱ 451

Maximum 452

Mechanics 453

Median 454

Meetings 454

Mega Man’s Missions 455

Military Game 455

Ministry 457

Mobile Positioning 458

Mobile Tower 459

Moles and Holes 460

More Sweets！ 460

Mountain Road 461

Mouse 462

Movie Promotion 463

Moving to Nuremberg 464

National Park 464

Net Loss 465

Network Mess 465

Network 467

Never End 468

New Go Game 469

Nikifor’s walk 469

Nikifor-3 470

No Smoking 471

Nuclear Plants 472

Number Game 473

Number Permutations 474

Obfuscation 475

Objective Berlin 476

Obscene words filter 476

Observers Coloring 477

Optimal Dartboard 478

Optimal Strategy for the ICPC 478

Order 479

Orthogonal Circles 479

Pairs 480

Palindrom 481

Palindromic Subsequence 481

Party of 8g 482

Pascal vs C++ 483

Pass Licenses 484

Password Suspects 484

Perspective 485

Petya the Hero 486

Pinocchio 486

Piotr’s Ants 487

PLAHTE 488

Playing with Matches 488

Plot Purchase 489

Police and Thief 490

Polygon 490

Postal Charges 491

Prefiixes and Suffixes 492

Present for MM 492

Prester John 493

Problem Stacks 494

Protecting Zonk 494

Prototype 496

pyramid 497

Quad Tiling 498

Quadratic Equation 498

Rabbit Hunt 499

Racing Route 499

Railway Tickets 500

Random Walk 501

Rebus 502

Rectangular Polygons 503

Regions 504

Repair Depots 504

Requirements 505

Resistance 506

Right Words 506

Rings’n’Ropes 507

Roads 508

Robot 508

Rooks 509

Room Assignments 509

Rotating a Frame 510

Rotation Estimation 511

Routing II 512

Routing 513

Ruler 514

Sails 515

Search for a Hiding-Place 516

Searching the String 517

Security by Ambiguity 518

Separate Points 519

Sequence Median 520

Sequence 520

Sequence Sum 521

Shadow Area 522

Sharif Super Computer 523

Shoot the Bullet 523

Shoot your gun！ 524

Sightseeing 525

Signals and Systems 525

Simple Game on a Grid 526

Simple Sequence 526

Slalom 527

Snake 528

Special Subsequence 529

Square Country 2 530

Square 530

Stone Grid 531

Strange Game 532

Strange People 533

Street Lamp 534

Student’s Morning 534

Subnumber 535

Suffiix reconstruction 536

Super Snake 537

Super squares 537

Super Memo 538

Sweet 539

Switchback 540

Taxi 541

Team Building 541

Team Forming 542

Team Tryouts 542

That Nice Euler Circuit 544

The Archaeologist’s Trouble Ⅱ 544

The art to the broad masses！ 545

The book 546

The Deadly Olympic Returns 546

The Different Task 547

The Gossiping System 548

The Great Escape 548

The Greatest Angle 549

The Laurel Hardy Story 550

The longest constant gene 551

The Lucky Numbers 551

The Mastermind Master’s Mind 552

The Merchant Guild 553

The Monochrome Picture 554

The Most Frequent Number 554

The Party of Ural Champions 555

The Prufer Code 555

The Rotation Game 557

The SetStack Computer 558

The Sky is the Limit 558

The Staircases 559

The Sultan’s Problem 560

The Teacher’s Side of Math 560

The Warehouse 561

Theodore Roosevelt 562

Thermal Death of the Universe 562

Ticket Office 563

Ticket to Ride 564

Tiling Dominoes 564

Titanic 565

Tmutarakan exams 566

To Go or Not to Go 566

To xor or not to xor 567

Toll Road 567

Top Secret 568

Total Solar Eclipse 568

Tower of Hanoi 569

Trade 570

Traffic Jam 570

Train 571

Training little cats 572

Transcribed Books 572

Transversal 573

Trash 574

Travelling tours 574

Treasuty 575

Tree 2 575

Tri 576

Trie， Trie Again 577

Trigonometric Optimization 578

Trip 579

TUSK 580

Twist and whirl-want to cheat 580

Two professors 581

Two shortest 582

UFO Circles 583

Undetectable Tour 584

Unequalled Consumption 585

Unique Attack 585

Very Simple Counting 586

Walls II 586

Walls 587

Warping of N Dimensional Space 588

Water Ring 588

Weapon 589

Weird Dissimilarity 590

Wheel Good 590

Which is next 591

White Streaks 592

Winsock 3 Beta 593

Wolves and Sheep 593

Wonder Team 594

Working at the Restaurant 595

Worms 595

X+R（X）=N 596

XOR Sum 597

Youth Hostel Dorm 597

Yungom 598

ZMAJ 599

Zones 599

瑰丽华尔兹 600

智慧珠游戏 601

植物大战僵尸 601

附录1按赛区题库索引 603

附录2赛区题库缩写对照表 622