ACM程序设计节课总结

1、浅谈ACM

刚进入大学时，我便对C++这门课程感到十分有兴趣，在上学期的C++程序设计课程中，我便迷上了这门语言，以及十分有个性的费老师，可能是有那么一点灵性吧，我入门的非常快，一开始放在农大OJ上的题目能非常快的做出来，在那时体会到了AC的快感。不过在我现在看来，那时的我还是太天真了，在大一上学期，我所学的只能算是C++这门编程语言的皮毛，可能连入门都不算，当时的自大在我现在看来就是无知，就像是学会了点气功就沾沾自喜，殊不知还有更高深奥妙的功法，将这门课的学习比作是学习武功真是再恰当不错了。所以为了让自己变得更强，我在大一下学期一咬牙，报了这门在学长学姐口中有些恐怖的课程，说实话，这门课程是真的有难度，不过难度是层层递进的，从最基础的STL算法到递归递推再到动态规划，是有一个逐渐上升的过程，老师布置在网上的题目有水题也有难题，都是有考验能力与增加做题量的用途。

2、ACM学习心得

ACM课程设计这门选修课本质上就是一个学习算法和思想的过程，不同的专题都有不同的学习方法，下面是我学习个个专题的心得体会。

2.1 STL专题

STL，即C++标准模板库，是我接触ACM的第一个知识，STL是C++标准程序库的核心，深刻影响了标准程序库的整体结构，STL由一些可适应不同需求的集合类（collection class），以及在这些数据集合上操作的算法（algorithm）构成。STL内的所有组件都由模板（template）构成，其元素可以是任意类型，STL是所有C++编译器和所有操作平台都支持的一种库，简单来说，就是使许多操作变得简单了许多，比如学STL之前，数组用的还是简单的一维二维数组，在定位与查找方面有诸多的不便，而STL中有迭代器，对于STL中的所有容器都提供获得迭代器的函数，能非常方便的定位到所想寻找的元素位置，以一个list为例

list l;

for(pos=l.begin();pos!=l.end();++pos{

…

}

在省略处便可输入寻找条件的代码，而在普通的数组中对于一些特殊的情况则难以实现。

Vector数组则非常方便的解决了定义一个数组时所要面对的要开的大小的问题，vector相当于一个动态的一维数组，可以随着填入的数据即时扩大容量，而且vector的元素可以是任意类型T，支持随机存取，若要使用vector，必须包含头文件#include ，相较于普通的一维数组，vector还有一个好处，vector可以使用size和capacity函数，能够返回动态数组的实际元素个数以及能容纳的元素最大数量。

Map/multimap容器，可以类似于一个动态的即时扩大容量的二维数组，使用平衡二叉树管理元素，元素包含两部分（key，value），key和value可以是任意类型，而使用map/multimap前必须包含头文件#include

而virtual judge上的《ACM程序设计》书中题目B遇到map马上就迎刃而解，下面是该题：

We all know that FatMouse doesn't speak English. But now he has to be prepared since our nation will join WTO soon. Thanks to Turing we have computers to help him.

Input Specification

Input consists of up to 100,005 dictionary entries, followed by a blank line, followed by a message of up to 100,005 words. Each dictionary entry is a line containing an English word, followed by a space and a FatMouse word. No FatMouse word appears more than once in the dictionary. The message is a sequence of words in the language of FatMouse, one word on each line. Each word in the input is a sequence of at most 10 lowercase letters.

Output Specification

Output is the message translated to English, one word per line. FatMouse words not in the dictionary should be translated as "eh".

这道题大致的意思就是输入翻译表，每行的左边单词是英语单词，每行右边的单词是一个fat mouse 语言，所以只要用map就可以解决这个翻译问题可以把fat mouse 语作为键值，对应的英语翻译作为元素值，主要问题是如何将输入翻译表和输出翻译分隔开，我用了两个getchar实现了这个操作，又因为防止每一行的首字母被吞做了一个make_ pair(b,e+a)的语句。所以设置了一个名为dictionary的map数组，输入由下列关键伪代码实现：

while(cin>>fat mouse语>>对应英语翻译)

{

d=getchar();

往dictionary中插入元素(make_pair(英语翻译,e+fatmouse语));

e=getchar();

if(e=='\n')break;

}

Set/multiset用法与map/multimap差不多，map容器是键-值对的集合，好比以人名为键的地址和电话号码。相反地，set容器只是单纯的键的集合。当我们想知道某位用户是否存在时，使用set容器是最合适的。

2.2 递归地推

一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系；如果可以找到前后过程之间的数量关系，能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。

递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。即把一个复杂的问题的求解，分解成了连续的若干步简单运算。

做完virtual judge上的递归递推这套练习后，还是有所心得的，做递推递归类的题目我觉得唯一的需要的是灵感和努力，灵感是因为做递推递归的练习时有时候要将题目与以前数学学过的思考题相结合，灵感便是指如何在看到题的几分钟里能够将题目解剖，取其主干然后与所认识的数学题目联系起来。努力指的是如果一时间内没办法想到以前见过的数学题目，那就想办法枚举出题目数据的前几项，然后找规律。这个过程肯定是枯燥且很难成功的。没什么特别好的办法，大概只能多看看题目了吧。