竞赛程序设计知识要点图谱

一、基础算法

1.枚举法

POJ1248 Safecracker

HDU1172 猜数字

POJ1543 Perfect Cubes

POJ1046 Color Me Less

2.递归法:Hanoi塔、Fibonacci数列、整数划分问题、排列问题

POJ1664 放苹果

3.分治法:快速排序、归并排序

4.贪心法:删数问题、背包问题

POJ2287 Tian Ji -- The Horse Racing

POJ1065 Wooden Sticks

POJ1042 Gone Fishing

HDU2570 迷瘴

HDU1735 字数统计

HDU1009 FatMouse' Trade

5.排序

6.模拟

POJ1028 Web Navigation

HDU3052 Vim

UVA10315 Poker Hands

POJ2269 Friends

UVA486 English-Number Translator

7.水题


二、数据结构与STL

1.基本数据结构:堆栈、队列、堆、并查集

POJ2082 Terrible Sets

POJ2258 Team Queue

POJ2051 Argus

POJ1703 Find them, Catch them

2.线段树

POJ3182 Lost Cows

POJ2528

3.树状数组

POJ2352 Stars

4.搜索树:二叉搜索树、AVL搜索数、红黑树、伸展树、Treap数堆、SBT、跳跃表

POJ2418 Hardwood Species

POJ3481 Double Queue

POJ2761 Feed the dogs

5.Hash表

POJ2503 Babelfish

6.左偏树

HDU1512 Monkey King

7.STL


三、动态规划

1.动态规划简介

2.线性动态规划

POJ2479 Maximum sum

POJ1458 Common Subsequence

POJ1159 Palindrome

POJ2533 Longest Ordered Subsequence

3.树形动态规划

POJ1463 Strategic Game

4.概率动态规划

POJ3071 Football

5.状态压缩动态规划

POJ1038 Bugs Integrated


四、数学问题

1.乘方取模与矩阵快速幂

POJ3761 Bubble Sort

POJ3735 Training little cats

2.欧几里得算法

POJ1061 青蛙的约会

3.数制与分数

POJ1220 Number Base Conversion

POJ3191 The Moronic Cowmpouter

4.欧拉函数

POJ2407 Relatives

5.素数判定与大数分解

POJ1811 Prime Test

6.中国剩余定理

POJ2891 Strange Way to Express Integers

7.Polya原理

POJ2409 Let it Bead


五、计算几何

1.矢量

POJ1269

2.线段相交

3.线段合并

POJ2074 Line of Sight

4.凸包

POJ3348 cows

5.最近点对

POJ3714 Raid

6.半平面交

POJ3384 Feng Shui

7.旋转卡壳

POJ2187 Beauty contest

8.扫描线

POJ1151 Atlantis


六、搜索算法

1.深度优先搜索

POJ1011 Sticks

2.广度优先搜索

POJ3278 Catch That Cow

3.启发式搜索:A*算法

POJ1077 Eight


六、图算法

1.图的表示

2.最短路算法:Dijkstra算法、SPFA算法、Floyd最短路径算法

POJ1797 Heavy Transportation

POJ1511 Invitation Cards

POJ1125 Stockbroker Grapevine

3.生成树算法:Prim算法、Kruskal算法

POJ1258 Agri-Nets

POJ2485 Highways

POJ1679 The Unique MST

POJ2728 Desert King

POJ1639 Picnic Planning

4.图连通性:欧拉回路、Hamilton回路

POJ2186 Popular

POJ3177 Redundant Paths

POJ1144 Network

5.网络流:DINIC算法、SAP算法、SPFA算法

POJ1459 Power Network

POJ1149 PIGS

6.二分图匹配:KM算法

POJ2239 Selecting Courses

POJ2536 Gopher II

POJ3686 The Windy's


七、字符串算法

1.KMP算法

    POJ2752 Seek the Name, Seek the Fame

2.字典树

    POJ2503

3.AC自动机

    POJ2778 DNA Sequence

4.后缀数组

    POJ3294 Life Forms

相关文章
相关标签/搜索