enigmahuang/acm-icpc-algorithm

ACM/ICPC algorithm problems, mainly solved on POJ and HDU(HDOZ).

请先读我

这里有什么

这里有七个文件夹，按创建的时间顺序分别是图论、数学类、计算几何、数据结构、字符串、搜索枚举和博弈论。这是我自2013年10月4日至2014年9月8日这一年的时间内，自己准备ACM/ICPC竞赛所做的算法相关的题目。每个文件夹内，一般还有子文件夹，因为这八个大方向底下还有子专题。在每一个子专题文件夹里，一定会有一些源代码和一份PDF“题解”，部分文件夹内还会有我下载的NOI国家集训队论文。这些源代码全部是在在线测评系统上已经测试通过的，而题解基本上也是我自己写的。

题解内容

题解涉及的主要方面和内容，大多是参考《ACM国际大学生程序设计竞赛 算法与实现》一书的，加上自己准备的博弈论，以及复习性质的深搜和广搜。我默认读到这些题解的诸君有基本的深搜、广搜、组合数学、模拟、字符串等知识。数学类的题目内涉及一些线性代数和矩阵的知识。 题解里所选用的题目，大多数是POJ的，一部分是HDOJ(HDU)的，极少数是ZOJ的。HDOJ我使用的时间比较晚，因为早期一直只在POJ上做题，后来发现有些题POJ上我没有找到，就去HDOJ上做了。对于有些题目，如果我看到在POJ或者HDOJ上同时出现的，一般都会注明。无论POJ还是HDOJ，都有Discuss区，这是一个很有用的地方。如果有时候反复WA/TLE/别的错误，或者没有想法，我推荐去Discuss区看一下。每一道题的题解，我都会有中文的题目描述、输入输出要求以及我对这道题的解答思路。

中文的题目描述不是原题翻译，而是我抽取出所有有关的要素，甚至有时候可能直接抽象出问题的本质。之所以这么做，是因为我在高中阶段的时候英语不是太好，看到一堆英文题目会头皮发麻，所以想着自己做的时候顺便做了译题的工作，让看到这份文档的人能更关注解题本身。附带一提，如果原题是中文出的，那么我会指明，而不再赘述。

输入输出要求一般会指明数据需要以什么样的格式被读入，以及答案以什么样的格式被输出。对于题目中使用的字母表示的变量，我一般会保持不变，但偶尔会改。所有输出数据的范围一般会给出，如果有没有给出的情况，建议查看原题。有时候输入输出要求比较奇特，无法用简短的文字说明时，我也会建议去阅读原题。

关于题解，虽然我也经常参考网上的题解来做题（我认为，这个学习过程是有必要的），但是我一般不会照抄网上的题解，而尽量用自己的话简单明了地重新说明一次。这可能有点重复发明轮子的感觉，但是我觉得这样有助于我清晰地整理思路。遇上某一些比较长的题解，或者完整的讲解，我一般会附上参考的网页或者相关的论文。如果某一道题我没有做出来，那么也会说明，并且尽可能地附上一些参考源。

关于源代码

• 这里面的源代码，全部是已经在OJ上测试通过了的。所以，可以直接被拿去刷AC数。但是我强烈不建议这么做，因为这样是毫无意义的。但是，我不反对在Debug不出来的时候用这些题解来作为参考样例进行对拍，因为我自己偶尔也会这么做。
• 源代码主要有三种文件类型：lpr文件、c文件和cpp文件
  • lpr文件是我在Lazarus上用Pascal语言写的代码，在 Lazarus 1.0.6 + Pree Pascal Compiler 2.6.0 的环境下可以编译通过。但是，一般来说，Lazarus编译需要一个.lpi文件作为工程信息文件，所以如果要使用，建议在Lazarus中通过【文件】-【新建】-【Project】-【程序】来新建一个空白程序，然后把代码复制粘贴进去。我不建议在OJ上做题的时候，使用Delphi或者其他的Pascal语言编译器，因为这可能引入一些其他不必要的问题。需要提醒的是，HDOJ上的Pascal语言用的编译器是Borland Delphi 7.0的编译器，和Free Pascal之间有一定的区别，这个请参阅HDOJ的FAQ页面。
  • c文件和cpp文件是我从Pascal转到C/C++以后写的代码，使用的编辑编译环境是 Dev-C++ 5.4.1 + MinGW GCC 4.7.2 32bit （有时会在更高的编译器版本下编译但在这个环境下都测试过可以正常编译调试和运行）。需要先在此道歉的是，虽然我是一个强迫症患者，但是由于Dev-C++的缩进设置我以前没有正确设置，所以可能出现了Tab和空格混杂造成的缩进混乱，而我并没有足够的时间去订正这些问题。
• 我的代码风格及需要注意的问题。首先接上一段，c和cpp文件中可能会出现一些Tab和空格混杂造成的缩进混乱。我原本的标准是，C/C++每一个代码块缩进四个英文空格，Pasacl每一个代码块缩进两个英文空格。并且，C/C++中的{}和Pascal中的begin/end，都会另起一行，然后再增加新的缩进。对于for和if语句，在其后接语句只有一句的情况下，我一般不会分行。由于习惯了从文件输入调试然后输出到文件，所以我一般：在Pascal代码中一般会在头部定义OnDebug或者OnDbg常量，当此值为false时就不会进行文件读写；在C/C++代码中会有两句freopen，将stdin和stdout重定向到输入输出文件。需要提交的时候，请改掉、注释掉或者删掉这些语句，否则会导致出错。

其他

我不是一个计算机科学或者信息科学专业的学生，我是一个计算数学专业的学生。大一的时候学算法准备比赛，是因为以前中学的时候就已经一直在搞竞赛。现在大二的课程和大一的成绩让我觉得我大二没有什么时间继续搞竞赛了，所以我把这些东西全部都打包上来了。

实际上，还有不少的专题，我并没有去做相关的题，因为时间或者难度问题被我跳过了。所以，这里的题总体而言没有太高级的题目。至于剩下那些内容，比如动态规划这一大块专题，我也不知道什么时候会去碰了。

衷心希望这些题解和代码能够为各位ACMer提供一点帮助，祝各位在ACM的道路上越走越远！