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

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

### 第2题 ```cpp #include<iostream> #include<algorithm> int main() { int n, d; std::cin >> n >> d; int x[n]; for (int i = 0; i < n; ++i) { std::cin >> x[i]; } std::sort(x, x + n); long long pair = 0; int j = 1; for (int i = 0; i < n; ++i) { while (j < n and x[j] - x[i] <= d) { j++; } pair += j - i - 1; } std::cout << pair << "\n"; } ```

### 第三题 ```cpp #include<iostream> int mem[2000000] = {0}; int q[2000000] = {0}; int main() { int r, b; std::cin >> r >> b; int step = 0; while (r != 0) { step++; if (mem[r] > 0) { break; } else { mem[r] = step; } q[step] = r * 2 / b; r = r * 2 % b; } std::cout << "0."; if (r == 0) { for (int i = 1; i <= step; ++i) std::cout << q[i]; } else { int begin = mem[r]; for (int i = 1; i < begin; ++i) std::cout << q[i]; std::cout << "("; for (int i = begin; i < step; ++i) std::cout << q[i]; std::cout << ")"; } } ```

## 三、完善程序（单选题，每小题3分，共计30分） ### 第1题 给定一个长度为 $n$、由正整数组成的序列 $a_1,a_2,\ldots,a_n$，请你求出所有子段中第 $k$ 小的子段和。 ```cpp #include<iostream> int n,k,a[100005]; bool check(long long mid) { long long s = 0; for(int l = 1,r = 1;r <= n; r++) { while(l <= r && ____(1)____) l++; s+=____(2)____; } return ____(3)____; } int main(){ std::cin>>n>>k; for(int i=1;i<=n;i++) { std::cin >>a[i]; a[i]+=a[i-1]; } long long lbound = 0,rbound = 5000000000,mid; while(lbound <= rbound) { mid = (lbound + rbound) >> 1; if(check(mid)) ____(4)____rbound = mid - 1; else ____(5)____lbound = mid + 1; } std::cout << lbound; return 0; } ```

### 第2题 给定 $n\times m$ 个方格构成的图，每个格子都有一种地形：有一些格子是墙，以符号 `#` 表示，墙不可通行；有一些格子是空地，以符号 `.` 表示，空地可以通行。请统计从左上角的方格出发，有多少种不同的路线可以以最短距离走到右下角。在行走过程中，不能进入地形为墙的方格，保证起点与终点方格地形不是墙。且行走时，只能移动到水平或垂直方向相邻的方格。由于方案数可能很大，输出模 $1000000007$ 的余数。 ```cpp #include<iostream> char a[1000][1000]; int d[1000][1000]; int w[1000][1000]; int n, m; int qx[1000*1000]; int qy[1000*1000]; int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0, -1, 0}; void bfs(int x, int y) { qx[0] = x; qy[0] = y; d[x][y] = 1; w[x][y] = 1; int head = 0; int tail = 1; while (head < tail) { int x = qx[head]; int y = qy[head]; head++; for (int k = 0; k < 4; ++k) { int nx = x + dx[k]; int ny = y + dy[k]; if (0 <= nx and nx < n and 0 <= ny and ny < m and a[nx][ny] == '.') { if ( ____(1)____ ) { d[nx][ny] = ____(2)____; w[nx][ny] = ____(3)____; qx[tail] = nx; qy[tail] = ny; tail++; } else if (____(4)____) { w[nx][ny] = ____(5)____; w[nx][ny] %= 1000000007; } } } } } 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]; } bfs(0, 0); std::cout << ____(6)____ << "\n"; } ```