一.动态规划

参考资料：

刘汝佳《算法艺术与信息学竞赛》

《算法导论》

推荐题目：

http://acm.pku.edu.cn/JudgeOnline/problem?id=1141

简单

http://acm.pku.edu.cn/JudgeOnline/problem?id=2288

中等，经典TSP问题

http://acm.pku.edu.cn/JudgeOnline/problem?id=2411

中等，状态压缩DP

http://acm.pku.edu.cn/JudgeOnline/problem?id=1112

中等

http://acm.pku.edu.cn/JudgeOnline/problem?id=1848

中等，树形DP。

可参考《算法艺术与信息学竞赛》动态规划一节的树状模型

http://acm.zju.edu.cn/show_problem.php?pid=1234

中等，《算法艺术与信息学竞赛》中的习题

http://acm.pku.edu.cn/JudgeOnline/problem?id=1947

中等，《算法艺术与信息学竞赛》中的习题

http://acm.pku.edu.cn/JudgeOnline/problem?id=1946

查看更多...

以下等式或者不等式均可以用数学归纳法予以证明！

1 + 3 + 5 + ... + (2n - 1) = n^2

1*2 + 2*3 + 3*4 + ... + n*(n + 1) = n*(n + 1)*(n + 2) / 3

1*1! + 2*2! + 3*3! + ... + n*n! = (n + 1)! - 1

1^2 + 2^2 + 3^2 + ... + n^2 = n*(n + 1)*(2n + 1) / 6

1^2 - 2^2 + 3^2 -... + (-1)^n * n^2 = (-1)^(n + 1) * n * (n + 1) / 2

2^2 + 4^2 + ... + (2n)^2 = 2n*(n+1)*(2n+1) / 3

1/2! + 2/3! + ... + n/(n+1)! = 1 - 1/(n+1)!

2^(n + 1) < 1 + (n + 1)2^n

1^3 + 2^3 + 3^3 + ... + n^3 = (n*(n + 1) / 2)^2

1/(2*4)+1*3/(2*4*6)+1*3*5/(2*4*6*8)+...+(1*3*5*...*(2n-1))/(2*4*6*...*(2n+2)) = 1/2 - (1*3*5*...*(2n+1))/

(2*4*6*...*(2n+2))

1/(2^2-1) + 1/(3^2-1) + .. + 1 / ((n+1)^2 - 1) = 3/4 - 1/(2*(n+1)) - 1/(2*(n+2))

1/2n <= 1*3*5*...*(2n-1) / (2*4*6*...*2n) <= 1 / sqrt(n+1)  n=1,2...

2^n >= n^2 , n=4, 5,...

2^n >= 2n + 1, n=3,4,...

r^0 + r^1 + ... + r^n < 1 / (1 - r), n>=0, 0<r<1

1*r^1 + 2*r^2 + ... + n*r^n < r / (1-r)^2, n>=1, 0<r<1

1/2^1 + 2/2^2 + 3/2^3 + ... + n /2^n < 2, n>=1

(a(1)*a(2)*...*a(2^n))^(1/2^n) <= (a(1) + a(2) + ... + a(2^n)) / 2^n, n = 1, 2, ... a(i)是正数 注:()用来标记下标

cos(x) + cos(2x) + ... + cos(nx) = cos((x/2)*(n+1))*sin(nx/2) / sin(x/2), 其中sin(x/2) != 0

1*sin(x) + 2*sin(2x) + ... + n*sin(nx) = sin((n+1)*x) / (4*sin(x/2)^2) - (n+1)cos((2n + 1)/2 * x) / (2 * sin(x/2))
其中sin(x/2) != 0

5^n - 1能被4整除

查看更多...

ACM社区 http://www.608088.com

同济大学的 Online Judge -http://acm.tongji.edu.cn/
浙江大学的 Online Judge -http://acm.zju.edu.cn/
北京大学的 Online Judge -http://acm.pku.edu.cn/
吉林大学的 Online Judge -http://acm.jlu.edu.cn/
四川大学的 Online Judge -http://cs.scu.edu.cn/acm
汕头大学的 Online Judge -http://acm.stu.edu.cn/
中科大的 Online Judge -http://acm.ustc.edu.cn/index.php
哈工大的 Online Judge -http://acm.hit.edu.cn/acm.php
西班牙的 Universidad de Valladolid -http://acm.uva.es/
俄罗斯乌拉尔大学 -http://acm.timus.ru/

入门三本：《数据结构与算法》（傅清祥，王晓东编著，我所见过的最好的算法教材）
程序设计导引及在线实践 作者: 李文新
ACM程序设计培训教程 吴昊
基础提高：
算法艺术与信息学竞赛 第二版 刘汝佳
算法设计与分析 王晓东
算法设计与试验题解 王晓东
科曼：《算法导论》
组合数学 第三版 冯舜玺 译
计算几何－算法设计与分析 周培德
国际信息学奥林匹克竞赛指导— — 实用算法的分析与程序设计 吴文虎 王建德
网络算法与复杂性理论 谢政 李建平
《Concrete Mathematics --- A Foundation For Computer Science》 Ronald L. Gr.........

一、语言是最重要的基本功 
          无论侧重于什么方面，只要是通过计算机程序去最终实现的竞赛，语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与JAVA。笔者首先说说JAVA，众所周知，作为面向对象的王牌语言，JAVA在大型工程的组织与安全性方面有着自己独特的优势，但是对于信息学比赛的具体场合，JAVA则显得不那么合适，它对于输入输出流的操作相比于C++要繁杂很多，更为重要的是JAVA程序的运行速度要比C++慢10倍以上，而竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽，这无疑对算法设计提出了更高的要求，是相当不利的。其实，笔者并不主张大家在这种场合过多地运用面向对象的程序设计思维，因为对于小程序来说这不但需要花费更多的时间去编写代码，也会降低程序的执行效率。
         接着说C和C++。许多现在参加讲座的同学还在上大一，C的基础知识刚刚学完，还没有接触过C++，其实在赛场上使用纯C的选手还是大有人在的，它们主要是看重了纯C在效率上的优势，所以这部分同学如果时间有限，并不需要急着去学习新的语言，只要提高了自己在算法设计上的造诣，纯C一样能发挥巨大的威力。
         而C++相对于C，在输入输出流上的封装大大方便了我们的操作，同时降低了出错的可能性，并且能够很好地实现标准流与文件流的切换，方便了调试的工作。如果有些同学比较在意这点，可以尝试C和C++的混编，毕竟仅仅学习C++的流操作还是不花什么时间的。
         C++的另一个支持来源于标准模版库（STL），库中提供的对于基本数据结构的统一接口操作和基本算法的实现可以缩减我们编写代码的长度，这可以节省一些时间。但是，与此相对的，使用STL要在效率上做出一些牺牲，对于输入规模很大的题目，有时候必须放弃STL，这意味着我们不能存在“有了STL就可以不去管基本算法的实现”的想法；另外，熟练和恰当地使用STL必须经过一定时间的积累，准确地了解各种操作的时间复杂度，切忌对STL中不熟悉的部分滥用，因为这其中蕴涵着许多初学者不易发现的陷阱。
         通过以上的分析，我们可以看出仅就信息学竞赛而言，对语言的掌握并不要求十分全面，但是对于经常用到的部分，必须十分熟练，不允许有半点不清楚的地方，下面我举个真实的例子来说明这个道理——即使是一点很细微的语言障碍，都有可能酿成错误：
         在去年清华的赛区上，有一个队在做F题的时候使用了cout和printf的混合输出，由于一个带缓冲一个不带，所以输出一长就混乱了。只是因为当时 
          judge 
          team中负责F题的人眼睛尖，看出答案没错只是顺序不对（答案有一页多，是所有题目中最长的一个输出），又看了看程序发现只是输出问题就给了个 
          Presentation error（格式错）。如果审题的人不是这样而是直接给一个 Wrong 
          Answer，相信这个队是很难查到自己错在什么地方的。 
          现在我们转入第二个方面的讨论，基础学科知识的积累。 
           二、以数学为主的基础知识十分重要 
 

查看更多...

对ACM竞赛的算法大概分了一下类，分成了数学、数据结构和算法三大块。

一 数学(Mathematics)

1 离散数学(Discrete Mathematics)

1.1 图论(Graph Theory)

图的遍历(Graph Traversal): DFS, BFS

最小生成树(Minimum Spanning Tree): Prim, Kruskal

最短路径(Shortest Path): Dijkstra, Floyd

传递闭包(Transitive Closure)

关节点(Articulation Point - UndiGraph)

拓扑排序(Topological Sort - AOV-Network)

关键路径(Critical Path - AOE-Network)

回路问题: 欧拉路(Euler Path), 汉密尔顿回路(Hamilton Tour)

差分约束(Difference Constraints): Bellman-Ford

二部图匹配(Bipartite Matching)

网络流(Network Flow)

...

1.2 组合数学(Combinatorics)

2 数论(Number Theory)

2.1 素数: GCD, LCM...

2.2 同余

3 计算几何(Computational Geometry)

线段相交, 多边形面积, 内点外点的判断, 凸包(Convex Hull), 重心(Bary Center)...

4 线性代数

矩阵(Matrix), 线性方程组(Linear Equations)...

5 概率论

6 初等数学与解析几何

7 高等数学

点积(Dot Product), 差积(Cross Product), 积分(Integral), 微分(Differential)...

二 数据结构(Data Structure)

1 线性结构

线性表(Linear List)

栈(Stack), 队列(Queue)

数组(Array), 串(String), 广义表(General List)

2 非线性结构

树(Tree)

堆(Heap)

图(Graph)

3 排序

3.1 插入排序

直接插入排序(Insert Sort) O(n^2)

折半插入排序(Binary Insert Sort)

希尔排序(Shell Sort)

3.2 交换排序

冒泡排序(Bubble Sort) O(n^2)

快速排序(Quick Sort)?? O(nlogn)

3.3 选择排序

直接选择排序(Select Sort) O(n^2)

锦标赛排序(Tournament Sort) O(nlogn)

堆排序(Heap Sort) O(nlogn)

3.4 归并排序(Merge Sort) O(nlogn)

3.5 基数排序(Radix Sort) O(d(n+radix))

4 查找

4.1 二分(Binary Search)

4.2 树型

二叉搜索树(Binary Search Tree)

平衡搜索树(AVL Tree)

并查集(Union-Find Set)

4.3 哈希(Hashing)

三 算法(Algorithm)

1 模拟算法

2 搜索算法

2.1 枚举搜索(Enumeration)

2.2 深度优先(Depth First Search)

2.3 广度优先(Breadth First Search)

2.4 启发式搜索(Heuristic Search)

3 以“相似或相同子问题”为核心的算法

3.1 递推

3.2 递归(Recursion)

3.3 贪心法(Greedy)

3.4 动态规划(Dynamic Programming)