[18考研]复试中“机试”是什么？应该如何准备？

本文转载了一部分王道机试指南中的内容

提醒：这篇文章是新手向，适合 跨专业/没接触过ACM/不懂机试 的同学，ACM大神可以直接关掉不看了。

什么是机试

众所周知，机试是计算机考研当中非常重要的一个环节。在越来越注重实践动手能力的今天，越来越多的知名高校在计算机研究生招生考试当中采用了机试的形式，通过这种考试手段来考察考生分析问题并利用计算机程序解决问题的能力。通过机试，可以考察一个考生从实际问题当中抽象得出数学模型的能力，利用所学的计算机专业知识对该模型进行分析求解的能力，以及利用计算机编程语言，结合数据结构和算法真正解决该实际问题的能力。

所以，我们在准备机试的过程中要特别注意以下几个方面：

1、如何将一个实际问题抽象成数学问题。例如将高速公路网抽象成带权图，这就是一种简单的、直接的抽象。

2、如何将我们所学的计算机专业知识运用到解决抽象出来的数学模型上去。这就要求我们在脑子里事先熟知一些常用的数据结构和算法，再结合模型求解的要求，很快地选择合适的编程思想来完成算法的设计。甚至可以利用一些经典算法特征，加入一些自己的优化，使得编写的程序更优雅、更高效（当然这是建立在充分理解经典算法的基础上）。

3、如何将我们为解决该数学模型所设计的算法编写成一个能被计算机真正执行的计算机程序。我们认为，关于这个能力的定义有三个层次：1）会编写（默写）一些经典算法的程序代码。2）能够将自己的想法或设计的算法转换为程序代码。3）能够使得自己编写的程序在大量的、多种多样的、极限的测试数据面前依旧正常完成功能（程序的健壮性）。我们在准备机试的训练过程中，就要依次经历这三个层次，从而最后能够在实际考试当中取得理想的成绩。

机试的形式

而 ACM 是目前所有高校机试所采取的唯一形式，因此提早开始准备和练习，对于一个完全没有接触过 ACM 的计算机考研人来说，是必须的！

绝大部分机试所采用的形式，归结起来可以概括为：得到题目后，在计算机上完成作答，由计算机评判并实时告知结果的考试过程。

机试考试中的问题往往有五部分组成。

首先是问题描述，问题描述描述该问题的题面，题面或直接告知考生所要解决的数学问题或给出一个生活中的实际案例，以待考生自己从中抽象出所要解决的数学模型。

第二是输入格式，约定计算机将要给出的输入数据是以怎样的顺序和格式向程序输入的，更重要的是它将给出输入数据中各个数据的数据范围，我们通过这些给出的数据范围确定数据的规模，为我们设计算法提供重要依据。

第三是输出格式，明确考生将要编写的程序将以怎样的顺序和格式向输出输出题面所要求的答案。

第四第五部分即输入、输出数据举例（Sample）。好的 Sample 不仅能为考生提供一组简单的测试用例，同时也能明确题意，为题面描述不清或有歧义的地方做适当的补充。

另外我们也要特别注意，题目中给定的两个重要参数：1、时间限制。2、空间限制。这两个重要的参数限定了考生提交的程序在输出答案之前所能耗费的时间和空间。

我们来看一个典型的题目描述，从而了解机试题的问题形式。

题目选自HDOJ 1231

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 35982    Accepted Submission(s): 16246

Problem Description

给定K个整数的序列{ N1, N2, ..., NK }，其任意连续子序列可表示为{ Ni, Ni+1, ..., Nj }，其中 1