几个程序设计的训练网站给大家，供大家参考！
http://poj.org/ 北大的，比较难
http://acm.hdu.edu.cn/ 杭电的，相对容易
http://cm2prod.baylor.edu/welcome.icpc ACM/ICPC官方网站
### ACM程序设计大赛知识点解析
#### 一、训练网站推荐
1. **北京大学POJ (Problem Online Judge)**
- **网址**: http://poj.org/
- **难度**: 较高
- **特点**: 提供了大量的算法题目，涵盖各种难度级别，尤其适合已经有一定基础的学生进一步提升自己的算法能力。
- **适用人群**: 对算法有一定了解，希望通过挑战难题来提高自己水平的学生。
2. **杭州电子科技大学OJ (Online Judge)**
- **网址**: http://acm.hdu.edu.cn/
- **难度**: 相对较低
- **特点**: 题目相对简单，适合初学者入门训练，同时也包含了一些中等难度的题目，便于逐步提升。
- **适用人群**: 刚接触算法的新手，或是希望从简单题目入手逐步提升的同学。
3. **ACM/ICPC国际大学生程序设计竞赛官方网站**
- **网址**: http://cm2prod.baylor.edu/welcome.icpc
- **特点**: 提供了竞赛的相关信息、历年赛题及解决方案等内容，是参加ACM/ICPC竞赛的重要资源。
- **适用人群**: 准备参加ACM/ICPC比赛的学生，以及希望深入了解竞赛相关信息的人群。
#### 二、推荐图书知识点概览
**《计算机常用算法与程序设计教程》**
- **作者**: 杨克昌
- **出版社**: 人民邮电出版社
- **推荐章节**: 第1-7章
1. **第1章: 算法与程序设计简介**
- **1.1 算法与算法描述**
- **算法**: 定义为解决问题的一系列明确指令。
- **算法描述**: 使用自然语言、流程图或伪代码等方式来表达算法。
- **1.2 算法复杂性分析**
- **时间复杂度**: 描述算法运行时间与输入数据规模之间的关系。
- **空间复杂度**: 描述算法运行过程中占用内存空间大小与输入数据规模之间的关系。
- **1.3 程序设计简介**
- **算法与程序**: 算法是解决特定问题的步骤集合，而程序则是实现算法的具体代码。
- **结构化程序设计**: 强调模块化、自顶向下设计的原则，便于理解和维护。
2. **第2章: 穷举与回溯**
- **2.1 穷举及其应用**
- **穷举概述**: 通过尝试所有可能的解来寻找正确答案的方法。
- **穷举应用**: 如求解组合数学中的问题。
- **2.2 穷举设计的优化**
- **优选穷举对象**: 选择更有效的变量或数据结构来减少穷举次数。
- **优化穷举循环参量**: 合理设置循环变量，避免不必要的重复计算。
- **精简穷举循环**: 通过对问题特性的分析，尽可能减少循环的执行次数。
- **2.3 回溯法及其描述**
- **回溯法**: 一种在遇到解空间的无效解时能够自动回退并继续寻找其他可能解的算法。
- **回溯法描述**: 使用树形结构来表示所有可能的解，通过剪枝减少搜索范围。
- **2.4 回溯设计应用**
- **桥本分数式**: 求解桥本分数式的最大值。
- **排列组合**: 求解特定条件下的排列或组合数量。
- **德布鲁金环序列**: 求解特定长度的环状序列。
- **高斯皇后问题及其拓展**: 求解N皇后问题的不同解法。
3. **第3章: 递归与分治**
- **3.1 递归及其应用**
- **递归**: 一个函数调用自身的过程。
- **递归应用**: 如斐波那契数列的计算。
- **3.2 分治法概述**
- **分治法基本思想**: 将大问题分解成若干个小问题来解决。
- **分治算法设计方法和特点**: 先将问题分成若干个子问题，再递归地求解这些子问题，最后将各个子问题的解合并得到原问题的解。
- **分治法的时间复杂度**: 通常可以通过主定理（Master Theorem）来估计分治算法的时间复杂度。
- **3.3 分治法的基本应用**
- **数据查找与排序**: 如快速排序、归并排序等。
- **计数逆序排名问题**: 计算一个数组中逆序对的数量。
- **投资问题**: 最优的投资策略问题。
4. **第4章: 递推**
- **4.1 递推概述**
- **递推算法**: 通过已知初始值和递推关系来求解问题的方法。
- **递推实施步骤与描述**: 确定初始条件，定义递推关系式。
- **4.2 递推数列**
- **裴波那契数列与卢卡斯数列**: 两种常见的递推数列。
- **分数数列**: 如求解特定形式的分数序列。
- **幂序列**: 按照指数规律增长的数列。
- **双关系递推数列**: 需要同时考虑两个变量的递推关系。
- **4.3 递推数阵**
- **杨辉三角**: 一种常用的数阵形式。
- **折叠方阵**: 特殊形状的数阵。
- **4.4 应用递推求解应用题**
- **猴子爬山问题**: 求解猴子爬山的最大步数。
- **整币兑零问题**: 给定面额和总金额，求解兑换方式。
- **整数划分问题**: 将一个正整数分解成若干个正整数之和的方式。
- **4.5 递推与递归比较**
- **区别与联系**: 递推和递归都是基于已知结果推导未知结果的思路，但递推通常不需要额外的空间栈来保存中间结果。
5. **第5章: 贪心算法**
- **5.1 贪心算法概述**
- **贪心算法**: 在每一步选择中都采取当前看起来最优的选择。
- **5.2 贪心算法的理论基础**
- **理论基础**: 贪心选择性质、最优子结构性质。
- **5.3 删数字问题**
- **问题描述**: 给定一个数字串和一个删除次数k，求出经过k次删除后可能获得的最大数字。
- **5.4 背包问题**
- **0-1背包问题**: 只能选择每个物品一次，求解最大价值。
- **可拆背包问题**: 物品可以分割，求解最大价值。
- **5.5 覆盖问题**
- **问题描述**: 通过最少的元素来覆盖整个集合。
- **5.6 图的着色问题**
- **问题描述**: 用尽可能少的颜色给图中的节点着色，使得相邻节点颜色不同。
- **5.7 遍历问题**
- **问题描述**: 求解图的所有节点的遍历顺序。
- **5.8 最小生成树**
- **问题描述**: 从一个加权无向图中找到一棵包含所有顶点的最小权值的树。
- **5.9 哈夫曼编码**
- **问题描述**: 根据字符出现频率构建最优前缀编码。
6. **第6章: 动态规划**
- **6.1 一般方法与求解步骤**
- **一般方法**: 通过记录子问题的结果来避免重复计算。
- **动态规划求解步骤**: 状态定义、状态转移方程、初始化、输出。
- **6.2 装载问题**
- **问题描述**: 给定一组物品的重量和价值，以及一个容量有限的背包，求解最大价值。
- **6.3 插入乘号问题**
- **问题描述**: 给定一系列数字，通过插入乘号使结果最大。
- **6.4 0-1背包问题求解**
- **0-1背包问题**: 物品不可分割，只能选择或不选择。
- **二维0-1背包问题**: 扩展版本，考虑多个限制条件。
- **6.5 最长子序列探索**
- **最长非降子序列**: 求解一个序列中最长的非降子序列。
- **最长公共子序列**: 求解两个序列的最长公共子序列。
- **6.6 最优路径搜索**
- **点数值三角形的最优路径搜索**: 从三角形顶部到底部的最大路径和。
- **边数值矩形的最优路径搜索**: 从矩阵左上角到右下角的最大路径和。
- **6.7 动态规划与其他算法的比较**
- **动态规划与递推比较**: 动态规划可以解决递推无法处理的状态依赖问题。
- **动态规划与贪心算法比较**: 动态规划适用于子问题有重叠的情况，而贪心算法则需要满足贪心选择性质。
7. **第7章: 模拟**
- **7.1 模拟概述**
- **模拟**: 通过编程模拟某个过程或现象。
- **7.2 运算模拟**
- **运算模拟描述**: 通过编程模拟具体的计算过程。
- **n个1的整除问题**: 求解特定形式的整除问题。
- **尾数前移问题**: 求解特定形式的整数移动问题。
- **阶乘与幂的计算**: 求解阶乘和幂运算。
- **求圆周率π**: 通过编程求解圆周率。
- **7.3 随机模拟**
- **进站时间模拟**: 模拟车站进站乘客的时间间隔。
- **蒙特卡罗模拟计算**: 通过随机抽样来估计数学问题的解。
- **模拟发扑克牌**: 模拟发牌过程。
- **7.4 操作过程模拟**
- **洗牌**: 模拟洗牌过程。
- **泊松分酒**: 模拟分酒过程。
- **模拟小孔流水**: 模拟水从小孔流出的过程。
- **7.5 模拟外索夫游戏**
- **问题描述**: 一种两人轮流进行的游戏，目标是让对方无法出招。
8. **第8章: 智能优化**
- **8.1 模拟退火算法**
- **物理退火过程和Metropolis准则**: 介绍模拟退火算法的基础原理。
- **模拟退火算法概述**: 通过模拟固体退火过程来求解优化问题。
- **应用举例**: 如TSP旅行商问题的求解。
- **8.2 遗传算法**
- **生物的进化与遗传**: 介绍遗传算法的生物学背景。
- **遗传算法概述**: 通过模拟自然选择过程来求解优化问题。
- **遗传算法关键参数**: 种群大小、交叉概率、变异概率等。
- **遗传算法应用举例**: 如求解连续函数的全局最小值。
- **8.3 粒子群优化算法**
- **粒子群算法的基本结构**: 通过模拟鸟群觅食行为来求解优化问题。
- **粒子群算法的关键参数**: 粒子速度更新规则等。
- **应用举例**: 如多目标优化问题的求解。
- **8.4 人工神经网络**
- **神经网络模型**: 通过模拟人脑神经元的工作原理来构建模型。
- **神经网络学习规则**: 如反向传播算法等。
9. **第9章: 并行算法简介**
- **9.1 基本概念**
- **并行计算机系统结构模型**: SIMD、MIMD等。
- **并行计算性能评价**: 如加速比、效率等。
- **9.2 并行算法设计**
- **SIMD共享存储模型**: 单指令多数据流。
- **SIMD互连网络模型**: 用于大规模并行处理。
- **MIMD共享存储模型**: 多指令多数据流。
- **MIMD异步通信模型**: 适用于分布式计算环境。
- **9.3 并行程序开发**
- **并行程序设计概念**: 并行编程的基本思想。
- **共享存储系统并行编程**: 如OpenMP等。
- **分布存储系统并行编程**: 如MPI等。
**总结**:
以上是《计算机常用算法与程序设计教程》这本书中涉及的主要知识点概览。这些知识点不仅涵盖了基本的数据结构和算法，还深入探讨了高级算法和优化技术。对于准备参加ACM程序设计大赛的学生而言，掌握这些知识是非常重要的。通过阅读本书并结合实际编程实践，可以显著提高解决复杂问题的能力，并在比赛中取得更好的成绩。
