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

## 二、阅读程序（判断题正确填T，错误填F；判断题1分，选择题3分，共计37分） ### 第1篇 ```cpp #include<iostream> int main() { int a, b; std::cin >> a >> b; int s = 0; int c = 0; while (a > 0 || b > 0) { int x = a % 10; int y = b % 10; a /= 10; b /= 10; if (x + y + c >= 10){ c = 1; s++; } else { c = 0; } } std::cout << s << "\n"; } ```

### 第2篇 ```cpp #include<iostream> int main() { int d; std::cin >> d; char s[1000]; int size = 0; char c; while (std::cin >> c){ while (size > 0 and d > 0){ char top = s[size - 1]; if (top < c){ d--; size--; } else{ break; } } s[size++] = c; } while (d > 0){ d--; size--; } for (int i = 0; i < size; ++i) { std::cout << s[i]; } } ```

### 第3篇 ```cpp #include<iostream> int choose[20]; int dfs(int m, int n) { if (m == n) { bool flag = true; for (int i = 0; i + 1 < n; ++i) { if (choose[i] && choose[i+1]) { flag = false; } } if (flag) { return 1; } else { return 0; } } else { choose[m] = true; int pick = dfs(m+1, n); choose[m] = false; int drop = dfs(m+1, n); return pick + drop; } } int fib(int n) { int f[21]; f[0] = 1; f[1] = 2; for (int i = 2; i <= n; ++i) { f[i] = f[i-1] + f[i-2]; } return f[n]; } int main() { int n; std::cin >> n; std::cout << dfs(0, n) << " "; std::cout << fib(n) << "\n"; } ```

## 三、完善程序（单选题，每小题3分，共计33分） ### 第1题 给定 $n$ 个数字 $a_1,a_2,\dots,a_n$，从 $1$ 到 $n$ 中挑出两个下标 $i$ 与 $j$ 并要求 $i<j$，然后将 $a_i$ 与 $a_j$ 组成一个有序的序对 $(a_i,a_j)$。 请统计，能从序列中挑选出多少种互不相等的数对？数对 $(x,y)$ 与 $(p,q)$ 称之为不相等，是指 $x\neq p$ 或者 $y\neq q$。 ```cpp #include<iostream> const int maxn = 100005; int a[maxn]; int c[maxn]; bool present[maxn]; int main() { int n; std::cin >> n; int num = 0; long long pair = 0; for (int i = 1; i <= n; ++i) { std::cin >> a[i]; pair += ____①____; pair -= c[____②____]; ____③____ = num; if (____④____){ present[a[i]] = true; ____⑤____; } } std::cout << pair << "\n"; } ```

### 第2题 给定一个网格，该网格由 $n\times m$ 个方格组成，每个方格内有一个正整数，其中第 $i$ 行第 $j$ 列的整数为 $a_{i,j}$。我们可以使用任意多块 $1\times 2$ 的骨牌覆盖网格上的数字，每块骨牌不得重叠，也不能越过网格的边界。被骨牌覆盖的数字就消失了。请问应该如何摆放骨牌，使得没有消失的数字的异或之和达到最大。所谓异或，就是 C++ 的 `^` 操作。注意不覆盖任何骨牌也是一种选择。 ```cpp #include<iostream> int a[20][20]; bool covered[20][20]; int n, m; int solve(int x, int y, int sum) { if (y == m) { return ____②____; } if (____③____) { return sum; } int D = 0; if ( covered[x][y] ) D = solve(x, y+1, sum); else D = ____④____; int V = 0; int H = 0; if (!covered[x][y] && y+1 < m && !covered[x][y+1]) { covered[x][y] = covered[x][y+1] = true; V = ____⑤____; covered[x][y] = covered[x][y+1] = false; } if (!covered[x][y] && x+1 < n) { covered[x][y] = covered[x+1][y] = true; H = ____⑥____; covered[x][y] = covered[x+1][y] = false; } return std::max(D, std::max(H, V)); } int main(){ std::cin >> n >> m; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { std::cin >> a[i][j]; } } std::cout << ____①____ << "\n"; } ```