Category Archives: 结构之法

漫谈穷举和枚举的关系和异同

说道枚举,大家可能想到的都是枚举变量,枚举类型。前两天,不知为何就把他的一个好兄弟联想到了一起,他的好兄弟是谁?——哈哈,那就是穷举。

那他们到底有什么关系呢?让我们一言以蔽之:

  • 【枚举】一般是指一种构造类型——枚举(类型)。这个好多人和他等同于穷举(法),但我在写本篇日志的时候,搜索到的很少说枚举法,但也有不少将两者都视为同一种方法。
  • 【穷举】是一种算法,也可以说是一种思想

Continue reading

并查集补充:Ackerman函数及C语言实现(递归方法和非递归方法)

第二天数据结构讲的是并查集,这里是补充并查集的补充内容:Ackerman函数。想看并查集内容,请移步→谈并查集思想——基础入门

【1.Ackerman函数定义】

  • 当两个连续函数都趋于无穷时,我们常用洛必达法则来比较它们趋向无穷的快慢。
  • 函数的阶越高,它趋向无穷的速度就越快。
  • 在定义在正整数域上的函数中,n!趋向于正无穷的速度非常快,所以在算法设计中如果出现这样的时间复杂度就太糟糕了。logn趋向无穷的速度则非常慢。

Continue reading

POJ3468 A Simple Problem with Integers——线段树的建立,插入,修改,查询

这两天效率很低的说,从昨晚快睡觉时候开始看这个题,看会儿这个看会儿那个。心思乱飞~,按理说午睡应该按时睡,结果快到两点才睡T。T,果断睡得沉沉的,醒来难受(╯﹏╰)。切入正题,开始。

A Simple Problem with Integers

给定Q(1 ≤ Q≤ 100,000)个数A1,A2… AQ,以及可能多次进行的两个操作:

  1. 对某个区间Ai … Aj的每个数都加n(n可变);
  2. 求某个区间Ai … Aj的数的和。

Continue reading

POJ3264 Balanced Lineup——用链表实现一维线段树的建立,插入,查询

今天下午考试,一个程序也没写出来,尽管结果在意料之中,但是还是有些开心,毕竟我看到的两道题,都有思路。一个是做函数的求导,另一个是Crossing River。不管了,正题开始,要看数组解本题的,以及具体的输入输出样例的,请移步→POJ3264——用数组实现一维线段树的建立,插入,查询

POJ 3264 Balanced Lineup

给定Q(1 ≤ Q≤ 200,000)个数A1,A2… AQ,,多次求任一区间Ai–Aj中最大数和最小数的差。

Continue reading

POJ3264 Balanced Lineup——用数组实现一维线段树的建立,插入,查询

话说,明天考试,想想明天考试内容。什么也不会<破涕为笑>,我还说什么好,好好给程序写注释吧<破涕为笑>233333333……..。也可移步,看POJ3264——用数组实现一维线段树的建立,插入,查询

POJ 3264 Balanced Lineup

给定Q(1 ≤ Q≤ 200,000)个数A1,A2… AQ,,多次求任一区间Ai–Aj中最大数和最小数的差。

Continue reading