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

## 二、阅读程序（判断题正确填T，错误填F；判断题1分，选择题3分，共计40分） ### 第1题 ```cpp int solve1(int n) { n++; int size = 0; int digit[16]; int pow = 1; int s = 0; while (n > 0) { digit[size] = n % 10; size++; n /= 10; s += pow; pow *= 5; } while (size > 0) { --size; pow /= 5; s += (digit[size] / 2) * pow; if (digit[size] % 2 == 0) break; } return s - 1; } int solve2(int n) { int s = 0; for(int i = 1; i <= n ; i += 2) { int t = i; bool pass = true; while (t > 0) { int x = t % 10; if(x%2 == 0) { pass = false; break; } t /= 10; } if (pass) s++; } return s; } ``` 保证 `solve1` 与 `solve2` 的参数 `n` 是非负整数。

### 第2题 ```cpp int a[maxn]; int b[maxn]; int n, m; const long long mod = 1'000'000'007; bool filled[maxn][maxn]; long long mem[maxn][maxn]; long long solve(int i, int j) { if (i == n) return 1; if (j == m) return 1; if (filled[i][j]) return mem[i][j]; filled[i][j] = true; long long sum = solve(i+1, j) + solve(i, j+1); if (a[i] == b[j]) { return mem[i][j] = sum % mod; } else { return mem[i][j] = (sum - solve(i+1, j+1)) % mod; } } int main() { std::cin >> n >> m; for (int i = 0; i < n; ++i) std::cin >> a[i]; for (int i = 0; i < m; ++i) std::cin >> b[i]; std::cout << (solve(0, 0) + mod) % mod << "\n"; } ```

### 第3题 ```cpp long long k; int n; int p[20]; bool used[20] = {false}; long long frac[20]; void gen(int i) { if (i > n) { for (int i = 1; i <= n; ++i) std::cout << p[i] << " "; return; } for (int a = 1; a <= n; ++a) if (not used[a]) { if (k <= frac[n-i]) { p[i] = a; used[a] = true; gen(i+1); return; } else { k -= frac[n-i]; } } } int main() { n = 1; frac[0] = frac[1] = 1; std::cin >> k; while (k > frac[n]) { k -= frac[n]; frac[n+1] = frac[n] * (n+1); n++; } gen(1); } ```

## 三、完善程序（单选题，每小题3分，共计30分） ### 第1题 有一个用户，在连续的 $n$ 天里，都会收到积分，也会消费积分。积分在获得后的 $m$ 天内有效（$m$ 为一个给定的整数），过期失效。 在第 $i$ 天，用户将会获得 $p_i$ 分，他需要消费 $c_i$ 分。若积分不足，则用掉全部积分后用其他方式消费。消费积分时，先用最早的。当天获取的积分可以当天消费。请计算这个用户一共消费了多少积分。 ```cpp const int max_size = 100000; int queue[max_size]; int head = 0; int tail = 0; int main() { int n, m; std::cin >> n >> m; int sum = 0; for (int i = 0; i < n; ++i) { int p, c; std::cin >> p >> c; queue[____(1)____] = p; while ( ____(2)____ ) { if ( ____(3)____ ) { queue[head] -= c; sum += c; c = 0; } else { int amount = ____(4)____; c -= amount; sum += amount; } } if ( ____(5)____ > m) { head++; } } std::cout << sum << "\n"; } ```

### 第2题 给定一个 $1$ 到 $n$ 的排列 $p_1,p_2,\ldots,p_n$，请统计排列中所有长度大于等于 $2$ 的连续子序列的次大数之和。 定义 $\max_2(a_i,a_{i+1},\ldots,a_j)$ 表示从 $a_i$ 开始到 $a_j$ 结束的连续子序列中，排名第二大的数，这个数就是一个连续子序列的次大数之和。 题目就是要求： $$ \sum_{1 \le i < j \le n} \max_2(a_i,a_{i+1},\ldots,a_j) $$ `solve` 用于解决这个问题。 ```cpp int q[maxn]; int prev[maxn]; int next[maxn]; long long solve(int n, int p[]) { for (int i = 1; i <= n; ++i) { ____(1)____ ; } p[0] = q[0] = prev[0] = 0; p[n+1] = q[n+1] = next[n+1] = n+1; for (int i = 1; i <= n; ++i) { int num = ____(2)____; int prev_num = p[i-1]; int next_num = p[i+1]; prev[num] = ____(3)____; next[num] = ____(4)____; } long long sum = 0; for (int num = 1; num <= n; ++num) { int prev_num = prev[num]; int prev_prev_num = prev[prev_num]; int next_num = next[num]; int next_next_num = next[next_num]; sum += (long long) num * ____(5)____ * (q[next_num] - q[num]); sum += (long long) num * (q[num] - q[prev_num]) * ____(6)____ ; ____(7)____ = prev_num; ____(8)____ = next_num; } return sum; } ```