版本2和8间的区别 (跳过第6版)
⇤ ← 于2008-08-05 17:04:10修订的的版本2 →
大小: 21029
编辑: 66
备注:
← 于2009-04-11 10:33:00修订的的版本8 → ⇥
大小: 21354
编辑: 128
备注:
删除的内容标记成这样。 加入的内容标记成这样。
行号 9: 行号 9:
[[TableOfContents]] <<TableOfContents>>
行号 291: 行号 291:
 * 12.16 http://acm.zju.edu.cn/show_problem.php?pid=1516 [[zju1516参考答案]]
行号 386: 行号 387:

== Group 23: 数据结构 ==
* 23.0 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1610 Count the Colors [[zju1610 参考答案]]
* 23.1 http://acm.hdu.edu.cn/showproblem.php?pid=1828 Picture [[hud 1828参考答案]]		 

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

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

目录

  1. 新手须知
  2. 热身
  3. 起步
  4. 英文题（1）
  5. 英文题（2）
  6. TOJ前20题中剩余题
  7. 基础题继续练习
  8. 高精度运算练习
  9. 模拟类题目专项练习
  10. 新一组练习
  11. 字符串处理
  12. Group 9:
  13. Group 10:
  14. 专题１：递归运用初步
  15. Group Z1:递归和深度优先搜索初步
  16. Group 11: 搜索初步
  17. Group 12: 深度优先搜索
  18. Group 13: 广度优先搜索
  19. Group 14: 图--遍历(Graph Traversal)、传递闭包（Transitive Closure）
  20. Group 15: 图--拓扑排序（Topological Sort）、关节点（Articulation Point）
  21. Group 16: 图--最小生成树（Minimum Spanning Tree）
  22. Group 17: 图--最短路径（Shortest Path）
  23. Group 18: 图--回路问题（Euler Path & Hamilton Tour）
  24. Group 19: 图--二部图匹配（Bipartite Matching）
  25. Group 20: 图--网络流（Network Flow）
  26. Group 21: 图--差分约束（Difference Constraints）
  27. Group 22: 图--其它
  28. Group 23: 数据结构

新手须知

  • 目的与注意事项

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

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

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

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

  • b. 为了便于核对，请在代码开头加上可以表明题目的注释，如：//ZJU1001; /*PKU1002 */等

热身

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

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

起步

  • 以下是一些TOJ上的题目，作为起步练习很不错。题目是中文的，但其它形式和比赛题型一样。要注意输出格式。有些题目对格式交待不是很清楚，但这并不是说你可以随意增加空格和空行。遇到这种情况，根据样例输出自行判断。一般行尾没有多余空格。

编号 来源 题号 标题 评注

  • 1.1 TOJ 1001 排版题.输出排列成菱形的字母
  • 1.2 TOJ 1003 排版题.输出三角形的字符
  • 1.3 TOJ 1006 敲七
  • 1.4 TOJ 1007 Step.如何得到输入数据的结束
  • 1.5 TOJ 1008 扬辉三角
  • 1.6 TOJ 1009 蛇行矩阵 可以直接在2维数组中填数.

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

  • 1.7 TOJ 1015 行编辑器 简单的字符串处理
  • 1.8 TOJ 1019 输入三个自然数

英文题（1）

  • 以下是ZJU上的题目，ZJU的题都是英文的，有些题难度可能不比上面一组高。但对新队员来说，理解题意本身可能是个难点。

编号 来源 题号 标题 评注

只比A+B难一点

英文题（2）

  • 下面这些题可能稍微难一些，但与上面一组难度上并没有本质区别。只要仔细想想，应当不难做出。

编号 来源 题号 标题 评注

TOJ前20题中剩余题

  • TOJ前20题都是基础题，在第一组练习中已经做了一部分，剩下的这一部分难度肯定比第一组大，但与上一组难度差不多。有几道题涉及更知识，在这依旧被剔除，留着以后做。

编号 来源 题号 标题 评注

  • 4.1 TOJ 1005 母牛生小牛 类似Fibonacci数列，但有区别
  • 4.2 TOJ 1012 约瑟夫问题
  • 4.3 TOJ 1013 去尾问题
  • 4.4 TOJ 1014 阶乘结果末尾有多少零？ 这两题涉及到一些数学推导，可能难度较大
  • 4.5 TOJ 1016 请求N！左边第二位的数字
  • 4.6 TOJ 1018 编制一个乘法运算的程序
  • 4.7 TOJ 1020 字符串编辑

基础题继续练习

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

极简单

注意质数判定的效率

高精度运算练习

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

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

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

  • 6.7 ZJU 1210 Reciprocals 高精度除法，同时注意输出格式要求
  • 6.8 ZJU 1962 How Many Fibs?

高精度加法,以及比较

  • 6.9 ZJU 2017 Simple Arithmetics 涉高精加，减，乘，且格式处理较繁
  • 6.10 ZJU 2241 Fractran 表示一个大数不仅可以用各位数，也可以用它的各因子。这题就是一例。

模拟类题目专项练习

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

Run Length Encoding

新一组练习

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

字符串处理

  • 8.1 ZJU 1099

HTML

Group 9:

Group 10:

专题１：递归运用初步

  • 在同济练习题前２０道题中，有三题至今没有被加入我们的练习题中。其中有两题１００２（全排列问题）和１０１７（石子归并），运用递归思想可以很方便的解决它们。
    • 对递归的介绍，请看这里。 递归的应用总是和深度优先搜索联系到一起。这里先请看两篇有关的文章，一篇中文的，一篇英文的。 看了这两篇文章，应当对深度优先的基本概念有些了解。请结合样例程序仔细体会8皇后问题的解法。这是很经典的深度优先搜索问题。

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

  • 理解这些程序若有困难，我们会详细讲解它们。理解后，请自己再编一遍。

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

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

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

  • Z1.1 TOJ 1002 全排列问题
  • Z1.2 TOJ 1017 石子归并

这两题涉及N的全组合

  • Z1.3 TOJ 1032 等式问题

Group 11: 搜索初步

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

Group 12: 深度优先搜索

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

  • 12.0 PKU 1256 Anagram

生成不重复排列

Group 13: 广度优先搜索

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

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

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

  • 15.0 ZJU 1060 Sorting It All Out
  • 15.1 ZJU 1119 SPF
  • 15.2 ZJU 1311 Network

Group 16: 图--最小生成树（Minimum Spanning Tree）

Group 17: 图--最短路径（Shortest Path）

  • 17.0 ZJU 1053 FDNY to the Rescue!
  • 17.1 ZJU 1609 Equivalence

  • 17.2 http://acm.zju.edu.cn/show_problem.php?pid=1082 Stockbroker Grapevine

  • 17.3 ZJU 1655 Transport Goods 边权值有些特别

  • 17.4 http://acm.zju.edu.cn/show_problem.php?pid=1092 Arbitrage

  • 17.5 ZJU 1967 Fiber Network 想想如何利用Floyd三重循环?
  • 17.6 ZJU 1456 Minimum Transport Cost 有些难度的最短路径题
  • 17.7 ZJU 2008 Invitation Cards 带最小堆的Dijkstra
  • 17.8 ZJU 1765 Which Way Do I Go? 综合题，比较复杂
  • 17.9 ZJU 1232 Adventure of Super Mario

Group 18: 图--回路问题（Euler Path & Hamilton Tour）

  • 18.0 ZJU 1105 FatMouse's Tour

  • 18.1 ZJU 2016 Play on Words 可转化为判定欧拉路的存在性
  • 18.2 ZJU 1130 Ouroboros Snake 可以转化为欧拉路
  • 18.3 SCU 1286 First Love 可以转化为欧拉路

Group 19: 图--二部图匹配（Bipartite Matching）

  • 19.0 ZJU 1140 Courses
  • 19.1 ZJU 1137 Girls and Boys
  • 19.2 ZJU 1157 A Plug for UNIX

  • 19.3 http://acm.zju.edu.cn/show_problem.php?pid=1364 Machine Schedule

  • 19.4 ZJU 1197 Sorting Slides
  • 19.5 ZJU 1525 Air Raid
  • 19.6 ZJU 1059 What's In a Name
  • 19.7 ZJU 1516 Uncle Tom's Inherited Land
  • 19.8 ZJU 1654 Place the Robots
  • 19.9 ZJU 1509 Family

Group 20: 图--网络流（Network Flow）

  • 20.0 PKU 1273 Drainage Ditches 典型的网络最大流问题
  • 20.1 ZJU 1734 Power Network 可转化为网络最大流问题

Group 21: 图--差分约束（Difference Constraints）

  • 21.0 ZJU 1260 King
  • 21.1 ZJU 1420 Cashier Employment
  • 21.2 ZJU 1455 Schedule Problem
  • 21.3 ZJU 1508 Intervals

Group 22: 图--其它

  • 22.0 ZJU 1015 Fishing Net 弦图判定
  • 22.1 ZJU 1492 Maximum Clique 求最大团，经典NP hard
  • 22.2 ZJU 1576 Marriage is Stable 稳定婚姻，延迟认可算法

Group 23: 数据结构

* 23.0 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1610 Count the Colors zju1610 参考答案 * 23.1 http://acm.hdu.edu.cn/showproblem.php?pid=1828 Picture hud 1828参考答案

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

ch3n2k.com | Copyright (c) 2004-2020 czk.