Hal Burch conducted an analysis over spring break of 1999 and made an amazing discovery: there are only 16 types of programming contest problems! Furthermore, the top several comprise almost 80% of the problems seen at the IOI. Here they are:
Dynamic Programming
Greedy
Complete Search
Flood Fill
Shortest Path
Recursive Search Techniques
Minimum Spanning Tree
Knapsack
Computational Geometry
Network Flow
Eulerian Path
Two-Dimensional Convex Hull
BigNums
Heuristic Search
Approximate Search
Ad Hoc Problems
The most challenging problems are Combination Problems which involve a loop (combinations, subsets, etc.) around one of the above algorithms - or even a loop of one algorithm with another inside it. These seem extraordinarily tricky to get right, even though conceptually they are ``obvious''.
If you can master solving just 40% of these problem types, you can almost guarantee a silver medal at the IOI. Mastering 80% moves you into the gold range almost for sure. Of course, `mastery' is a tough nut to crack! We'll be supplying a plethora of problems so that you can hone your skills in the quest for international fame.
简单翻译一下:
文中提到的IOI，即国际信息学奥林匹克竞赛
与之对应的NOI，即全国信息学奥林匹克竞赛
我想楼主说的“电脑如果在全国获奖”，应该就是指的这个，文中讲题目类型进行了分类，我想“需要什么才能”这个问题你看了题目类型分类就明了了。
动态规划
贪心
完全搜索
满水法填充
最短路径
递规搜索
最小生成树
背包
计算几何
网络流
欧拉路径
2D凸包
大整数
启发式搜索
近似搜索
特别问题
Dynamic Programming
Greedy
Complete Search
Flood Fill
Shortest Path
Recursive Search Techniques
Minimum Spanning Tree
Knapsack
Computational Geometry
Network Flow
Eulerian Path
Two-Dimensional Convex Hull
BigNums
Heuristic Search
Approximate Search
Ad Hoc Problems
The most challenging problems are Combination Problems which involve a loop (combinations, subsets, etc.) around one of the above algorithms - or even a loop of one algorithm with another inside it. These seem extraordinarily tricky to get right, even though conceptually they are ``obvious''.
If you can master solving just 40% of these problem types, you can almost guarantee a silver medal at the IOI. Mastering 80% moves you into the gold range almost for sure. Of course, `mastery' is a tough nut to crack! We'll be supplying a plethora of problems so that you can hone your skills in the quest for international fame.
简单翻译一下:
文中提到的IOI，即国际信息学奥林匹克竞赛
与之对应的NOI，即全国信息学奥林匹克竞赛
我想楼主说的“电脑如果在全国获奖”，应该就是指的这个，文中讲题目类型进行了分类，我想“需要什么才能”这个问题你看了题目类型分类就明了了。
动态规划
贪心
完全搜索
满水法填充
最短路径
递规搜索
最小生成树
背包
计算几何
网络流
欧拉路径
2D凸包
大整数
启发式搜索
近似搜索
特别问题
