ACM培训计划

这个计划是网络上找的,我自己做过的,我都了http。无论我AC过的,没AC的,都欢迎和我讨论。ymc

[url=http://acm.ecust.edu.cn/training/articles/]http://acm.ecust.edu.cn/training/articles/[/url]

新手须知

先做几组难度最低的题,这些题都来自浙大(ZJU)、北大(PKU)和同济(TOJ)的网站。 有些题的解法几乎一眼可以看出,但对C,C++基本语句的熟悉还是很有好处的。练习这些题还有以下目的:

  1. 了解竞赛题的形式
  2. 熟悉如何在训练系统中提交做对的题目
    • 请所有的新队员认真完成以下各题。如果做题遇到困难,如题意难以理解、不知如何着手或不知错在哪里,不要气馁,可以请教别的队员,也可请教教练。我们会尽力帮助你完成这几组中每一道题。但不要复制别人的程序,即便参考了别人的程序,也要亲自再完成一遍。而且不建议过多参考别人程序,这样会消弱训练的效果,也减少了思考的乐趣。
    • 有些队员可能觉得某些题太简单,但我们还是建议将它们都做掉。因为题目虽然简单,但是再简单的题目都不能保证一次做对,而做错题的各种原因如题意理解错误,格式错误等你都会碰到。了解这些原因对减少错误率很有好处。
  1. 做题前请了解一些规范:
    1. main函数应为int型,最后return 0 ,即:

   1 int main()
   2 {
   3 ...
   4    return 0;
   5 }

这样做是因为避免有些编译器报错。

热身

再次提醒:做对后别忘提交到训练系统.

三道都是A+B,而且有样例程序。请自己做一遍,不要拷。

起步

编号 来源 题号 标题 评注

(直接推出每个位置数字的公式和递推公式也可以,但效果并不比前一种方法更有效,而且难度较大)

英文题(1)

编号 来源 题号 标题 评注

只比A+B难一点

英文题(2)

编号 来源 题号 标题 评注

TOJ前20题中剩余题

编号 来源 题号 标题 评注

基础题继续练习

再补充一些适于基本功练习的题目,供大家继续打好C(C++)与语言基础。 有些题目需要一些数学推算,但都不会超出你们的知识范围。 编号 来源 题号 标题 评注

极简单

注意质数判定的效率

高精度运算练习

高精度运算也是基本功之一。 以下各题都牵涉到高精度运算,许多涉及数制转换。但也需注意其它方面。 做题时注意模块化。做完这些题后,你会发现很多功能可以重用。

高精度加法,但不是十进制

高精和数制转换,注意,长度题目中未明确给定。如果设固定长数组,先设50.如果运行时溢出再往上加。

高精度加法,以及比较

模拟类题目专项练习

所谓模拟类题目,就是那些题目详细描述了完成某一过程的步骤,你只须严格按照要求模拟这一过程即可。 这类题目通常不需要很复杂的算法设计,但有些题十分繁琐,稍不小心就会出错。另外,对题意的准确把握也是关键,特别是这些步骤的细节方面,一定要完全搞清楚,不能自己乱猜。 下面的一些模拟类题目都是比较繁琐的,大家做它们时一定要细心,且有足够的耐心。

Run Length Encoding

新一组练习

这一组题目较综合,难度不一。

字符串处理

HTML

Group 9:

Group 10:

专题1:递归运用初步

以下是一些问题的样例程序: 整数拆分 组合问题 全排列 八皇后问题

下面是一些有关它们的练习。 关于这方面的题目很多,我们会不断添加。

Group Z1:递归和深度优先搜索初步

先做几道简单的试试。估计问题不少。

这两题涉及N的全组合

Group 11: 搜索初步

深度优先搜索和广度优先搜索是属于常用的搜索技术。前者用到递归,后者涉及队列。 深度优先搜索对于解决某些问题并不一定是最好的,但很容易实现,有时也十分有效,它的难点在于如何剪枝优化。出现在递归初步中的题目可以算是深搜的一种。 广度优先搜索技术的结构相对固定,但节点的判重也是个难点。由于时间效率的原因,广度优先搜索运用得更为广泛。 下面是关于它们的一些练习。

Group 12: 深度优先搜索

下面是关于深度优先搜索(DFS)的一些练习。

生成不重复排列

Group 13: 广度优先搜索

下面是关于广度优先搜索(BFS)的一些练习。

Group 14: 图--遍历(Graph Traversal)、传递闭包(Transitive Closure)

Group 15: 图--拓扑排序(Topological Sort)、关节点(Articulation Point)

Group 16: 图--最小生成树(Minimum Spanning Tree)

Group 17: 图--最短路径(Shortest Path)

Group 18: 图--回路问题(Euler Path & Hamilton Tour)

Group 19: 图--二部图匹配(Bipartite Matching)

Group 20: 图--网络流(Network Flow)

Group 21: 图--差分约束(Difference Constraints)

Group 22: 图--其它

Group 23: 数据结构

ACM培训计划 (2009-04-16 19:50:16由74编辑)