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

## 二、阅读程序（判断题1分，选择题3分，共计40分） 判断题正确填 `T`，错误填 `F`。 ### 第1题 ```cpp #include<iostream> int main() { int n, c; std::cin >> n >> c; long long sum = 0; int pre = 1000000000; for (int i = 0; i < n; ++i) { int a; std::cin >> a; if (pre > a) { pre = a; } sum += pre; pre += c; } std::cout << sum << "\n"; } ```

### 第2题 ```cpp bool c[max_size][max_size] = {false}; void draw(int size, int x, int y) { if (size == 1) { c[x][y] = true; } else { int half = size / 2; draw(half, x + half, y); draw(half, x, y + half); draw(half, x + half, y + half); } } void print(int n) { int length = 1 << n; draw(length, 0, 0); for (int x = 0; x < length; ++x) { for (int y = 0; y < length; ++y) { if (c[x][y]) std::cout << '*'; else std::cout << '.'; } std::cout << "\n"; } } ```

### 第三题 ```cpp bool valid = true; std::vector<int> adj[max_node]; bool instack[max_node] = {false}; bool visited[max_node] = {false}; void dfs(int node) { instack[node] = true; visited[node] = true; for (auto after : adj[node]) { if (!visited[after]) { visited[after] = true; dfs(after); } else if (instack[after]) { valid = false; } } instack[node] = false; } int main() { int n, m; std::cin >> n >> m; for (int i = 0; i < m; i++) { int x, y; std::cin >> x >> y; adj[x].push_back(y); } for (int i = 1; i <= n; i++) { if (!visited[i]) { dfs(i); } } if (valid) { std::cout << "Valid\n"; } else { std::cout << "Invalid\n"; } } ```

## 三、完善程序（单选题，每小题3分，共计30分） ### 第1题 给定一个 $n\times n$ 的网格。第 $i+1$ 行、第 $j+1$ 列的格子（$0\le i,j<n$）记作 $(i,j)$。格子 $(i,j)$ 的颜色由字符 $P[i\bmod n][j\bmod n]$ 决定，如果是 `B`，则 $(i,j)$ 是黑格，如果是 `W`，则是白格。 给定 $Q$ 个查询，请依次处理。每个查询给出 $4$ 个整数 $A,B,C,D$，求出以 $(A,B)$ 为左上角、$(C,D)$ 为右下角的矩形区域内包含的黑格数量。 ```cpp #include<iostream> int n, q; int s[1001][1001]; long long sum(int row, int col) { long long a = 1LL * ____(1)____ ; long long b = 1LL * (row/n) * s[n][col%n]; long long c = 1LL * (col/n) * s[row%n][n]; long long d = 1LL * ____(2)____ ; return ____(3)____ ; } int main() { std::cin >> n >> q; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { char c; std::cin >> c; ____(4)____ ; } while (q-->0) { int x1, x2, y1, y2; std::cin >> x1 >> y1 >> x2 >> y2; std::cout << ____(5)____ << "\n"; } } ```

### 第2题 给定一个分数 $a/b$，若它是一个假分数，请将它化简成带分数形式输出。例如当 $a/b=91/30$，输出 ```text 1 3-- 30 ``` 当输入是一个真分数时，请将它化简后输出，且忽略整数部分，例如当 $a/b=30/100$ 时，输出 ```text 3 -- 10 ``` 当输入的分数可以变成整数时，忽略它分数部分。注意输出的所有分数都应该是既约的。 ```cpp #include<iostream> int len(int n) { int length = 0; while (n > 0) { n/=10; length++; } return length; } void print(int n, char ch) { while (n-->0) std::cout << ch; } int main() { int a, b; char dummy; std::cin >> a >> dummy >> b; int p = a; int q = b; while (a != 0 and b != 0) { if (a >= b) a %= b; else b %= a; } int gcd; if ( ____(1)____ ) gcd = b; else gcd = a; int i = p / q; p %= q; p /= gcd; q /= gcd; if ( ____(2)____ ) { std::cout << i << "\n"; } else { int i_len = len(i); int p_len = len(p); int q_len = len(q); ____(3)____ ; std::cout << ____(4)____ << "\n"; if (i != 0) std::cout << i ; ____(5)____ ; std::cout << "\n"; ____(6)____ ; std::cout << ____(7)____ << "\n"; } } ```