第一部分 例 题 精 讲
第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
第二部分 题 库
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
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
Heapsort 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
Infinite 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
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
Prefixes 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 Ⅱ 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
Suffix 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 II 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
Treasury 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 赛区题库缩写对照表
