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

## 二、阅读程序（判断题1分，选择题3分，共计40分） 判断题正确填 `T`，错误填 `F`。 ### 第1题 ```cpp void solve(int n, int a[]) { while (true) { bool found = false; for (int i = 0; i + 1 < n; ++i) { if (a[i] > a[i+1]) { found = true; int temp = a[i]; a[i] = a[i + 1]; a[i + 1] = temp; } } if (not found) { break; } } } ``` #### 判断题

#### 选择题

### 第2题 ```cpp long long solve(long long n) { long long c = 0; long long p = 1; long long t = 0; while (n > 0) { int d = n % 10; n /= 10; if (d > 0) { c += n * p; } else { c += (n-1) * p; c += t + 1; } t += d * p; p *= 10; } return c; } ``` #### 判断题

#### 选择题

### 第三题 ```cpp #include<iostream> int n, q; char op[200000]; long long p[200000]; long long d[200000]; long long mod = 1000000007; void solve1(long long a[]) { for (int i = 0; i < n; ++i) a[i] = 0; for (int i = 0; i < q; ++i) { if (op[i] == '+') { a[p[i]] += d[i]; a[p[i]] %= mod; } else if (op[i] == '*') { for (int j = 0; j < n; ++j) { a[j] *= d[i]; a[j] %= mod; } } } } void solve2(long long a[]) { for (int i = 0; i < n; ++i) a[i] = 0; long long f = 1; for (int i = q-1; i >= 0; i--) { if (op[i] == '+') { a[p[i]] += d[i] * f; a[p[i]] %= mod; } else if (op[i] == '*') { f *= d[i]; f %= mod; } } } ``` #### 判断题

#### 选择题

## 三、完善程序（单选题，每小题3分，共计30分） ### 第1题 炼制一块合金，该合金需要 $a$ 克黄金与 $b$ 克白银。商店里有 $n$ 块材料，第 $i$ 块材料含有 $x_i$ 克黄金与 $y_i$ 克白银，且含有 $w_i$ 克杂质。 请问应该使用哪些材料，将它们炼制在一起，才能使得合金中黄金与白银含量不少于给定的要求，且杂质总和最小。所有材料均不可切割。输入数据保证所要求的合金一定可以炼成。 ```cpp int n, a, b; int x[maxn], y[maxn], w[maxn]; int mem[maxn][maxm][maxm]; bool cache[maxn][maxm][maxm]; const int INF = 1000000000; int dfs(int k, int i, int j) { if (____(1)____) return 0; if (____(2)____) return INF; if (cache[k][i][j]) return mem[k][i][j]; int ni = ____(3)____; int nj = ____(4)____; int giveup = ____(5)____; int pickup = ____(6)____; cache[k][i][j] = true; return mem[k][i][j] = std::min(giveup,pickup); } int main() { std::cin >> n >> a >> b; for (int i = 0; i < n; ++i) std::cin >> x[i] >> y[i] >> w[i]; std::cout << ____(7)____ << "\n"; return 0; } ```

### 第2题 给定一个整数序列 $a_1,a_2,\ldots,a_n$，对该序列的所有子区间，分别算出它们的中位数，并且将这些中位数组成一个新序列，输出这个新序列的中位数。 所谓一个序列的中位数，就是将这个序列排序后，排名在最中间的数字，如果序列的长度是偶数，规定中位数是排名最居中的两个数之中偏大的数。 ```cpp #include<iostream> const int maxn = 1000000; int a[maxn]; int b[maxn]; int s[maxn + 1]; int n; long long total; long long merge(int begin, int mid, int end) { int buffer[end - begin]; auto i = begin; auto j = mid; auto k = 0; long long sum = 0; while (i < mid and j < end) { if (s[i] <= s[j]) { buffer[k++] = s[i++]; sum += ____(1)____; } else { buffer[k++] = s[j++]; } } while (i < mid) buffer[k++] = s[i++]; while (j < end) buffer[k++] = s[j++]; for (int x = begin, k = 0; x < end; ++x, ++k) s[x] = buffer[k]; return sum; } long long merge_sort(int begin, int end) { auto length = end - begin; if (____(2)____) return 0; auto mid = begin + length / 2; auto front = merge_sort(begin, mid); auto back = merge_sort(mid, end); auto cross = merge(begin, mid, end); return ____(3)____; } bool predicate(int key) { for (int i = 0; i < n; ++i) { if (____(4)____) b[i] = 1; else b[i] = -1; s[i+1] = s[i] + b[i]; } long long num = ____(5)____; return ____(6)____; } int main() { std::cin >> n; for (int i = 0; i < n; ++i) std::cin >> a[i]; total = (long long)n * (n + 1) / 2; int begin = 0; int end = 1000000001; while (true) { int length = ____(7)____; if (length == 1) break; auto mid = ____(8)____; if (predicate(mid)) begin = mid; else end = mid; } std::cout << ____(9)____ << "\n"; } ```