## 一、单项选择题（共15题，每题2分，共计30分）

## 二、阅读程序（判断题1分，选择题3分，共计40分） 判断题正确填 `T`，错误填 `F`。 ### 第1题 ```cpp int solve1(int n) { int s = 0; for (int i = 1; i <= n; ++i) { int f = 1; for (int j = i; j >= 1; --j) { f = f * i; } s = s + f; } return s; } int solve2(int n) { int s = 0; for (int i = n; i >= 1; --i) { s = s + 1; s = s * i; } return s; } ``` 保证 `solve1` 与 `solve2` 的参数 `n` 是正整数。 #### 判断题

#### 选择题

### 第2题 ```cpp bool move(int b[], int n) { for (int i = 0; i < n; ++i) { if (b[i] == 1) { b[i] = 0; } else { b[i] = 1; return true; } } return false; } void loop(int n) { int b[n]; for (int i = 0; i < n; ++i) b[i] = 0; do { for (int i = 0; i < n; ++i) std::cout << b[i]; std::cout << "\n"; } while (move(b, n)); } ``` 保证 `loop` 的参数 `n` 是一个正整数。 #### 判断题

#### 选择题

### 第三题 ```cpp struct flat_map { struct { int key; int value; } bucket[65536]; int size = 0; struct result { int index; bool hit; }; result find(int begin, int end, int key) { if (begin == end) return {begin, false}; else { int mid = begin + (end - begin) / 2; if (key < bucket[mid].key) return find(begin, mid, key); else if (bucket[mid].key < key) return find(mid+1, end, key); else return {mid, true}; } } int get(int key) { result p = find(0, size, key); if (p.hit) return bucket[p.index].value; else return 0; } void put(int key, int value) { result p = find(0, size, key); for (int i = size; i > p.index; --i) bucket[i] = bucket[i - 1]; size++; bucket[p.index].key = key; bucket[p.index].value = value; } }; ``` #### 判断题

#### 选择题

## 三、完善程序（单选题，每小题3分，共计30分） ### 第1题 给定含有 $n$ 个顶点的有向完全图（顶点编号为 $0$ 到 $n-1$）。顶点 $x$ 到 $y$ 的边的权重为 `g[x][y]`。 请找出一条不重复经过任何点的路径，从顶点 $0$ 出发到顶点 $n-1$ 结束，路径上所有边的权重的异或值尽可能大。 ```cpp int n, m; long long g[MAXN][MAXN]; bool visited[MAXN] = {false}; int dfs(int node, int path) { if (____(1)____) { return ____(2)____; } int best = 0; visited[node] = true; for (int next = 0 ; next < ____(3)____; ++next) { if (____(4)____) { best = std::max(best, ____(5)____); } } visited[____(6)____] = ____(7)____; } int solve() { return ____(8)____; } ```

### 第2题 $n$ 个岛屿由 $n$ 座桥连成环。岛的编号为 $0$ 到 $n-1$，第 $i$ 座桥连第 $i$ 号岛与第 $(i+1)\bmod n$ 号岛。 某旅行团从第 $x_1$ 号岛出发，依次访问的岛编号为 $x_2,\ldots,x_m$。 现在需要选择拆掉一座桥，请问拆掉哪一座桥可以使得旅行团的过桥次数达到最小。 ```cpp int solve(int n, int m, int x[]) { int diff[n]; for (int i = 0; i < n; ++i) diff[i] = 0; int common = 0; for (int i = 1; i < m; ++i) { int prev = x[i - 1]; int next = x[i]; int begin, end; if (prev < next) { begin = prev; end = next; } else { begin = next; end = prev; } common += ____(1)____; int inc = ____(2)____; diff[____(3)____] += inc; diff[____(4)____] -= inc; prev = next; } int best = n * m; int sum = 0; for (int i = 0; i < n; ++i) { ____(5)____; if (best > sum) best = sum; } return ____(6)____; } ```