## 一、单项选择题（共计 $30$ 分）

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

选择题

### 第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 print(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)); } int count(int n) { int b[100]; for (int i = 0; i < n; ++i) b[i] = 0; int c = 0; do { c++; } while (move(b, n)); return c; } ``` 判断题

### 第2题（续） #### 选择题

### 第3题 ```cpp const int mod = 1'000'000'007; bool filled[maxn][maxn]; int mem[maxn][maxn]; int solve(int i, int j, int a[], int b[]) { if (i == 0 || j == 0) { return 1; } if (filled[i][j]) { return mem[i][j]; } filled[i][j] = true; int sum = (solve(i - 1, j, a, b) + solve(i, j - 1, a, b)) % mod; if (a[i] == b[j]) { return mem[i][j] = sum; } else { return mem[i][j] = (sum - solve(i - 1, j - 1, a, b)) % mod; } } ``` #### 判断题

#### 选择题

## 三、完善程序（共计 $30$ 分） 单项选择题，每小题 $3$ 分。 ### 第1题 套餐限价 有一家快餐店，出售 $N$ 种主食，其价格以数组 `A[0..N)` 表示，出售 $M$ 种饮料，其价格以数组 `B[0..M)` 表示。 现推出一种促销活动：顾客可以任选主食及饮料各一份形成套餐，若套餐价格超过一个给定的最高价格 $L$，则这份套餐只收取 $L$ 元。 请计算，若顾客购买所有食物与饮料的搭配（共有 $N\times M$ 种），需要花多少钱。 ```cpp long long S[MAXN]; long long solve(int N, int M, int L, int A[], int B[]) { std::sort(A, A + ____(1)____); std::sort(B, B + M); S[0] = 0; for (int i = 0; i < M; ++i) { S[i + 1] = S[i] + B[i]; } long long j = ____(2)____; long long sum = 0; for (int i = 0; i < N; ++i) { while (____(3)____ && A[i] + B[j - 1] > L) { j--; } sum += (A[i] * ____(4)____); sum += S[____(5)____]; sum += (M - j) * L; } return sum; } ```

### 第2题 给定 $N$ 个点、$M$ 条边，构成一个图。请统计从 $1$ 号出发，有多少条简单路径。所谓简单路径，就是路径上的所有点及所有边不会重复出现两次。如果路径超过 $1024$ 条，则输出 $-1$。 ```cpp #include <iostream> #include <vector> int N, M; std::vector<int> adj[200001]; // 邻接表 bool visited[200001]; const int limit = 1024; int cnt = 0; void dfs(int node) { ____(1)____; if (cnt > limit) return; visited[node] = ____(2)____; for (auto v : ____(3)____) { if (not visited[v]) { dfs(____(4)____); } } visited[node] = ____(5)____; } int main() { std::cin >> N >> M; for (int i = 0; i < M; ++i) { int A, B; std::cin >> A >> B; adj[A].push_back(B); adj[B].push_back(A); } dfs(____(6)____); if (cnt > limit) { std::cout << -1 << "\n"; } else { std::cout << cnt << "\n"; } } ```