ACM国际大学生程序设计竞赛 题目与解读[PDF电子书版本下载]-书葵网 (2024)

第一部分 例题精讲3

第1章 数学3

1.1概率3

Coupons3

Generator3

1.2代数4

1.2.1 Polya4

Arif in Dhaka（First Love Part 2）4

1.2.2矩阵5

Tower5

XX Language6

1.2.3线性方程组7

Ars Longa7

1.2.4线性规划8

Expensive Drink8

1.3组合9

1.3.1基本排列组合9

The Unreal Tournament9

1.3.2容斥原理10

Jackpot10

The Almost Lucky Numbers11

1.3.3生成函数12

Vasya’s Dad12

1.3.4生成树计数13

Organising the Organisation13

1.3.5综合14

Hero of Our Time14

Permutation15

1.4博弈17

Battle for the Ring17

Fool’s Game17

Points Game18

1.5数论20

1.5.1模线性方程20

Integer Sequences20

1.5.2欧几里得20

Wizards20

1.5.3欧拉定理21

Strange Limit21

1.5.4欧拉函数22

GCD Determinant22

1.5.5平方剩余23

Square Root23

1.5.6原根24

Fermat’s Last Theorem24

1.5.7整除与剩余26

Brute-Force Algorithm26

Integral Roots26

Vivian’s Problem27

1.5.8中国剩余定理28

Voyager 128

1.6分析29

Bridge29

第2章 数据结构31

2.1优先队列31

The Lazy Programmer31

2.2线性表32

Book Pile32

2.3散列表32

Language Recognition32

2.4并查集33

Feel Good33

Parity34

2.5排序35

Inversions35

All for Love35

2.6 ST表37

Lubenica37

2.7树状数组38

Elections38

Stars39

2.8线段树40

Dynamic Rankings40

Wild West41

2.9可并堆41

Monkey King41

2.10平衡树42

Treediff42

维护数列43

2.11动态树44

OTOCI44

第3章 图论46

3.1路径46

3.1.1连通性46

Network Attack46

Synchrograph47

3.1.2欧拉路48

Strange Graph48

3.1.3基本最短路49

Animal Run49

New Islands50

Recover Path51

Suffix-Replacement Grammars52

3.1.4有负权的最短路53

Layout53

Sightseeing Cows53

Word Rings54

3.2匹配55

3.2.1二分图匹配55

Double NP-hard55

Emergency Pizza Order56

Number Graph56

Rooks58

3.2.2二分图最优匹配59

Railway Communication59

The Great Wall Game60

Warehouse61

3.2.3稳定婚姻61

Ladies’ Choice61

3.3树62

3.3.1最小生成树62

Confiidential62

Island Explorer63

3.3.2最优比率生成树64

Portkey Network64

3.4网络流65

3.4.1最大流（最小割）65

Bomb， Divide and Conquer65

Buy one， get the rest free66

Destroying The Graph67

Dual Core CPU68

Network Wars68

Rectangle of Permutation69

The Glorious Karlutka River71

3.4.2有上下界的网络流72

Flow construction72

Reactor Cooling72

3.4.3费用流73

Highway Patrol73

Insurrection74

Paint the Roads75

Shortest pair of paths76

第4章 计算几何77

4.1多边形77

Areas77

Cave Crisis78

Chocolate79

Ancient vending machine80

Fool’s Day81

4.2圆82

Sweet Dream82

Malfatti Circles83

Get Out！84

Biscuits85

4.3凸包85

Mixed Juice85

Fuel86

4.4半平面交87

Fairies’ Defense87

Largest Circle88

4.5离散化89

Phone cell89

Shy Polygons90

降雨量91

月下柠檬树92

4.6立体几何94

3D Triangles94

Lowest Pyramid94

The Return of Carl96

第5章 求解策略97

5.1搜索97

Holedox Moving97

Insecure in Prague98

Mines For Diamonds99

Power Calculus101

智破连环阵102

5.2贪心103

Beijing Guards103

Body Check104

Cow Acrobats104

Keep the Customer Satisfiied105

5.3递推106

Dispute106

Dropping water balloons107

Questions108

管道取珠109

5.4分治110

Friendly Points110

Mokia111

Tree112

5.5动态规划113

5.5.1经典问题113

Boxes of Chocolates Again113

Greatest Common Increasing Subsequence114

Inheritance114

Long Live the Queen115

Prince and Princess116

5.5.2朴素动态规划116

Clock116

Damn Couples117

Decrypt the Dragon Scroll118

Dice contest120

Drive through MegaCity120

Facer’s Chocolate Dream122

Incredible！123

Lights124

Network Connection124

Painting the balls125

Persephone126

Post offices127

Salary for Robots128

Salesman130

Shoveling Snow131

Strange Dream132

The Best Name for Your Baby133

The Bookcase134

Think Positive134

Wildcards136

Yet Another Answer137

二叉查找树137

5.5.3树形138

Apple Transportation138

Chandelier140

Counting heaps141

Succession142

Tribe Council143

Vaccination Centers144

网络收费145

5.5.4按位动态规划146

Almost Lucky Numbers146

Amount Of Degrees147

Hotel in Ves Lagos147

Password Remembering148

5.5.5状态压缩149

Controlled Tournament149

Easter Eggs149

Fun Game150

Integer Transmission151

5.5.6连通性152

Connect152

Channel153

Manhattan Wiring155

Paint Me Less156

Pipes157

Tour in the Castle159

5.5.7优化160

Euro160

Fibonacci Subsequence163

Nice Prefixes164

Quadratic Functions166

Two Sawmills167

Frogs169

诗人小G171

5.6模拟172

Archery172

Exiting Time173

Flip and Turn175

Water Tanks175

5.7构造177

Airline Company177

Funny Language178

Payment System178

Square country 3.179

Train Car Sorting180

5.8二分180

Array Transformations180

Doors182

Food Competition183

5.9三分184

Fire Station Building184

5.10离散化184

Crop circles184

5.11遗传算法186

Sherlock Holmes186

第6章 论题选编188

6.1字符串188

6.1.1 KMP188

Cow Patterns188

6.1.2 Trie树189

Billing Table189

6.1.3后缀数组189

Stammering Aliens189

Common Substrings190

Connecting the Segments191

6.1.4自动机192

Censored！192

6.1.5 Rabin-Karp193

Square Palindrome193

6.2最近公共祖先195

The Merchant195

Transportation Network196

Design the city196

6.3 2-SAT197

Game with cards197

Cipher198

6.4快速傅立叶变换199

K-neighbor substrings199

第二部分 题库203

4 Values Whose Sum is 0203

8G Island203

A Binary Apple Tree204

A Dinner with Schwarzenegger!!!204

A Foldy but a Goody205

A Game with Colored Balls206

A Line Painting207

A Secret Book207

A Simple Pendulum208

Abelian Groups209

Aerodynamic209

Again Palindrome210

Against Mammoths210

Air Conditioning Machinery211

All Your Bases Belong to Us212

Alphabet213

Alternating Sum of Digits214

Always an Integer215

Amphiphilic Carbon Molecules216

Anansi’s Cobweb216

Ancient decoration217

Angry Teacher218

Anniversary Party218

Another Chocolate Maniac219

Another Minimum Spanning Tree220

Ants II221

Ants221

Apple or Doughnut222

Archipelago222

Area 51223

Arrays224

Art of War225

Asteroids226

Astronomy226

Autocompletion227

Automaton228

B-Station229

Balance229

Barisal Stadium233

Battle234

Battle of the Triangle234

Battle235

Be a Smart Raftsman236

Be Wary of Roses237

Beloved Sons238

Best Cow Line， Gold238

Bigger is Better239

Binary Lexicographic Sequence239

Bingo240

Bishops241

Bit Compressor242

Bitmap242

Black & White243

Black Box243

Black Vienna244

Black-white king245

Blind Walk246

Bone Sort247

Boring Sequence Operations248

Boring.Hot.Summer249

Breadtree249

Bridges250

Broken Chessboard251

Bubble Sort251

Business Center252

Buttons253

Buy or Build254

Cactus254

Cake Share255

Camera in the Museum255

Card Game256

Casino257

Castles259

Cave Exploration260

Centers Of Symmetry261

Central Heating261

Centroid262

Challenge of Bravery262

Challenge of Wisdom263

Chameleons All Around263

Changing Digits265

Chapayev265

Chemist’s Math266

Chessmaster267

ChiBi268

Chinese Hockey268

Choose The Best269

Choreographer Problem269

Circle Drawing270

Circular Railway271

Clever’s Problem272

Cliquers strike back272

co*cktail273

Collecting Bugs274

Collecting Luggage275

Collector’s Problem276

Color a Tree276

Colorful Decoration277

Combinations278

Compositions278

Compressed String279

Concatenation of280

Languages280

Conduit Packing281

Confectionery281

Connect It， If You Can！282

Connecting People283

Connections in Galaxy War284

Consecutive Ones284

Constructive Plan285

Cookie Choice Ⅱ286

Cookie Choice286

Cover an Arc287

Coverage287

Crack288

Cracking RSA289

Crazy Professor289

Crazy Thairs290

Cross Counting291

Cross Stitch292

Crossing Streets293

Crossing294

Cryptography294

Cube Root295

Cubes296

Cyclic Polygons297

Dangerous Pattern297

Darkterror’s Combos298

｛Sum+=i++｝ to Reach N299

Darts299

Deciphering300

Dendrograms301

DFA302

Dice Compare302

Difference Is Beautiful303

Different Digits304

Dig or Climb304

Digit Counting306

Digit Puzzle307

Dinner’s Ready308

Dirt308

Discrete Roots309

Distinct Substrings310

Divide and conquer311

Divisibility by 15311

Divisibility Testing！ Wow！312

Document Indexing313

Dog Distance314

Domestic Networks314

Domino Sorting315

Door painting315

Double Cyclic316

Double Patience317

Driving Directions317

Droid Formation319

Dueue’s Quiz320

Dungeon321

Duopoly321

dwarfs322

Edison323

Editor Nottobad324

Electrician325

Elementary symmetric functions325

Elevator326

Ellipse327

Equal Squares327

Equation329

Escape From Enemy Territory329

Evacuation Plan330

Exclusive Access 2.330

Expectation331

Expedition331

Exploring Pyramids332

Expression Evaluation333

Eyeball Benders334

Fall the Brick334

Farey Sequence335

Fast Typing337

Fence338

Feng Shui338

Ferry Lanes339

Fibonacci System339

File System Travel340

Find a Multiple341

Find the Border341

Find the Latitude342

Find the Number343

Finding Treasure344

Fixing the Great wall345

Flight Safety345

Fliptile347

Flying Right348

Fold Paper Strips349

Foot Notes350

Formula350

From G to H and back351

Full Steiner Topologies352

Fund Management353

Funny Feature354

Funny Strings354

Gaby Ivanushka355

Game for Little Johnny357

Game358

Garbling Game358

Garlands359

Gena’s Soul Cake360

Geometrical Dreams361

Geometry Problem362

Given a string362

Go Downstairs362

Gold Balanced Lineup363

Gold Bars364

Google Book364

Gourmet Grazers365

Great Berland Wall366

Greatest Greatest Common Divisor367

Greedy Path367

Guards367

Gunman369

Hanoi Tower369

Hard Life371

Harder Sokoban Problem371

Hardwood Cutting372

Harmony Forever373

Haybale Guessing373

H eapsort374

Heavy Disc375

Height， Bisector and Median376

Hell on the Markets376

Help Bubu377

Help Little Laura378

Here’s a Product Which Will Make You Tensor378

Heroes379

Hexagon Coin Toss380

Hexagonal Parcels382

Hills382

Holey Square Tiling383

Horn Clauses385

Hour Glass386

How Many bases？387

How many ones needed387

Huffman Codes388

Hyperrook389

I-country389

Ice-cream Tycoon390

Ideal Frame391

Illuminated Planet392

Illumination of Buildings392

Ilya Murometz393

Immaterial and Missing Power393

Impudent Thief394

In the army now395

Increasing Subsequences395

Infected Land396

Infiinite Fraction397

Inheritance397

Inner Vertices398

Inspection399

Intelligent Cats399

Interconnect400

Interesting Yang Hui Triangle401

Irrelevant Element402

Islands and Bridges402

It’s Never Too Late403

Jacks Socks404

Jacquard Circuits404

Jam’s Store405

Japanese Puzzle405

Java Certification406

Jenny’s First Exam407

Joke with Turtles407

Journey408

Journey with Pigs409

Jumping Joe409

K Best410

K-based Numbers. Version 3411

K-th Number411

Kadj Squares412

Kaka’s Matrix Travels412

Key Insertion413

Key Substrings414

Key Task415

Keyword416

Khepel’s Problem416

Kindergarten Graduation417

King Berl Ⅵ417

Kingdom Partitioning418

Kingdom Map419

Knapsack Ⅱ420

Knights of the Round Table420

Knowledge for the masses421

Landscaping422

Lap time in a racing circuit423

Largest Rectangle in a Histogram424

Laser Ball424

Lattice Animals425

Lattice Squares426

Lazy Cows426

Lazy Susan427

Leonardo’s Notebook428

Let’s play a game429

Liar or Not Liar that is the429

Lifting the stone430

Light430

Lights431

Line Chart432

Lineland’s Airport433

Link434

Little Jumper435

Longest Repeated435

Substring435

Lottery436

Love for Pizza437

Lucky cities437

Lucky numbers438

Lucky Tickets438

Machine Schedule439

Magic Car440

Magic Pairs440

Magic Rings441

Magic Seven442

Mahjong443

Map Generator444

Marble Game445

March of the Penguins446

Martian Mining446

Mathematics Ⅱ447

Mathematics448

Matrix Processing448

Matrix449

Maximal Clique450

Maximum Ⅱ451

Maximum452

Mechanics453

Median454

Meetings454

Mega Man’s Missions455

Military Game455

Ministry457

Mobile Positioning458

Mobile Tower459

Moles and Holes460

More Sweets！460

Mountain Road461

Mouse462

Movie Promotion463

Moving to Nuremberg464

National Park464

Net Loss465

Network Mess465

Network467

Never End468

New Go Game469

Nikifor’s walk469

Nikifor-3470

No Smoking471

Nuclear Plants472

Number Game473

Number Permutations474

Obfuscation475

Objective Berlin476

Obscene words filter476

Observers Coloring477

Optimal Dartboard478

Optimal Strategy for the ICPC478

Order479

Orthogonal Circles479

Pairs480

Palindrom481

Palindromic Subsequence481

Party of 8g482

Pascal vs C++483

Pass Licenses484

Password Suspects484

Perspective485

Petya the Hero486

Pinocchio486

Piotr’s Ants487

PLAHTE488

Playing with Matches488

Plot Purchase489

Police and Thief490

Polygon490

Postal Charges491

Prefiixes and Suffixes492

Present for MM492

Prester John493

Problem Stacks494

Protecting Zonk494

Prototype496

pyramid497

Quad Tiling498

Quadratic Equation498

Rabbit Hunt499

Racing Route499

Railway Tickets500

Random Walk501

Rebus502

Rectangular Polygons503

Regions504

Repair Depots504

Requirements505

Resistance506

Right Words506

Rings’n’Ropes507

Roads508

Robot508

Rooks509

Room Assignments509

Rotating a Frame510

Rotation Estimation511

Routing II512

Routing513

Ruler514

Sails515

Search for a Hiding-Place516

Searching the String517

Security by Ambiguity518

Separate Points519

Sequence Median520

Sequence520

Sequence Sum521

Shadow Area522

Sharif Super Computer523

Shoot the Bullet523

Shoot your gun！524

Sightseeing525

Signals and Systems525

Simple Game on a Grid526

Simple Sequence526

Slalom527

Snake528

Special Subsequence529

Square Country 2530

Square530

Stone Grid531

Strange Game532

Strange People533

Street Lamp534

Student’s Morning534

Subnumber535

Suffiix reconstruction536

Super Snake537

Super squares537

Super Memo538

Sweet539

Switchback540

Taxi541

Team Building541

Team Forming542

Team Tryouts542

That Nice Euler Circuit544

The Archaeologist’s Trouble Ⅱ544

The art to the broad masses！545

The book546

The Deadly Olympic Returns546

The Different Task547

The Gossiping System548

The Great Escape548

The Greatest Angle549

The Laurel Hardy Story550

The longest constant gene551

The Lucky Numbers551

The Mastermind Master’s Mind552

The Merchant Guild553

The Monochrome Picture554

The Most Frequent Number554

The Party of Ural Champions555

The Prufer Code555

The Rotation Game557

The SetStack Computer558

The Sky is the Limit558

The Staircases559

The Sultan’s Problem560

The Teacher’s Side of Math560

The Warehouse561

Theodore Roosevelt562

Thermal Death of the Universe562

Ticket Office563

Ticket to Ride564

Tiling Dominoes564

Titanic565

Tmutarakan exams566

To Go or Not to Go566

To xor or not to xor567

Toll Road567

Top Secret568

Total Solar Eclipse568

Tower of Hanoi569

Trade570

Traffic Jam570

Train571

Training little cats572

Transcribed Books572

Transversal573

Trash574

Travelling tours574

Treasuty575

Tree 2575

Tri576

Trie， Trie Again577

Trigonometric Optimization578

Trip579

TUSK580

Twist and whirl-want to cheat580

Two professors581

Two shortest582

UFO Circles583

Undetectable Tour584

Unequalled Consumption585

Unique Attack585

Very Simple Counting586

Walls II586

Walls587

Warping of N Dimensional Space588

Water Ring588

Weapon589

Weird Dissimilarity590

Wheel Good590

Which is next591

White Streaks592

Winsock 3 Beta593

Wolves and Sheep593

Wonder Team594

Working at the Restaurant595

Worms595

X+R（X）=N596

XOR Sum597

Youth Hostel Dorm597

Yungom598

ZMAJ599

Zones599

瑰丽华尔兹600

智慧珠游戏601

植物大战僵尸601

附录1按赛区题库索引603

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