挑战程序设计竞赛（第2版）练习题

tips：难度（个人主观判断）：

简单* 简单但卡思维 ** 中 *** 中稍加思考 **** 难 *****

1 . 记录结果再利用的“动态规划”

（1）基础的动态规划算法：

* POJ 3176 Cow Bowling 基础的动态规划算法 **POJ 2229 Sumsets 计数dp **POJ 2385 Apple Catching 基础的动态规划算法 POJ 3616 POJ 3280

优化递推关系式：

****POJ 1742 Coins 多重背包+是否装满问题 POJ 3046 POJ 3181

需要稍加思考的题目：

**POJ 1065 Wooden Sticks 最大上升子序列+动态规划状态转移思维 POJ 1631 POJ 3666 POJ 2392 POJ 2184

2. 数学问题的解题窍门

辗转相除法：

*Aizu 0005 GCD and LCM 辗转相除 *****POJ 2429 GCD & LCM Inverse java或【Miller Rabin素数測试】+【Pollar Rho整数分解】 POJ 1930

素数：

*Aizu 0009 Prime Number 素数筛 POJ 3126 POJ 3421 POJ 3292

快速幂运算：

*POJ 3641 Pseudoprime numbers 快速幂+判素数 POJ 1995

3.常用技巧精选（一）

尺取法：

*** POJ 2566 Bound Found 尺取法+前缀和创造区间变化趋势 ** POJ 2739 Sum of Consecutive Prime Numbers 线性欧拉筛+尺取法 POJ 2100

反转：

**POJ 3185 The Water Bowls 开关问题+暴力 POJ 1222

弹性碰撞：

*** POJ 2674 Linear world 弹性碰撞+技巧

折半枚举：

***POJ Subset 3977 折半枚举+二分 POJ 2549

坐标离散化：

Aizu 0531

4. 与平面和空间打交道的计算几何

极限情况：

*** POJ 1981 Circle and Points 单位圆覆盖最多点 POJ 1418 Aizu 2201

平面扫描：POJ 3168 POJ 3293 POJ 2482

凸包：POJ 1113 POJ 1912 POJ 3608 POJ 2079 POJ 3246 POJ 3689

数值积分：Aizu 2256 Aizu 2215

5. 更加复杂的数学问题

模运算的世界：

**** POJ 1150 The Last Non-zero Digit （n!mod p） POJ 1284 POJ 2115 POJ 3708 POJ 2720

矩阵：

POJ 2345 POJ 3532 POJ 3526

计数：

POJ 2407 POJ 1286 POJ 2409 Aizu 2164 Aizu 2214

6. 找出游戏的必胜策略

推理与动态规划算法：

POJ 1082 Calendar Game关于日历的博弈问题 POJ 2068 POJ 3688 POJ 1740

Nim与Grundy数：

POJ 2975 POJ 3537 CodeForces 138D POJ 2315

7. 华丽地处理字符串

动态规划算法：

Aizu 2212 CodeForces 86C

字符串匹配：

CodeForces 25E Aizu 1312

后缀数组：

POJ 1509 POJ 3415 POJ 3729 Aizu 2292 CodeForces 123D

先列出框架，后面陆续补充，勿催，加急中。。。