## 一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）

## 二、阅读程序（判断题正确填T，错误填F；判断题1分，选择题3分，共计40分） ### 第1题 ```cpp int solve(int n, int a[], int b[]) { std::sort(a, a + n); std::sort(b, b + n); int ans = std::max(a[0] - b[0], b[0] - a[0]); int i = 0; int j = 0; while (i < n && j < n) { if (a[i] < b[j]) { int diff = b[j] - a[i]; if (ans > diff) ans = diff; i++; } else { int diff = a[i] - b[j]; if (ans > diff) ans = diff; j++; } } return ans; } ``` #### 判断题

#### 选择题

### 第2题 ```cpp int solve(int n, int a[]) { int ret = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { int sum = 0; for (int k = j; k <= i; ++k) { sum += a[k]; } ret += sum; } } return ret; } ``` #### 判断题

#### 选择题

### 第三题 ```cpp using std::string; string post(const string& pre, const string& in) { if (pre == "") return ""; char root = pre[0]; int i = 0; while (root != in[i]) ++i; string left_in = in.substr(0, i); string right_in = in.substr(i+1); string left_pre = pre.substr(1, i); string right_pre = pre.substr(i+1); string left_post = post(left_pre, left_in); string right_post = post(right_pre, right_in); return left_post + right_post + root; } ``` #### 判断题

#### 选择题

## 三、完善程序（单选题，每小题3分，共计30分） ### 第1题 给定 $n$ 根火柴的长度 $a_1,a_2,\cdots,a_n$，请用这些火柴围成一个面积最大的三角形。注意所有的火柴都必须用上，不得丢弃。输出最大三角形的面积。假设最大面积为 $s$，则输出 $16s^2$。$1 \le a_i \le 40$，数据保证至少有一种方案可以围成三角形。 ```cpp #include<iostream> using i64 = long long; int n; int a[40]; bool mem[40][40*40][40*40]; i64 value[40][40*40][40*40]; i64 solve(int i, int x, int y, int z) { if (i < n) { if (mem ____(1)____ > 0) return value ____(2)____; i64 s1 = solve(i+1, x + a[i], y, z); i64 s2 = solve(i+1, x, y + a[i], z); i64 s3 = solve(i+1, x, y, z + a[i]); mem[i][x][y] = true; return value[i][x][y] = ____(3)____; } else { if ( ____(4)____ ) return 0; i64 p = ____(5)____ ; return ____(6)____ ; } } int solve() { std::cin >> n; for (int i = 0; i < n; ++i) { std::cin >> a[i]; } std::cout << solve(0, 0, 0, 0); } ```

### 第2题 给定一个 $N \times M$ 的迷宫网格（含不可通行的 `#`、可通行的 `.`、双向必传送且耗时 $0$ 的滑梯对（大写字母）、出口 `=` 和起点 `@`），从起点出发，移动相邻草地耗时 $1$，传送耗时 $0$。计算从起点到达出口所需的最短时间。 ```cpp #include<iostream> char a[1000][1000]; int d[1000][1000]; int n, m; int qx[1000*1000]; int qy[1000*1000]; int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0, -1, 0}; int sumx[26]; int sumy[26]; void bfs(int x, int y) { qx[0] = x; qy[0] = y; d[x][y] = 1; int head = 0; int tail = 1; while (head < tail) { int x = qx[____(1)____]; int y = qy[____(2)____]; ____(3)____++; for (int k = 0; k < 4; ++k) { int nx = x + dx[k]; int ny = y + dy[k]; if (____(4)____) { if (____(5)____) continue; if ('A' <= a[nx][ny] and a[nx][ny] <= 'Z') { char c = a[nx][ny]; nx = ____(6)____ ; ny = ____(7)____ ; } if ( ____(8)____ ) { d[nx][ny] = ____(9)____ ; qx[tail] = nx; qy[tail] = ny; tail++; } } } } } int main() { std::cin >> n >> m; int sx, sy, tx, ty; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { std::cin >> a[i][j]; if (a[i][j] == '@') {sx = i; sy = j;} if (a[i][j] == '=') {tx = i; ty = j;} if ('A' <= a[i][j] and a[i][j] <= 'Z') { sumx[a[i][j] - 'A'] += i; sumy[a[i][j] - 'A'] += j; } } bfs(sx, sy); std::cout << ____(10)____ << "\n"; } ```