acm-challenge-workbook

1 前言

项目为《挑战程序设计竞赛（第2版）》习题册攻略，已完结。可配合书籍或笔记，系统学习算法。

• 题量：约200道，代码注释内含详解。
• 难度：总体高于Leetcode，部分接近ACM。
• 题解：代码均AC，题解个人向；Bug或优化请建Issue或Pull Request。

1.1 题库来源

• Google Code Jam（GCJ）
• Peking University Online Judge（POJ）
• Aizu Online Judge（AOJ）
• UVa Online Judge（UVa）
• CodeForces（CF）

1.2 算法笔记

• 初级篇
• 中级篇
• 高级篇

1.3 题库目录

• 初级： 穷竭搜索、 贪心法、 动态规划、 数据结构、 图论、 数论

• 中级： 二分搜索、 常用技巧、 数据结构（二）、 动态规划（二）、 网络流、 计算几何

• 高级： 数论（二）、 博弈论、 图论（二）、 常用技巧（二）、 智慧搜索、 分治、 字符串

2 初级算法

2.1 穷竭搜索

• 深度优先搜索

  • POJ 1979: Red and Black
  • AOJ 0118: Property Distribution
  • AOJ 0033: Ball
  • POJ 3009: Curling 2.0

• 宽度优先搜索

  • AOJ 0558: Cheese
  • POJ 3669: Meteor Shower
  • AOJ 0121: Seven Puzzle

• 穷竭搜索

  • POJ 2718: Smallest Difference
  • POJ 3187: Backward Digit Sums
  • POJ 3050: Hopscotch
  • AOJ 0525: Osenbei

2.2 贪心法

• 区间贪心

  • POJ 2376: Cleaning Shifts
  • POJ 1328: Radar Installation
  • POJ 3190: Stall Reservations

• 其他贪心

  • POJ 2393: Yogurt factory
  • POJ 1017: Packets
  • POJ 3040; Allowance
  • POJ 1862: Stripies
  • POJ 3262: Protecting the Flowers

2.3 动态规划

• 基础DP

  • POJ 3176: Cow Bowling
  • POJ 2229: Sumsets
  • POJ 2385: Apple Catching
  • POJ 3616: Milking Time
  • POJ 3280: Cheapest Palindrome

• 优化递推式

  • POJ 1742: Coins
  • POJ 3046: Ant Counting
  • POJ 3181: Dollar Dayz

• 进阶DP

  • POJ 1065: Wooden Sticks
  • POJ 1631: Bridging signals
  • POJ 3666: Making the Grade
  • POJ 2392: Space Elevator
  • POJ 2184: Cow Exhibition

2.4 数据结构

• 优先队列

  • POJ 3614: Sunscreen
  • POJ 2010: Moo University - Financial Aid

• 并查集

  • POJ 2236: Wireless Network
  • POJ 1703: Find them, Catch them
  • AOJ 2170: Marked Ancestor

2.5 图论

• 最短路

  • AOJ 0189: Convenient Location
  • POJ 2139: Six Degrees of Cowvin Bacon
  • POJ 3259: Wormholes
  • POJ 3268: Silver Cow Party
  • AOJ 2249: Road Construction
  • AOJ 2200: Mr. Rito Post Office

• 最小生成树

  • POJ 1258: Agri-Net
  • POJ 2377: Bad Cowtractors
  • AOJ 2224: Save Your Cats
  • POJ 2395: Out of Hay

2.6 数论

• 辗转相除法

  • AOJ 0005: GCD and LCM
  • POJ 2429: GCD & LCM Inverse
  • POJ 1930: Dead Fraction

• 素数

  • AOJ 0009: Prime Number
  • POJ 3126: Prime Path
  • POJ 3421: X-factor Chains
  • POJ 3292: Semi-prime H-numbers

• 快速幂

  • POJ 3641: Pseudoprime numbers
  • POJ 1995: Raising Modulo Numbers

3 中级算法

3.1 二分搜索

• 最大化最小值

  • POJ 3258: River Hopscotch
  • POJ 3273: Monthly Expense
  • POJ 3104: Drying
  • POJ 3045: Cow Acrobats

• 01分数规划

  • POJ 2976: Dropping tests
  • POJ 3111: K Best

• 第k大值

  • POJ 3579: Median
  • POJ 3685: Matrix

• 最小化第k大值

  • POJ 2010: Moo University - Financial Aid
  • POJ 3662: Telephone Lines

• 其他二分搜索

  • POJ 1759: Garland
  • POJ 3484: Showstopper

3.2 常用技巧

• 尺取法

  • POJ 2566: Bound Found
  • POJ 2739: Sum of Consecutive Prime Numbers
  • POJ 2100: Graveyard Design

• 反转

  • POJ 3185: The Water Bowls
  • POJ 1222: EXTENDED LIGHTS OUT

• 弹性碰撞

  • POJ 2674: Linear world

• 折半枚举

  • POJ 3977: Subset
  • POJ 2549: Sumsets

• 离散化

  • AOJ 0531: Paint Color

3.3 数据结构（二）

• 树状数组

  • POJ 1990: MooFest
  • POJ 3109: Inner Vertices
  • POJ 2155: Matrix
  • POJ 2886: Who Gets the Most Candies?

• 线段树和平方分割

  • POJ 3264: Balanced Lineup
  • POJ 3368: Frequent values
  • POJ 3470: Walls
  • POJ 1201: Intervals
  • UVa 11990: "Dynamic" Inversion

3.4 动态规划（二）

• 状态压缩DP

  • POJ 2441: Arrange the Bulls
  • POJ 3254: Corn Fields
  • POJ 2836: Rectangular Covering
  • POJ 1795: DNA Laboratory
  • POJ 3411: Paid Roads

• 矩阵的幂

  • POJ 3420: Quad Tiling
  • POJ 3735: Training little cats

• 数据结构与DP

  • POJ 3171: Cleaning Shifts

3.5 网络流

• 最大流与最小割

  • POJ 3713: Transferring Sylla
  • POJ 2987: Firing
  • POJ 2914: Minimum Cut
  • POJ 3155: Hard Life

• 二分图匹配

  • POJ 1274: The Perfect Stall
  • POJ 2112: Optimal Milking
  • POJ 1486: Sorting Slides
  • POJ 1466: Girls and Boys
  • POJ 3692: Kindergarten
  • POJ 2724: Purifying Machine
  • POJ 2226: Muddy Fields
  • AOJ 2251: Merry Christmas

• 最小费用流

  • POJ 3068: "Shortest" pair of paths
  • POJ 2195: Going Home
  • POJ 3422: Kaka's Matrix Travels
  • AOJ 2266: Cache Strategy
  • AOJ 2230: How to Create a Good Game

3.6 计算几何

• 极限

  • POJ 1981: Circle and Points
  • POJ 1418: Viva Confetti
  • AOJ 2201: Immortal Jewels

• 平面扫描

  • POJ 3168: Barn Expansion
  • POJ 3293: Rectilinear polygon
  • POJ 2482: Stars in Your Window

4.1 数论（二）

• 模运算

  • POJ 1150: The Last Non-zero Digit
  • POJ 1284: Primitive Roots
  • POJ 2115: C Looooops
  • POJ 3708: Recurrent Function
  • POJ 2720: Last Digits
  • GCJ 2011 Final B: Bacterial Reproduction

• 矩阵

  • POJ 2345: Central heating
  • POJ 3532: Resistance
  • POJ 3526: The Teacher’s Side of Math

• 计数

  • POJ 2407: Relatives
  • POJ 1286: Necklace of Beads
  • POJ 2409: Let it Bead
  • AOJ 2164: Revenge of the Round Table
  • AOJ 2214: Warp Hall

4.2 博弈论

• 博弈DP

  • POJ 1082: Calendar Game
  • POJ 2068: Nim
  • POJ 3688: Cheat in the Game
  • POJ 1740: A New Stone Game

• Nim和Grundy数

  • POJ 2975: Nim
  • POJ 3537: Crosses and Crosses
  • CF 138D: World of Darkraft
  • POJ 2315: Football Game

4.3 图论（二）

• 强连通分量

  • POJ 3180: The Cow Prom
  • POJ 1236: Network of Schools

• 2-SAT

  • POJ 3678: Katu Puzzle
  • POJ 2723: Get Luffy Out
  • [POJ 2