算法竞赛入门经典的笔记(22)

>我来写笔记

按有用程度 按页码先后 最新笔记

  • 灵魂机器

    灵魂机器 (彪悍的人生不需要解释)

    作者没有考虑到正着数和倒着数的问题,而是一概处理为倒数,而如果k是偶数,那输出应该反过来。书中的代码是有问题的,这里给出修正后的代码: /代码内容已省略/ 82页的程序也同样有此问题,改法相同。

    2013-04-10 15:45

  • MathxH

    MathxH

    建立表达式树的方法就是每一次找到最后计算的运算符,然后递归建树。“最后计算”的运算符是在括号外的,优先级最低的运算符。如果有多个,根据结合性来选择:左结合(加,减,乘,除),右结合(乘方)。 并查集的精妙之处在于用树来表示集合。 最短路径:DIJKSTRA算法,Floyd算法。

    2013-06-01 13:48

  • MathxH

    MathxH

    设a,b,c为任意整数。若方程ax+by=c的一组整数解为(x0,y0),则它的任意整数解都可以写成(x0+kb',y0-ka'),其中a'=a/gcd(a,b),b'=b/gcd(a,b),k取任意整数。 设a,b,c为任意整数,g=gcd(a,b),方程ax+by=g的一组解是(x0,y0),则当c是g的倍数时ax+by=c的一组解是(x0c/g,y0c/g);当c不是g的倍数时无整数解。 数学归纳法是一种利用递归的思想的证明方法。如果要讨论的对象具有某种递归性质(如正整数),可以考虑用...

    2013-06-01 13:37

  • MathxH

    MathxH

    动态规划需要理解“状态”,“状态转移”,“最优子结构”,“重叠子问题”等概念。 动态规划是一种思维手段,本身不是什么特定的算法。 动态规划的核心是状态和状态转移方程。 状态转移方程的计算方法: 1.递归计算(时间效率低,原因在于重复计算。) 2.递推计算(递推的关键是边界和计算顺序。在大多数情况下,递推法的时间复杂度为:状态总数*每个状态的决策个数*决策时间。) 3.记忆化搜索(不必事先确定...

    2013-06-01 13:24

  • MathxH

    MathxH

    分治: 1.划分问题:把问题划分成子问题 2.递归求解:递归解决子问题 3.合并问题:合并子问题的解得到原问题解 归并排序: 1.划分问题:把序列分成元素个数尽量相等的两半 2.把两半元素分别排序 3.把两个有序表合并成一个 快速排序: 1.划分问题:把数组的各个元素重排后分成左右两部分,使得左边的任意元素都小于或等于右边的任意元素 2.递归求解:把左右两边部分分别排序 3.合并问题:不用合并,因为此时数...

    2013-06-01 12:39

  • MathxH

    MathxH

    暴力求解,一般用在排列枚举之类的方面。 如果某问题的解可以由多个步骤得到,而每个步骤可以由若干种选择,且可以使用递归枚举,工作方式可以用解答树来描述。 关于子集生成: 子集生成算法:给定一个集合,枚举它所有可能的子集。一般有3种思路:增量构造,位向量法,二进制法。 用二进制表示子集,其中从右往左第i位(从0开始编号)表示元素i是否在集合中(1表示“在”,0表示“不在”)。当用二进制法表示子...

    2013-06-01 12:24

  • MathxH

    MathxH

    对比测试,随机生成大规模随机数据量。考虑srand , time,rand rand生成闭区间的[0,RAND_MAX],RAND_MAX至少为32767. 二叉树的一般三种遍历:先序遍历,中序遍历,后序遍历如下: PreOrder(T)=T的根节点 + PreOrder(T的左子树) + PreOrder(T的右子树) InOrder(T)= InOrder(T的左子树) + T的根节点 + InOrder(T的右子树) PostOrder(T)=PostOrder(T的左子树) + PostOrder(T的右子树)+ T的根节点 ...

    2013-06-01 12:10

  • MathxH

    MathxH

    基本思考方案: 有些题考虑建立常量表,打表的方式可能会更简单。 用状态变量来辅助字符串读入 对于大数高精度运算,请考虑数组存储大数,模拟手工计算。考虑万进制提高效率。 排序的话,数据规模小的话,冒泡排序很管用的,比快排好。快排有时候分割不好,速度很慢。stdlib.h中的qsort速度就很快。

    2013-06-01 11:51

  • MathxH

    MathxH

    为了方便使用,往往用typedef struct {域定义;}类型名;的方式定义一个新类型名。这样,就可以像原生数据类型一样使用这个自定义类型了。 建议用来判断某事物是否具有某种特殊性质的函数命名成“is_xxx”的形式。返回非0数为真,0为假。 编写函数时,尽量保证它能对任何合法参数都能得到正确结果,如若不然,应在显著位置标明函数的缺陷,以避免使用。编程时,合理的利用assert宏,将给调试带来很大的方便。(assert.h..

    2013-06-01 11:20

  • MathxH

    MathxH

    字符数组: 竖式问题: 题目: 找出所有形如abc*de(三位数乘以两位数)的算式,使得在完整的竖式中,所有数字都属于一个特定的数字集合。输入数字集合(相邻数字之间没有空格),输出所有竖式。每个竖式前应有编号,之后应有一个空行。最后输出解的总数。具体格式见样例输出(为了便于观察,竖式中的空格改用小数点显示,但你的程序应该输出空格,而非小数点)。 样例输入:2357 样例输出: <1> ..775 ...

    2013-06-01 10:46

<前页 1 2 3 后页>

笔记是你写在书页留白边上的内容;是你阅读中的批注、摘抄及随感。

笔记必须是自己所写,不欢迎转载。摘抄原文的部分应该进行特殊标明。

算法竞赛入门经典

>算法竞赛入门经典