Monthly Archives: May 2010

记(福州)全国邀请赛

大二快要结束了,从我开始成为ACMer到现在已经快一年了。一年来我并没有非常系统的学过算法,水平也没有提高多少,仅仅是刷了一些水题而已。我就是这样懒散,时间一天一天的过去,很快我就要离开这支队伍了,我不是计算机科班的学生,甚至连相关专业都不是。作为一名土木工程专业的学生,编程与我的专业是没有多大关系的,花太多的时间学习编程简直就是不务正业。

从大一进入至诚学院我就知道,土木工程专业的课程很多也很难。说句心里话这个专业我并不是非常喜欢。

我不明白自己为什么那么懦弱,两年前应该是我第一次可以决定自己的将来的时候。高中是我曾经立志要成为一名软件工程师。可是填志愿那天我却选择了土木工程,没有什么其他原因,只是我的父母希望我读这个专业。

大一土木的课程并没有想象中的那么多,我还是有一些时间可以自学一些计算机专业的课程。

大约一年前的这个时间,学院决定开始做ACM这块,组织了一场选拔赛。然后是校赛。我希望自己可以多学一些,暑假就留在福州参加集训。所谓集训,不过是不断刷题而已。我确实是一个懒散的人,一个暑假我只做了150题而已,不过做题确实是提高编码能力的最佳途径,见效也很明显。

直到暑假结束,我的算法水平并没有多少提高。做题基本靠 模拟+优化。大二开始土木的课开始多了起来,每周有40多节,周六要画图,周日要作实验。整整2个月我几乎没写什么代码,直到软件工程系的第一次程序设计大赛。说实话,那次的题目真不是一般的水,如果现在做,我20分钟就可以把所有题目AC掉。

那次比赛让计算机专业的很多人都认识我了,那次也是我最后一次转专业的机会,只是我没有把握好。后面开始我做题才稍微努力了一些,有时间就做。随后学院对ACM也慢慢开始重视起来。

这次的邀请赛学院派了3支队伍参赛,我在2队,和两个软件工程专业的同学一组,虽然平时接触不是很多但配合起来还算默契。比赛还闹了点笑话:原本我们没有想过可以拿奖,所以队名就随便起了一个,2队叫“ZC_CaiNiao I”,3队叫“ZC_CaiNiao II”。结果那天RP暴涨。然后闭幕式的颁奖也就可想而知了。

比赛让我挺开心的,第一次参加现场赛,见识了很多大牛,也认识了一些新朋友。能和志同道合的朋友一起讨论问题是一件很开心的事。这次现场赛也让我觉得自己好像是一只井底之蛙,我不懂的实在太多了,CaiNiao这个队名其实是名副其实的,我们只是运气好而已。

当时坐在我前方的队伍是浙江理工大学的女队,后来她们拿了银牌和最佳女队,除了四道简单题他们还AC了一道矩阵相关的的题目,并且用时极少。这就是实力,我们的水平算什么。

马上就要大三了,我不知道我还可以做多久的ACMer,下学期也许是我最后能和我的队友一起比赛了。为了你们,为了学院,为了我的兴趣,我要再拼一次……

Read more »

FOJ 1906解题报告

Problem Description

There is a sequence that only consists of characters ‘/’ and ‘’. You should calculate the number of down sequences and up sequences respectively in the given sequence.
A down sequence is defined as follows:

1. “/” is a down sequence.
2. If S is a down sequence, then “S/” is also a down sequence.
3. Any other sequences are not a down sequences.

Read more »

HDU 3351解题报告

http://acm.hdu.edu.cn/showproblem.php?pid=3351

Problem Description

I’m out of stories. For years I’ve been writing stories, some rather silly, just to make simple problems look difficult and complex problems look easy. But, alas, not for this one.
You’re given a non empty string made in its entirety from opening and closing braces. Your task is to find the minimum number of “operations” needed to make the string stable. The definition for being stable is as follows:
1. An empty string is stable.
2. If S is stable, then {S} is also stable.
3. If S and T are both stable, then ST (the concatenation of the two) is also stable.

Read more »

快速排序(1)

快速排序

快速排序(以下简称快排)是一种排序算法,有C.A.R.Hoare所发展的,就如同他的名字一样,它的特点就是快。以平均效能来说,排序n个项目有O(n log n)次比较。在最差的效能下它需要O(n^2)次比较,所以它是一种不稳定排序法。

思路:

快排使用的分治(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。令其中一个子序列的元素小于另一个子序列,在对两个子序列采取同样递归操作。

(顺序排列)步骤为:

  1. 在数列中挑出一个元素作为"基准"(pivot)。
  2. 将比基准小的移到基准前面,比基准大的移到基准后面(相同的可以不必理会)。
  3. 递归(recursive)地对两个子序列排序。

Read more »

计数排序法

计数排序一般用于类似统计数组中元素出现次数。

条件:数组中的元素范围必须确定,如0~k。

基本思路:以被计数数组的元素值作为计数数组的索引(数组下标)对计数数组自增。

例题:统计输入的50个数据中出现最多的元素,元素范围在0~99。

Read more »

搭建GCC编译环境

编译器

MinGW:是GCC编译器的一个windows移植版本,也是类Unix操作系统下编写C/C++程序的首选。对于标准化方面一直做的不错.

代码编辑器

VIM:一个在类Unix系统下发展起来的全屏编辑器,它的前生就是大名鼎鼎的VI,当然现在也有windows版本。

1,安装MinGW编译器

官方网站:www.mingw.org

因为MinGW的官方网站已经不再直接提供下载,所以大家可以根据官方网站上的提示从http://sourceforge.net/project/showfiles.php?group_id=2435http://gd.tuwien.ac.at/gnu/mingw/?fisel=0-9,a-z,A-Z

......

Read more »

将VIM作为简易IDE

1.简介

ed编辑器是Unix上最古老的编辑器,最初由Unix之父Ken Thompson所编写,并应用了正则表达式。而VIM的前身VI正是基于ed的拓展ex上。

2.安装

安装有两种方法

方法一

首先大家先到http://www.vim.org/download.php下载一下几个文件

Runtime files               运行库
GUI executable            界面文件
PC translations            语言文件

然后一起解压这三个文件就可以了。

方法二

直接下载Self-installing executable文件进行安装。但我感觉这种方法太死板没有第一种的灵活,不喜欢。然后你还可以将vim/vim71地址加如path环境变量,这样就可以在dos下用gvim命令打开vim了。

2.配置

其实像VIM这种从Unix体系过来的东西,都会带有浓重的Unix色彩,比如,配置文件。所以,要让你的VIM变得更加强大那么一份好的配置文件是必不可少的。当然在刚才解压的vim/vim71文件夹下已经有两个作为范例的配置文件了,分别是 gvimrc_example.vim和vimrc_example.vim,根据你的使用进行选择,如果你使用的是Gvim那么可以使用gvimrc那个,将其中一个重命名为_vimrc或_gvimrc放到vim文件夹下就可以了(但是根据使用经验_gvim那个有些小问题,但_vimrc可以通用)。
但是系统提供的配置文件是非常简陋的,发挥DIY精神,我们应该写自己的配置文件。

以下是我的配置文件:

......

Read more »