版本2和3间的区别
于2008-08-05 17:04:10修订的的版本2
大小: 21029
编辑: 66
备注:
于2009-04-08 13:42:03修订的的版本3
大小: 21112
编辑: 218
备注:
删除的内容标记成这样。 加入的内容标记成这样。
行号 291: 行号 291:
 * 12.16 http://acm.zju.edu.cn/show_problem.php?pid=1516 ["zju1516参考答案"]

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

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

TableOfContents

新手须知

  • 目的与注意事项

先做几组难度最低的题,这些题都来自浙大(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:

专题1:递归运用初步

  • 在同济练习题前20道题中,有三题至今没有被加入我们的练习题中。其中有两题1002(全排列问题)和1017(石子归并),运用递归思想可以很方便的解决它们。
    • 对递归的介绍,请看这里。 递归的应用总是和深度优先搜索联系到一起。这里先请看两篇有关的文章,一篇中文的,一篇英文的。 看了这两篇文章,应当对深度优先的基本概念有些了解。请结合样例程序仔细体会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 稳定婚姻,延迟认可算法

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

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