斐波那契堆之Go实现

ACM

一个比二叉堆更高效的数据结构,但是实现起来非常复杂。本科的时候看《算法导论》的时候曾经研究过,不是很明白。今天终于对它有了一个比较清晰的了解。
enter description here

Basic Algorithms in Go

ACM

最近学Go,感觉挺不错的。闲来无事用它写了几种常用的基础算法。

快排

思想很简单,实现起来为了方便每次以left作为基准,也可以使用BFS来节省递归栈:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// QuickSort returns a sorted slice
func QuickSort(arr []int) {
if len(arr) <= 1 {
return
}
left, right := 0, len(arr)-1
for left < right {
if arr[left+1] > arr[left] {
arr[left+1], arr[right] = arr[right], arr[left+1]
right--
} else {
arr[left+1], arr[left] = arr[left], arr[left+1]
left++
}
}
QuickSort(arr[:left])
QuickSort(arr[left+1:])
}

ZOJ month contest D.Determinant and Matrix

ACM

Time Limit: 2 Seconds Memory Limit: 65536 KB

##Description
Recently, LBH is learning the curse linear algebra. Thus he is very interested in matrix and determinant now. In order to practice his ability of solving the problem of linear algebra, he just invent some problems by himself. Once the problems was create, he would solve it immediately. However, he meet a problem that was so hard that he couldn’t work out even though racked his brains. The problem was described as follow:

To a integer martix Mnn(aij), we define two function add(Mnn(aij))=Mnn(aij + 1) and sub(Mnn(aij))=Mnn(aij - 1) which were exactly like this:

FFT求快速卷积的思考

ACM

离散型卷积的定义是:$$y(n)=\sum_{m=0}^{n} x(m)h(n-m)$$

注意,h函数是反转的。

在Chipher Messages一题中,b串需要反转再与a串匹配。

比如说:

a串: 110110110,则:

b`串:1011<——这里才是原来b串的头。但是向上对应到a串时,已经是m-1这个位置了。所以说,小于m-1的卷积是没有意义的。

于是,base=m。整体匹配。

baylor 6622 Absurdistan Roads( NWERC Contest)

ACM

原题pdf:click here

##Description
The people of Absurdistan discovered how to build roads only last year. After the discovery, every city
decided to build their own road connecting their city with another city. Each newly built road can be
used in both directions.

Absurdistan is full of surprising coincidences. It took all N cities precisely one year to build their
roads. And even more surprisingly, in the end it was possible to travel from every city to every other
city using the newly built roads.