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 }

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

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

热身

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

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

• 0.1 http://acm.zju.edu.cn/show_problem.php?pid=1001 A+B Problem

• 0.2 PKU 1000 A+B Problem
• 0.3 TOJ 1000 熟悉一下Online Judge的环境

起步

• 以下是一些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的题都是英文的，有些题难度可能不比上面一组高。但对新队员来说，理解题意本身可能是个难点。

编号 来源 题号 标题 评注

• 2.1 http://acm.zju.edu.cn/show_problem.php?pid=1048 Financial Management

只比A+B难一点

• 2.2 http://acm.zju.edu.cn/show_problem.php?pid=1045 HangOver 这一道和下面两道都是简单的计算

• 2.3 http://acm.zju.edu.cn/show_problem.php?pid=1049 I Think I need I boat

• 2.4 http://acm.zju.edu.cn/show_problem.php?pid=1813 Biker's Trip Odometer

• 2.5 http://acm.zju.edu.cn/show_problem.php?pid=1057 Undercut

• 2.6 http://acm.zju.edu.cn/show_problem.php?pid=1113 u Calculate e 没有输入，但要注意格式

• 2.7 http://acm.zju.edu.cn/show_problem.php?pid=1151 Word Reversal 简单的字符串处理

• 2.8 http://acm.zju.edu.cn/show_problem.php?pid=1195 Blowing Fuses 别看题有些长，但其实很简单

• 2.9 http://acm.zju.edu.cn/show_problem.php?pid=1755 Clay Bully

• 2.10 http://acm.zju.edu.cn/show_problem.php?pid=1760 Doubles

英文题（2）

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

编号 来源 题号 标题 评注

• 3.1 ZJU 1489 2^x mod n = 1

• 3.2 http://acm.zju.edu.cn/show_problem.php?pid=1712 Skew Binary

• 3.3 http://acm.zju.edu.cn/show_problem.php?pid=1016 Parencodings

• 3.4 http://acm.zju.edu.cn/show_problem.php?pid=1350 The Drunk Jailer

• 3.5 http://acm.zju.edu.cn/show_problem.php?pid=1051 A New Growth Industry 这三题可能比较繁琐，做的时候要仔细

• 3.6 http://acm.zju.edu.cn/show_problem.php?pid=1178 Booklet PrintingBook

• 3.7 http://acm.zju.edu.cn/show_problem.php?pid=1078 Palindrom Numbers

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++)与语言基础。 有些题目需要一些数学推算，但都不会超出你们的知识范围。 编号 来源 题号 标题 评注

• 5.1 http://acm.zju.edu.cn/show_problem.php?pid=1763 A Simple Question of Chemistry 极简单

• 5.2 http://acm.zju.edu.cn/show_problem.php?pid=1915 Above Average

极简单

• 5.3 http://acm.zju.edu.cn/show_problem.php?pid=2104 Let the Balloon Rise 极简单

• 5.4 http://acm.zju.edu.cn/show_problem.php?pid=2201 No Brainer 极简单

• 5.5 http://acm.zju.edu.cn/show_problem.php?pid=2208 To and Fro 极简单，只要读懂题

• 5.6 http://acm.zju.edu.cn/show_problem.php?pid=1797 Least Common Multiple 想一想如何有效率地求最大公约数和最小公倍数

• 5.7 http://acm.zju.edu.cn/show_problem.php?pid=1629 Counting Triangles

• 5.8 ZJU 2015 Number Sequence 注意数列的周期性

• 5.9 http://acm.zju.edu.cn/show_problem.php?pid=1657 Goldbach's Conjecture

• 5.10 http://acm.zju.edu.cn/show_problem.php?pid=1871 Steps

• 5.11 http://acm.zju.edu.cn/show_problem.php?pid=1858 Soundex

• 5.12 http://acm.zju.edu.cn/show_problem.php?pid=1622 Switch

• 5.13 http://acm.zju.edu.cn/show_problem.php?pid=1160 Biorhythms

• 5.14 TOJ 1022 数制转换 要注意如何读入数据

• 5.15 http://acm.zju.edu.cn/show_problem.php?pid=1010 数素数

注意质数判定的效率

高精度运算练习

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

• 6.1 ZJU 1272 Numerically Speaking 有样例程序

• 6.2 http://acm.zju.edu.cn/show_problem.php?pid=1292 Integer Inquiry 高精度加法

• 6.3 http://acm.zju.edu.cn/show_problem.php?pid=1205 Martian Addition

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

• 6.4 http://acm.zju.edu.cn/show_problem.php?pid=1073 Round and Round We Go 高精度乘法

• 6.5 ZJU 1086 Octal Fractions 高精和数制转换

• 6.6 http://acm.zju.edu.cn/show_problem.php?pid=1154 Niven Numbers

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

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

高精度加法,以及比较

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

模拟类题目专项练习

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

• 6.1 ZJU 1072 Microprocessor Simulation
• 6.2 ZJU 1208 Roll the Die!

• 6.3 http://acm.zju.edu.cn/show_problem.php?pid=1710 The Snail

• 6.4 ZJU 1723 Board Silly

• 6.5 http://acm.zju.edu.cn/show_problem.php?pid=1737 Unreliable Message

• 6.6 ZJU 1824 Maze Traversal

• 6.7 ZJU 1834 AutoFish

• 6.8 ZJU 1862 Mine Sweeper
• 6.9 ZJU 2240

Run Length Encoding

新一组练习

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

• 7.1 ZJU 1068 P,MTHBGWB
• 7.2 ZJU 1146 LC-Display

• 7.3 http://acm.zju.edu.cn/show_problem.php?pid=1243 URLs

• 7.4 http://acm.zju.edu.cn/show_problem.php?pid=1115 Digital Roots

• 7.5 http://acm.zju.edu.cn/show_problem.php?pid=1180 Self Numbers

• 7.6 http://acm.zju.edu.cn/show_problem.php?pid=1337 Pi

• 7.7 http://acm.zju.edu.cn/show_problem.php?pid=1312 Prime Cuts

• 7.8 ZJU 1326 M*A*S*H 建议用链表做

• 7.9 http://acm.zju.edu.cn/show_problem.php?pid=1494 Climbing Worm

• 7.10 http://acm.zju.edu.cn/show_problem.php?pid=1577 GCD & LCM

• 7.11 ZJU 2122 A Flea on a Chessboard
• 7.12 ZJU 1628 Diamond
• 7.13 ZJU 1630 Die
• 7.14 ZJU 1517 Grandpa's Rubik Cube

• 7.15 http://acm.zju.edu.cn/show_problem.php?pid=1161 Gone Fishing 贪心经典

字符串处理

• 8.1 ZJU 1099

HTML

• 8.2 ZJU 1318 Table
• 8.3 ZJU 1116 A Well-Formed Problem
• 8.4 ZJU 1324 Unix ls 用C语言的用scanf读数据

• 8.5 http://acm.zju.edu.cn/show_problem.php?pid=1295 Reverse Text

• 8.6 http://acm.zju.edu.cn/show_problem.php?pid=1392 The Hardest Problem Ever

• 8.7 ZJU 1325 Palindromes
• 8.8 ZJU 1404 Oil Pipeline

• 8.9 http://acm.zju.edu.cn/show_problem.php?pid=1884 WERTYU

Group 9:

• 9.1 http://acm.zju.edu.cn/show_problem.php?pid=2388 Beat the Spread!

• 9.2 http://acm.zju.edu.cn/show_problem.php?pid=2376 Ants 努力得猜吧

• 9.3 ZJU 2358 Sum of Factorials 注意0的阶乘

• 9.4 http://acm.zju.edu.cn/show_problem.php?pid=2345 Gold Coins

• 9.5 http://acm.zju.edu.cn/show_problem.php?pid=2321 Filling Out the Team

• 9.6 ZJU 2397 Tian Ji -- The Horse Racing 经典贪心
• 9.7 ZJU 2316 Matrix Multiplication 线性代数，加组合数学
• 9.8 ZJU 2301 Color the Ball 离散化坐标

• 9.9 ZJU 2330 A^{B == B}A? 高数题

• 9.10 ZJU 2329 AB Circle
• 9.11 ZJU 2313 Chinese Girls' Amusement

Group 10:

• 10.1 http://acm.zju.edu.cn/show_problem.php?pid=2417 Lowest Bit

• 10.2 http://acm.zju.edu.cn/show_problem.php?pid=2405 Specialized Four-Digit Numbers

• 10.3 http://acm.zju.edu.cn/show_problem.php?pid=2481 Unique Ascending Array

• 10.4 http://acm.zju.edu.cn/show_problem.php?pid=2478 Encoding

• 10.5 http://acm.zju.edu.cn/show_problem.php?pid=2421 Recaman's Sequence

• 10.6 http://acm.zju.edu.cn/show_problem.php?pid=2416 Open the Lock

• 10.7 http://acm.zju.edu.cn/show_problem.php?pid=2482 IP Address

• 10.8 ZJU 2401 Zipper
• 10.9 ZJU 2480 Simplest Task in Windows

• 10.10 http://acm.zju.edu.cn/show_problem.php?pid=2476 Total Amount

• 10.11 ZJU 2256 Mincost 贪心
• 10.12 ZJU 2258 Number Sequence II 构造

专题１：递归运用初步

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

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

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

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

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

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

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

这两题涉及N的全组合

• Z1.3 TOJ 1032 等式问题

Group 11: 搜索初步

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

• 11.0 http://acm.zju.edu.cn/show_problem.php?pid=2416 Open the Lock 广度优先。

• 11.1 http://acm.zju.edu.cn/show_problem.php?pid=1091 Knight Moves 最简单的广度优先搜索问题，但包括了这类方法的所有要素。

• 11.2 http://acm.zju.edu.cn/show_problem.php?pid=1005 Jugs 典型的广度优先

• 11.3 http://acm.zju.edu.cn/show_problem.php?pid=1649 Rescue 广度优先在迷宫问题中的应用

• 11.4 http://acm.zju.edu.cn/show_problem.php?pid=1002 Fire Net 这些都是可以运用深度优先的题目。有些需要很好的剪枝。

• 11.5 http://acm.zju.edu.cn/show_problem.php?pid=1003 Crashing Balloon

• 11.6 http://acm.zju.edu.cn/show_problem.php?pid=1004 Anagrams by Stack

Group 12: 深度优先搜索

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

• 12.0 PKU 1256 Anagram

生成不重复排列

• 12.1 http://acm.zju.edu.cn/show_problem.php?pid=1711 Sum It Up 生成不重复组合

• 12.2 http://acm.zju.edu.cn/show_problem.php?pid=2412 Farm Irrigation 初步

• 12.3 http://acm.zju.edu.cn/show_problem.php?pid=1694 Shredding Company

• 12.4 http://acm.zju.edu.cn/show_problem.php?pid=1457 Prime Ring Problem

• 12.5 http://acm.zju.edu.cn/show_problem.php?pid=1204 Additive equations

• 12.6 http://acm.zju.edu.cn/show_problem.php?pid=2192 T-shirt Gumbo 进阶,有序搜索与剪枝

• 12.7 http://acm.zju.edu.cn/show_problem.php?pid=1909 Square

• 12.8 http://acm.zju.edu.cn/show_problem.php?pid=1987 Vase Collection 状态压缩＋DFS

• 12.9 http://acm.zju.edu.cn/show_problem.php?pid=1937 Addition Chains DFS+剪枝

• 12.10 http://acm.zju.edu.cn/show_problem.php?pid=1984 Genetic Code DFS+打表

• 12.11 ZJU 2110 Tempter of the Bone

• 12.12 http://acm.zju.edu.cn/show_problem.php?pid=1179 Finding Rectangles DFS+剪枝，输出比较麻烦

• 12.13 ZJU 1411 Anniversary

• 12.14 http://acm.zju.edu.cn/show_problem.php?pid=1008 Gnome Tetravex

• 12.15 http://acm.zju.edu.cn/show_problem.php?pid=1499 Increasing Sequences

• 12.16 http://acm.zju.edu.cn/show_problem.php?pid=1516 zju1516参考答案

Group 13: 广度优先搜索

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

• 13.0 http://acm.zju.edu.cn/show_problem.php?pid=1438 Asteroids! 三维迷宫

• 13.1 http://acm.zju.edu.cn/show_problem.php?pid=2050 Flip Game BFS+状态压缩

• 13.2 http://acm.zju.edu.cn/show_problem.php?pid=2081 Mission Impossible 最短路径＋BFS+DFS

• 13.3 http://acm.zju.edu.cn/show_problem.php?pid=1310 Robot 进阶,最短路径＋BFS

• 13.4 http://acm.zju.edu.cn/show_problem.php?pid=1671 Walking Ant 最短路径 Floyd

• 13.5 http://acm.zju.edu.cn/show_problem.php?pid=1940 Dungeon Master 最短路径 BFS 三维迷宫

• 13.6 http://acm.zju.edu.cn/show_problem.php?pid=1103 Hike on a Graph 最短路径 BFS 状态表示

• 13.7 ZJU 1358 Moving Object Recognition
• 13.8 ZJU 1217 Eight 难题,注意状态的表示与哈希
• 13.9 ZJU 1227 Free Candies
• 13.10 ZJU 1505 Solitaire

• 13.11 http://acm.zju.edu.cn/show_problem.php?pid=1361 Holedox Moving 状态压缩＋BFS 最短路径

• 13.12 http://acm.zju.edu.cn/show_problem.php?pid=1084 Channel Allocation 图顶点着色

• 13.13 http://acm.hdu.edu.cn/showproblem.php?pid=1043 Eight 八数码问题 hdu 1043参考答案

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

• 14.0 http://acm.zju.edu.cn/show_problem.php?pid=1221 Risk 多源最短路径问题 Floyd-Warshall算法

• 14.1 http://acm.zju.edu.cn/show_problem.php?pid=2165 Red and Black 基于网格的连通性分析

• 14.2 http://acm.zju.edu.cn/show_problem.php?pid=1589 Professor John 传递闭包，也可以用DFS

• 14.3 http://acm.zju.edu.cn/show_problem.php?pid=1085 Alien Security 有向图最短路径与割点

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）

• 16.0 http://acm.zju.edu.cn/show_problem.php?pid=1406 Jungle Roads

• 16.1 ZJU 1203 Swordfish
• 16.2 ZJU 1542 Network

• 16.3 http://acm.zju.edu.cn/show_problem.php?pid=1586 QS Network 要注意节点权值

• 16.4 ZJU 1372 Networking 要注意重复边

• 16.5 http://acm.zju.edu.cn/show_problem.php?pid=1914 Arctic Network 想想为什么可以用最小生成树?

• 16.6 ZJU 2158 Truck History 想想如何转化为最小生成树?
• 16.7 ZJU 2048 High Ways 基于连通分量的最小生成树
• 16.8 ZJU 1718 Building a Space Station
• 16.9 PKU 1258 Agri-Net

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参考答案