挑戰程序設計競賽（第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

二分：

最大化最小值

***POJ - 3258 River Hopscotch 二分+最大化最小值

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

先列出框架，后面陸續補充，勿催，加急中。。。

總結

以上是生活随笔為你收集整理的备战ccpc分站赛：秦皇岛和威海站（数论模块和dp模块）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。