BIG NUMBER 算法竞赛入门经典 刘汝佳

高一入坑数竞必备书单高一是数竞的入门阶段，对于刚入坑的同学来说，选择合适的书籍是非常重要的。

下面是我为高一数竞入门推荐的必备书单。

1.《算法竞赛入门经典》这本书是数竞入门的经典教材，由刘汝佳编写。

它详细介绍了算法竞赛的基本知识和常用算法，包括排序、搜索、图论等内容。

书中的例题和习题很有代表性，对初学者非常友好。

阅读完这本书，你将对数竞的基本知识有一个全面的了解。

2.《算法竞赛入门经典训练指南》这本书是《算法竞赛入门经典》的配套训练指南，由刘汝佳和冯宇航编写。

它包含了大量的例题和习题，涵盖了各个难度级别。

通过做这些题目，你可以巩固和深入理解书中所讲的知识，并提高自己的编程能力。

3.《挑战程序设计竞赛》这本书是日本的一本经典教材，由吉田和弥和寺田康平合著。

它介绍了更多的算法和高级技巧，包括动态规划、贪心算法、网络流等。

书中的例题和习题很有挑战性，适合有一定基础的同学进一步提高自己的竞赛水平。

4.《算法导论》这本书是计算机科学领域的经典教材，由Thomas H.Cormen等人合著。

它系统地介绍了算法设计和分析的基本原理，包括分治法、动态规划、贪心算法等。

虽然这本书的内容相对较为深入，但对于对算法有浓厚兴趣的同学来说，是一本非常值得阅读的书籍。

5.《挑战程序设计竞赛2》这本书是《挑战程序设计竞赛》的续篇，由吉田和弥和寺田康平合著。

它进一步扩展了算法和高级技巧的内容，包括数据结构、字符串算法、几何算法等。

书中的例题和习题更加复杂和有趣，对于想要挑战自己的同学来说是一本很好的选择。

6.《算法笔记》这本书是浙江大学计算机学院的一本教材，由胡凡、曾磊等人合著。

它以清晰简洁的语言介绍了算法的基本概念和常用算法，适合初学者入门。

书中的例题和习题有助于巩固所学知识，并提供了一些思考和扩展的方向。

以上是我为高一入坑数竞推荐的必备书单。

当然，每个人的学习方式和兴趣爱好都不同，选择适合自己的书籍很重要。

希望这些建议对你有所帮助，祝你在数竞的道路上取得好成绩！。

数学伴你学答案数学，作为一门重要的学科，是我们日常生活中不可或缺的一部分。

无论是做生意、计算货币、解决计划或者是进行科学研究，数学都是必不可少的工具。

然而，毫不吹捧地说，数学并不是每个人都喜欢的学科。

一些学生，甚至有点害怕数学，认为它难以理解，甚至认为数学是“毒瘤”。

事实上，并非每一个人都可以像Einstein那样，将数学视为“最高坦白的哲学。

”但是，通过改变对数学的态度和方法，每个人都可以掌握数学的基础知识，并理解如何将这些理论应用于日常生活。

通过良好的数学学习方法和技巧的掌握，我们可以大大提高我们的数学理解和能力，让我们一起来探讨一下。

首先，最重要的是改变对数学的态度。

虽然很多人觉得数学很难，但事实上数学不难。

数学对于我们的生活是至关重要的。

数学是解决现实问题的重要工具，有很多真实的例子可以证明这点。

因此我们必须对数学学习充满信心，不能放弃，要对它抱乐观的态度。

其次，要学会用正确的方法来学习数学。

除了学习数学概念和理论外，我们可以结合一些实践来掌握数学技巧。

刘汝佳的“算法竞赛入门经典”或Skiena的“算法设计和分析基础原理”等教材，在学习数字理论，组合数学，图论等数学相关技巧时是非常有用的资料，它们可以帮助我们学习数学知识，同时也培养了我们的思维和解决问题的能力。

此外，我们还可以选择一些在线数学课程或视频资源，如卡内基梅隆大学的公开课、麻省理工学院的OCW 等，它们可以帮助我们更有效地学习数学知识。

最后，我们可以通过练习来提高我们的数学能力。

做数学题并不是在考试前好好准备，或者仅在学校课堂上做作业，而是一个日常学习过程。

我们可以通过刷题来提高我们的技能，并确保我们对数学知识的掌握程度。

可以使用一些教辅资料或者在线平台，如Khan Academy、真题人生、知乎问题广场等，帮助我们更好地进行练习和复习。

总的来说，数学对我们的生活至关重要，并且学习数学可以提高我们的思维解决问题的能力，从而更好地适应现代复杂的社会格局。

信息学奥赛（NOIP）必看经典书目汇总！最近有人在群里问，为什么没有关于NOIP的复习资料推荐贴！今天小编就来整理汇总一下大神们极力推荐的复习资料！（欢迎大家查漏补缺）•基础篇1、《全国青少年信息学奥林匹克分区联赛初赛培训教材》（推荐指数：4颗星）曹文，吴涛编著，知识点大杂烩，部分内容由学生撰写，但是对初赛知识点的覆盖还是做得相当不错的。

语言是pascal的。

2、谭浩强老先生写的《C语言程序设计（第三版）》（推荐指数：5颗星）针对零基础学C语言的筒子，这本书是必推的。

3、《骗分导论》（推荐指数：5颗星）参加NOIP必看之经典4、《全国信息学奥林匹克联赛培训教程（一）》（推荐指数：5颗星）传说中的黄书。

吴文虎，王建德著，系统地介绍了计算机的基础知识和利用Pascal语言进行程序设计的方法5、《全国青少年信息学奥林匹克联赛模拟训练试卷精选》王建德著，传说中的红书。

6、《算法竞赛入门经典》（推荐指数：5颗星）刘汝佳著，算法必看经典。

7、《算法竞赛入门经典:训练指南》（推荐指数：5颗星）刘汝佳著，《算法竞赛入门经典》的重要补充•提高篇1、《算法导论》（推荐指数：5颗星）这是OI学习的必备教材。

2、《算法艺术与信息学竞赛》（推荐指数：5颗星）刘汝佳著，传说中的黑书。

3、《学习指导》（推荐指数：5颗星）刘汝佳著，《算法艺术与信息学竞赛》的辅导书。

（PS：仅可在网上搜到，格式为PDF）。

4、《奥赛经典》（推荐指数：5颗星）有难度，但是很厚重。

5、《2016版高中信息学竞赛历年真题解析红宝书》（推荐指数：5颗星）历年真题，这是绝对不能遗失的存在。

必须要做！。

Linear Cellular AutomataA biologist is experimenting with DNA modification of bacterial colonies being grown in a linear array of culture dishes. By changing the DNA, he is able ``program" the bacteria to respond to the population density of the neighboring dishes. Population is measured on a four point scale (from 0 to 3. The DNA information is represented as an array DNA, indexed from 0 to 9, of population density values and is interpreted as follows:In any given culture dish, let K be the sum of that culture dish's density and the densities of the dish immediately to the left and the dish immediately to the right. Then, by the next day, that dish will have a population density of DNA[K].The dish at the far left of the line is considered to have a left neighbor with population density 0.The dish at the far right of the line is considered to have a right neighbor with population density 0. Now, clearly, some DNA programs cause all the bacteria to die off (e.g., [0,0,0,0,0,0,0,0,0,0]. Others result in immediate population explosions (e.g.,[3,3,3,3,3,3,3,3,3,3]. The biologist is interested in how some of the less obvious intermediate DNA programs might behave.Write a program to simulate the culture growth in a line of 40 dishes, assuming that dish 20 starts with a population density of 1 and all other dishes start with a population density of 0.InputThe input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.For each input set your program will read in the DNA program (10 integer values on one line.OutputFor each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.For each input set it should print the densities of the 40 dishes for each of the next 50 days. Each day's printout should occupy one line of 40 characters. Each dish is represented by a single character on that line. Zero population densities are to be printed as the character ` '. Population density 1 will be printed as the character `.'. Population density 2 will be printed as the character `x'. Population density 3 will be printed as the character `W'.Sample Input10 1 2 0 1 3 3 2 3 0Sample Outputbbbbbbbbbbbbbbbbbbb.bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb.xbx.bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb.bb.bb.bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb.........bbbbbbbbbbbbbbbbbbbbbbbbbbbbbb.xbbbbbbbx.bbbbbbbbbbbbbbbbbbbbbbbbbbbb.bbxbbbbbxbb.bbbbbbbbbbbbbbbbbbbbbbbbbb...xxxbbbxxx...bbbbbbbbbbbbbbbbbbbbbbbb.xb.WW.xbx.WW.bx.bbbbbbbbbbbbbbbbbbbbbb.bbb.xxWb.bWxx.bbb.bbbbbbbbbbbNote: Whe show only the first ten lines of output (the total number of lines must be 50 and the spaces have been replaced with the character "b" for ease of reading. The actual output file will use the ASCII-space character, not "b".。

#《算法竞赛入门经典》勘误关于勘误¶下面的勘误很多来自于热心读者，再次向他们表示衷心的感谢！我并不清楚这些错误实际是在哪个版本中改正过来的，所以麻烦大家都看一下。

有发现新错误的欢迎大家在留言中指出，谢谢！一些一般性的问题¶运算符<?、>?已经被废弃，请用min、max代替（代码仓库中的代码已更新，g++ 4.6.2下编译通过）重大错误¶p24. 最后一行，“然后让max=INF,而min=-INF”应该是“然后让max=-INF, 而min=INF”。

(感谢imxivid）p43. 最后，判断s[i..j]是否为回文串的方法也不难写出：int ok = 1; for(k = i; i<=j; i++)应该为for(k = i; k<=j; k++)(感谢imxivid）p45. 第七行和第九行i-j+1应为i+j+1。

修改后：1. {2. for (j = 0; i - j >= 0 && i + j < m; j++)3. {4. if (s[i - j] != s[i + j]) break;5. if (j*2+1 > max) { max = j*2+1; x = p[i - j]; y = p[i + j];}6. }7. for (j = 0;i - j >= 0 && i + j + 1 < m; j++) 8. { 9. if (s[i - j] != s[i + j + 1]) break; 10. if (j*2+2 > max) 11. {max = j*2+2; x = p[i - j]; y = p[i + j + 1]; } 12. } 13. }p53. 例题4-1. 组合数. 输入非负整数n和m，这里的n和m写反了。

应是“输入非负整数m和n”。

算法竞赛-入门经典-作者刘汝佳.doc第1部分语言篇第1章程序设计入门学习目标☑熟悉C语言程序的编译和运行☑学会编程计算并输出常见的算术表达式的结果☑掌握整数和浮点数的含义和输出方法☑掌握数学函数的使用方法☑初步了解变量的含义☑掌握整数和浮点数变量的声明方法☑掌握整数和浮点数变量的读入方法☑掌握变量交换的三变量法☑理解算法竞赛中的程序三步曲：输入、计算、输出☑记住算法竞赛的目标及其对程序的要求计算机速度快，很适合做计算和逻辑判断工作。

本章首先介绍顺序结构程序设计，其基本思路是：把需要计算机完成的工作分成若干个步骤，然后依次让计算机执行。

注意这里的“依次”二字——步骤之间是有先后顺序的。

这部分的重点在于计算。

接下来介绍分支结构程序设计，用到了逻辑判断，根据不同情况执行不同语句。

本章内容不复杂，但是不容忽视。

注意：编程不是看会的，也不是听会的，而是练会的，所以应尽量在计算机旁阅读本书，以便把书中的程序输入到计算机中进行调试，顺便再做做上机练习。

千万不要图快——如果没有足够的时间用来实践，那么学得快，忘得也快。

（为帮助没有分值的朋友能下载，特此修改文档，以免上传不了）1.1 算术表达式计算机的“本职”工作是计算，因此下面先从算术运算入手，看看如何用计算机进行复杂的计算。

程序1-1 计算并输出1+2的值#include<stdio.h>int main(){printf("%d\n", 1+2);return 0;}算法竞赛入门经典这是一段简单的程序，用于计算1+2的值，并把结果输出到屏幕。

如果你不知道如何编译并运行这段程序，可阅读附录或向指导教师求助。

即使你不明白上述程序除了“1+2”之外的其他内容，仍然可以进行以下探索：试着把“1+2”改成其他东西，而不要去修改那些并不明白的代码——它们看上去工作情况良好。

下面让我们做4个实验：实验1：修改程序1-1，输出3-4的结果实验2：修改程序1-1，输出5×6的结果实验3：修改程序1-1，输出8÷4的结果实验4：修改程序1-1，输出8÷5的结果直接把“1+2”替换成“3+4”即可顺利解决实验1，但读者很快就会发现：无法在键盘上找到乘号和除号。

ACM-ICPC比赛随想——刘汝佳刘汝佳，1982年12月生，毕业于重庆外国语学校，清华大学计算机科学与技术系2005级研究生。

高二时创立“信息学初学者之家”网站（OIBH），高三入选IOI2001国家集训队。

大学一年级时获ACM/ICPC世界总决赛银牌（世界第四），IOI2002/03/04国家集训队指导老师。

曾与黄亮合作出版了《算法艺术与信息学竞赛》丛书，自2002年至今为科学委员会学生委员，在命题方面和辅导学生方面成绩突出，同时兼任NOI网站总监。

从第一次听说ACM/ICPC到现在，已经有快七个年头了。

最开始因好奇而关注，而现在因了解而关注——关注比赛，更关注参加比赛的人。

ACM/ICPC是一个五味瓶。

没有接触过它的人不会知道其中的酸甜苦辣，而一旦置身其中，每个选手都会对它产生一种特殊的感情，时间越长，这种感情也越复杂、越浓烈。

感情来源于对算法与题目的喜爱，来源于对成功的向往和失败的恐惧，来源于各种选择与放弃中的徘徊与摇摆不定，来源于程序世界与现实生活的巨大差异，也来源于通往理想的曲折道路——探索其中时的无助和艰辛。

等到退役的那一天，回过头来再看当时的自己，相信每位选手都会发现自己的很多方面成熟了许多——远不只是编程能力和算法功底。

以前我觉得这是比赛的副产品，而现在我认为这才是比赛的主要目的，至少对于选手自己是如此。

虽然我从心里喜欢这个比赛，但我并不鼓励每个人参加。

并不是每个人在每个时期都适合参加这个比赛，且适合的人选也并不代表一定能取得好成绩——比赛场上是没有“一定”的，任何一个选手都必须有勇气承担风险，就像所有其他有潜在回报的事一样。

另一方面，对于所有下定决心参加比赛的选手，我鼓励他坚持到底，因为只有这样才会受到真正的磨练。

在“参加”与“不参加”的岔路口上，大多数选手被两个问题所困绕。

第一个是“我能获奖么？奖会给我带来什么好处？”，第二个是“抛开荣誉，从比赛中学到的东西值得我花费这么多时间吗？”。

数学基础(版本2009)刘汝佳例1. 同构计数•一个竞赛图是这样的有向图–任两个不同的点u、v之间有且只有一条边–不存在自环•用P表示对竞赛图顶点的一个置换。

当任两个不同顶点u、v间直接相连的边的方向与顶点P(u)、P(v)间的一样时，称该图在置换P下同构•对给定的置换P，我们想知道对多少种竞赛图在置换P下同构分析•先把置换它分解成为循环, 首先证明长度为L的偶循环将导致无解–对于点i1, 记P(i k)=i k+1, 假设i1和i L/2+1的边方向为i1->i L/2+1, 那么有i2->i L/2+2, i3->i L/2+3, …, i L/2+1->i1, 和假设矛盾!•假设确定其中k条独立边后其他边也会确定, 则答案为2k•考虑两类边: 循环内边和循环间边.分析•循环内顶点的关系–定了i 1和i j 之间的关系, i k 与i (k+j-2) mod n+1之间的关系也被确定下来了, 因此只需要确定i 1和i 2, i 3, …, i (L-1)/2+1这(L-1)/2对顶点的关系•不同循环间顶点的关系–设循环为(i 1,i 2,…,i L1)和(j 1,j 2,…,j L2), 通过类似分析得只需要确定gcd(L1, L2)对关系即可分析•最后答案为2k1+k2•其中k1=sum{(L-1)/2}, k2=sum{gcd(L1, L2)}•可以用二分法加速求幂例2. 图形变换•平面上有n个点需要依次进行m个变换处理•规则有4种, 分别把(x0,y)变为–平移M(x, y): (x0+x, y0+y)–缩放Z(L): (Lx0, Ly0)–翻转F(0): (x0, -y0); F(1): (-x0, y0)–旋转R(a): a为正时逆时针, 离原点距离不变, 旋转a度•给n(<=106)个点和m(<=106)条指令•求所有指令完成后每个点的坐标分析•如果直接模拟, 每次需要O(n)的时间, 一共O(nm), 无法承受•把点(x0, y)写成列向量[x, y]T, 则后3种变换可以都可以写成矩阵–缩放P’= Z * P, Z = [L 0; 0 L]–翻转P’= F * P, F = [1 0; 0 -1]或[-1 0; 0 1]–旋转P’= R * P, R = [cosa–sina; sina cosa]•可是无法实现平移, 怎么办呢?分析•修改表达方式, 令P = [x 0, y 0, 1]T , 则四种变换的矩阵M, Z, F, R 分别为100001,00001001x L M y Z L ⎡⎤⎡⎤⎢⎥⎢⎥==⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦100100010010001001F −⎡⎤⎡⎤⎢⎥⎢⎥=−⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦或cos sin 0,sin cos 0001a a R a a −⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦分析•只需要先计算所有变换矩阵的乘积A, 然后对于每个点, P’= A * P•注意: 矩阵乘法不满足交换律, 因此需要按照输入顺序进行乘法•每次矩阵乘法需要33=27次乘法, 则计算A一共需要27m次乘法, 对所有点变换需要27n 次乘法, 一共27(n+m)次例3. 染色方案•N*M(N<=10100, M<=5)的格子纸，每个格子被填上黑色或者白色。