中科大2012年复试机试题详解

第一题

题目描述

字符串处理：从string.in文件里读入两个字符串，字符串除了数字还可能包括'-'、'E'、'e'、'.'，相加之后输出到文件string.out中，如果是浮点型，要求用科学计数法表示（最多保留10个有效数字）。

解题思路

本题用C++的输入输出比较难处理，用C语言中的scanf、printf进行处理，注意按照题目要求，去除指数表示中的底数部分小数点后多余的0。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


#include <iostream>
using namespace std;

int main(int argc, char *argv[]) {
  double a, b;
  char buf[128];
  FILE *infile = fopen("./string.in", "r");
  FILE *outfile = fopen("./string.out", "w");
  if (!infile || !outfile) exit(1);
  fscanf(infile, "%lf", &a);
  fscanf(infile, "%lf", &b);
  sprintf(buf, "%.10e", a+b);
  int i, j;
  for (i = 0; buf[i] != '\0'; i++)
    if (buf[i] == 'e')
      break;
  for (j = i-1; buf[j] == '0'; j--);
  for (int k = 0; k <= j; k++)
    fputc(buf[k], outfile);
  fputc('e', outfile);
  for (j = i+1; buf[j] != '\0'; j++)
    fputc(buf[j], outfile);
  return 0;
}

第二题

题目描述

最大公约数：从number.in文件中读入n个数，求出这n个数的最小值、最大值以及它们两的最大公约数，输出到文件number.out中。number.in 中第一行为n，接下来为n个大于零的整数。

输入示例:
3
4 8 6

输出示例:
4 8 4

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


#include <fstream>
#include <vector>
using namespace std;

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

int main(int argc, char *argv[]) {
  ifstream ifs("./number.in");
  ofstream ofs("./number.out");
  int n;
  ifs >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++)
    ifs >> a[i];
  int minVal, maxVal;
  minVal = maxVal = a[0];
  for (int i = 1; i < n; i++) {
    if (a[i] < minVal)
      minVal = a[i];
    if (a[i] > maxVal)
      maxVal = a[i];
  }
  ofs << minVal << " " << maxVal << " " << gcd(maxVal, minVal);
  return 0;
}

第三题

题目描述

任务调度：从task.in文件中读入任务调度序列，输出n个任务适合的一种调度方式到task.out中。每行第一个表示前序任务，括号中的任务为后序任务，只有在前序任务完成的情况下，后序任务才能开始。若后序为NULL则表示无后序任务。

输入示例:
Task0(Task1,Task2)
Task1(Task3)
Task2(NULL)
Task3(NULL)

输出示例:
Task0 Task1 Task3 Task2

解题思路

本题考察的是拓朴排序的代码实现，对于该算法不熟悉的请参考这篇文章。在这里用dfs和visit数组来实现拓朴排序。

本题另外一个难点在于处理给定的文件形式，我们用多个unordered_map来存储某个任务名字与对应结点号之间的映射关系。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70


#include <fstream>
#include <unordered_map>
#include <vector>
using namespace std;

unordered_map<string, int> idxMap;
unordered_map<int, string> nameMap;
unordered_map<int, vector<int>> adjMap;
vector<int> q;
int curIdx = 0;

void parseLine(const string &line) {
  string tmp;
  int i, j;
  for (i = 0; i < line.length(); i++)
    if (line[i] == '(')
      break;
  tmp = line.substr(0, i);
  if (!idxMap.count(tmp)) {
    nameMap[curIdx] = tmp;
    idxMap[tmp] = curIdx++;
  }
  int src = idxMap[tmp];
  for (j = ++i; j <= line.length(); j++) {
    if (line[j] == ',' || line[j] == ')') {
      tmp = line.substr(i, j - i);
      if (!idxMap.count(tmp)) {
        nameMap[curIdx] = tmp;
        idxMap[tmp] = curIdx++;
      }
      adjMap[src].push_back(idxMap[tmp]);
      i = ++j;
    }
  }
}

void dfs(vector<int> &vis, int src) {
  vis[src] = 1;
  for (int next : adjMap[src]) {
    if (next == -1)
      break;
    if (vis[next])
      continue;
    dfs(vis, next);
  }
  q.push_back(src);
}

int main(int argc, char *argv[]) {
  ifstream ifs("./task.in");
  ofstream ofs("./task.out");
  idxMap["NULL"] = -1;
  string line;
  while (getline(ifs, line)) {
    parseLine(line);
  }
  int size = curIdx;
  vector<int> vis(size, 0);
  for (int i = 0; i < size; i++) {
    if (vis[i])
      continue;
    dfs(vis, i);
  }
  for (int i = q.size() - 1; i >= 0; i--) {
    if (i != q.size()-1)
      ofs << " ";
    ofs << nameMap[q[i]];
  }
  return 0;
}

第四题

题目描述

火车票订购：火车经过X站，火车的最大载客人数为m，有n个订票请求，请求订购从a站到b站的k张票，若能满足订购要求则输出1，否则输出0。数据从ticket.in中输入，第一行有两个数字，分别是n，m。接下来有n行，每行三个数分别是a、b、k。结果输出到文件ticket.out中。

解题思路

用一个大数组来存储每一站的车上人数，在每一次运送乘客时先尝试是否有足够空位，如果有空位则将flag置为1，否则将flag置为0，如果尝试之后flag=1则可以搭载这波乘客。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


#include <fstream>
#include <map>
#include <memory.h>
using namespace std;

int main(int argc, char *argv[]) {
  ifstream ifs("./ticket.in");
  ofstream ofs("./ticket.out");
  int nums[10000];
  memset(nums, 0, 10000);
  int n, m;
  ifs >> n >> m;
  int a, b, c, flag;
  for (int i = 0; i < n; i++) {
    ifs >> a >> b >> c;
    flag = 1;
    for (int j = a; j < b; j++) {
      if (nums[j] + c > m) {
        flag = 0;
        break;
      }
    }
    if (flag) {
      for (int j = a; j < b; j++) {
        nums[j] += c;
      }
    }
    ofs << flag << endl;
  }
  return 0;
}

最短路径：有n个城市和m条道路（n < 1000, m < 10000），每条道路有不同的长度，请找到从起点s到终点t的最短距离，并且输出经过的城市的序号，如果有多条，输出字典序最小的那条；若从s到t没有路径，则输出“can't arrive”。从文件road.in中读入数据，第一行有四个数，分别为n、m、s、t。接下来有m行，每行三个数，分别为两个城市的序号和相互之间的距离，将结果输出结果到文件road.out中。

输入示例:
3 3 1 3
1 3 3
1 2 1
2 3 1

输出示例:
2
1 2 3

解题思路

使用floyed-warshall算法，用road二维数组记录图的信息，用next二维数组记录下一跳。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


#include <fstream>
#include <vector>
using namespace std;

#define INF 0x7fffffff

int main(int argc, char *argv[]) {
  ifstream ifs("./road.in");
  ofstream ofs("./road.out");
  int cityCnt, roadCnt, src, dst;
  ifs >> cityCnt >> roadCnt >> src >> dst;
  vector<vector<int>> road(cityCnt+1, vector<int> (cityCnt+1, INF));
  vector<vector<int>> next(cityCnt+1, vector<int> (cityCnt+1, -1));
  for (int i = 0; i < roadCnt; i++) {
    int a, b, c;
    ifs >> a >> b >> c;
    road[a][b] = c;
    next[a][b] = b;
  }
  // floyed-warshall
  for (int k = 1; k <= cityCnt; k++) {
    for (int i = 1; i <= cityCnt; i++) {
      for (int j = 1; j <= cityCnt; j++) {
        if (road[i][k] != INF && road[k][j] != INF && road[i][k] + road[k][j] < road[i][j]) {
          road[i][j] = road[i][k] + road[k][j];
          next[i][j] = k;
        }
      }
    }
  }
  ofs << road[src][dst] << endl;
  int i = src;
  while (i != dst) {
    ofs << i << " ";
    i = next[i][dst];
  }
  ofs << dst;
  return 0;
}

中科大2012年复试机试题详解

相关文章：