题目截取历年真题

一

（枚举因数） 从小到大打印正整数 n 的所有正因数。

试补全枚举程序。。

01 #include <bits/stdc++.h>
02 using namespace std;
03
04 int main() {
05     int n;
06     cin >> n;
07
08     vector<int> fac;
09     fac.reserve((int)ceil(sqrt(n)));
10
11     int i;
12     for (i = 1; i * i < n; ++i) {
13         if ( ① ) {
14             fac.push_back(i);
15         }
16     }
17
18     for (int k = 0; k < fac.size(); ++k) {
19         cout << ② << " ";
20     }
21     if ( ③ ) {
22         cout << ④ << " ";
23     }
24     for (int k = fac.size() - 1; k >= 0; --k) {
25         cout << ⑤ << " ";
26     }
27 }

1.①处应填（ ） {{ select(1) }}

• n%i==0
• n%i==1
• n%(i-1)==0
• n%(i-1)==1

2.②处应填（ ） {{ select(2) }}

• n / fac[k]
• fac[k]
• fac[k]-1
• n / (fac[k]-1)

3.③处应填（ ） {{ select(3) }}

• (i-1) * (i-1) == n
• (i-1) * i == n
• i * i == n
• i * (i-1) == n

4.④处应填（ ） {{ select(4) }}

• n-i
• n-i+1
• i-1
• i

5.⑤处应填（ ） {{ select(5) }}

• n / fac[k]
• fac[k]
• fac[k]-1
• n / (fac[k]-1)

二

(洪水填充) 现有用字符标记像素颜色的 8x8 图像。颜色填充的操作描述如下：给定起始像素的位置和待填充的颜色，将起始像素和所有可达的像素（可达的定义：经过 一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色都与起始像素颜色相同），替换为给定的颜色。 试补全程序。

01 #include <bits/stdc++.h>
02 using namespace std;
03
04 const int ROWS = 8;
05 const int COLS = 8;
06
07 struct Point {
08     int r, c;
09     Point(int r, int c) : r(r), c(c) {}
10 };
11
12 bool is_valid(char image[ROWS][COLS], Point pt,
13     int prev_color, int new_color) {
14     int r = pt.r;
15     int c = pt.c;
16     return (0 <= r && r < ROWS && 0 <= c && c < COLS &&
17     ① && image[r][c] != new_color);
18 }
19
20 void flood_fill(char image[ROWS][COLS], Point cur, int new_color) {
21     queue<Point> queue;
22     queue.push(cur);
23
24     int prev_color = image[cur.r][cur.c];
25     ② ;
26
27     while (!queue.empty()) {
28         Point pt = queue.front();
29         queue.pop();
30
31         Point points[4] = { ③ , Point(pt.r - 1, pt.c),
32         Point(pt.r, pt.c + 1), Point(pt.r, pt.c - 1)};
33         for (auto p : points) {
34             if (is_valid(image, p, prev_color, new_color)) {
35                 ④ ;
36                 ⑤ ;
37             }
38         }
39     }
40 }
41
42 int main() {
43     char image[ROWS][COLS] = {{'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g'},
44     {'g', 'g', 'g', 'g', 'g', 'g', 'r', 'r'},
45     {'g', 'r', 'r', 'g', 'g', 'r', 'g', 'g'},
46     {'g', 'b', 'b', 'b', 'b', 'r', 'g', 'r'},
47     {'g', 'g', 'g', 'b', 'b', 'r', 'g', 'r'},
48     {'g', 'g', 'g', 'b', 'b', 'b', 'b', 'r'},
49     {'g', 'g', 'g', 'g', 'g', 'b', 'g', 'g'},
50     {'g', 'g', 'g', 'g', 'g', 'b', 'b', 'g'}};
51
52     Point cur(4, 4);
53     char new_color = 'y';
54
55     flood_fill(image, cur, new_color);
56
57     for (int r = 0; r < ROWS; r++) {
58         for (int c = 0; c < COLS; c++) {
59             cout << image[r][c] << " ";
60         }
61         cout << endl;
62     }
63 // 输出：
64 // g g g g g g g g
65 // g g g g g g r r
66 // g r r g g r g g
67 // g y y y y r g r
68 // g g g y y r g r
69 // g g g y y y y r
70 // g g g g g y g g
71 // g g g g g y y g
72
73     return 0;
74 }

6.①处应填 ( )

{{ select(6) }}

• image[r][c] == prev_color
• image[r][c] != prev_color
• image[r][c] == new_color
• image[r][c] != new_color

7.②处应填 ( ) {{ select(7) }}

• image[cur.r+1][cur.c] = new_color
• image[cur.r][cur.c] = new_color
• image[cur.r][cur.c+1] = new_color
• image[cur.r][cur.c] = prev_color

8.③处应填 ( ) {{ select(8) }}

• Point(pt.r, pt.c)
• Point(pt.r, pt.c+1)
• Point(pt.r+1, pt.c)
• Point(pt.r+1, pt.c+1)

9.④处应填 ( ) {{ select(9) }}

• prev_color = image[p.r][p.c]
• new_color = image[p.r][p.c]
• image[p.r][p.c] = prev_color
• image[p.r][p.c] = new_color

10.⑤处应填 ( ) {{ select(10) }}

• queue.push( p )
• queue.push(pt)
• queue.push(cur)
• queue.push(Point(ROWS,COLS))

三

（Josephus 问题） 有 𝑛 个人围成一个圈，依次标号 0 至 𝑛 − 1。从 0 号开 始，依次 0 , 1 , 0 , 1 , … 交替报数，报到 1 的人会离开，直至圈中只剩下一个人。求最后 剩下人的编号。 试补全模拟程序。

11.①处应填（ ）

{{ select(11) }}

• i < n
• c < n
• i < n- 1
• c < n-1

12.②处应填（ ） {{ select(12) }}

• i % 2 == 0
• i % 2 == 1
• p
• !p

13.③处应填（ ） {{ select(13) }}

• i++
• i = (i + 1) % n
• c++
• p ^= 1

14.④处应填（ ） {{ select(14) }}

• i++
• i = (i + 1) % n
• c++
• p ^= 1

15.⑤处应填（ ） {{ select(15) }}

• i++
• i = (i + 1) % n
• c++
• p ^= 1

四

（质因数分解）给出正整数 n，请输出将 n 质因数分解的结果，结果从小到大输出。 例如：输入 n=120，程序应该输出 2 2 2 3 5，表示：120 = 2 × 2 × 2 × 3 × 5。输入保证 2≤n≤$10^9$。提示：先从小到大枚举变量 i，然后用 i 不停试除 n来寻找所有的质因子。

试补全程序。

#include <cstdio>
using namespace std;
int n, i;

int main()
{
	scanf("d", &n);
	for (i = ①; ② <= n; i++)
	{
		③
		{
			printf("%d ", i);
			n = n / i;
		}
	}
	if (④)
		printf("%d ", ⑤);
	return 0;
}

16.①处应填（ ）

{{ select(16) }}

• 1
• n-1
• 2
• 0

17.②处应填（ ）

{{ select(17) }}

• n/i
• n/(i*i)
• i*i
• i* i * i

18.③处应填（ ）

{{ select(18) }}

• if(n%i==0)
• if(i*i<=n)
• while(n%i==0)
• while(i*i<=n)

19.④处应填（ ）

{{ select(19) }}

• n>1
• n<=1
• i<n/i
• i+i<=n

20.⑤处应填（ ）

{{ select(20) }}

• 2
• n/i
• n
• i

五

**（最小区间覆盖）**给出 n 个区间，第 i 个区间的左右端点是 [$a_i$,$b_i$]。现在要在这些区间中选出若干个，使得区间 [0, m] 被所选区间的并覆盖（即每一个 0≤i≤m 都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。

输入第一行包含两个整数 n 和 m （1≤n≤5000,1≤m≤$10^9$） 接下来 n 行，每行两个整数 $a_i$，$b_i$（0≤ai​,bi​≤m）。

提示：使用贪心法解决这个问题。先用 O($n^2$)的时间复杂度排序，然后贪心选择这些区间。

试补全程序。

#include <iostream>

using namespace std;

const int MAXN = 5000;
int n, m;
struct segment
{
	int a, b;
} A[MAXN];

void sort() // 排序
{
	for (int i = 0; i < n; i++)
		for (int j = 1; j < n; j++)
			if (①)
			{
				segment t = A[j];
				②
			}
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> A[i].a >> A[i]・b;
	sort();
	int p = 1;
	for (int i = 1; i < n; i++)
		if (③)
			A[p++] = A[i];
	n = p;
	int ans = 0, r = 0;
	int q = 0;
	while (r < m)
	{
		while (④)
			q++;
		⑤;
		ans++;
	}
	cout << ans << endl;
	return 0;
}

21.①处应填（ ）

{{ select(21) }}

• A[j].b>A[j-1].b
• A[j].a<A[j-1].a
• A[j].a>A[j-1].a
• A[j].b<A[j-1].b

22.②处应填（ ）

{{ select(22) }}

• A[j+1]=A[j];A[j]=t;
• A[j-1]=A[j];A[j]=t;
• A[j]=A[j+1];A[j+1]=t;
• A[j]=A[j-1];A[j-1]=t;

23.③处应填（ ）

{{ select(23) }}

• A[i].b>A[p-1].b
• A[i].b<A[i-1].b
• A[i].b>A[i-1].b
• A[i].b<A[p-1].b

24.④处应填（ ）

{{ select(24) }}

• q+1<n&&A[q+1].a<=r
• q+1<n&&A[q+1].b<=r
• q<n&&A[q].a<=r
• q<n&&A[q].b<=r

25.⑤处应填（ ）

{{ select(25) }}

• r=max(r,A[q+1].b)
• r=max(r,A[q].b)
• r=max(r,A[q+1].a)
• q++

六

**（矩阵变幻）**有一个奇幻的矩阵，在不停的变幻，其变幻方式为：

数字 0 变成矩阵

0 0 
0 1

数字 1 变成矩阵

1 1
1 0

最初该矩阵只有一个元素 0，变幻 n 次后，矩阵会变成什么样？

例如，矩阵最初为：[0]；

矩阵变幻 1 次后：

0 0 
0 1

矩阵变幻 2 次后：

0 0 0 0
0 1 0 1
0 0 1 1
0 1 1 0

输入一行一个不超过 10 的正整数 n。输出变幻 n 次后的矩阵。

试补全程序。

提示：

<< 表示二进制左移运算符，例如$(11)_2$ << 2 = $(1100)_2$​； 而 ^ 表示二进制异或运算符，它将两个参与运算的数中的每个对应的二进制位—进行比较，若两个二进制位相同，则运算结果的对应二进制位为 0 ，反之为 1。

#include <cstdio>
using namespace std;
int n;
const int max_size = 1 << 10;

int res[max_size][max_size];

void recursive(int x, int y, int n, int t)
{
	if (n == 0)
	{
		res[x][y] = ①;
		return;
	}
	int step = 1 << (n - 1);
	recursive(②, n - 1, t);
	recursive(x, y + step, n - 1, t);
	recursive(x + step, y, n - 1, t);
	recursive(③, n - 1, !t);
}

int main()
{
	scanf("%d", &n);
	recursive(0, 0, ④);
	int size = ⑤;
	for (int i = 0; i < size; i++)
	{
		for (int j = 0; j < size; j++)
			printf("%d", res[i][j]);
		puts("");
	}
	return 0;
}

26.①处应填（） {{ select(26) }}

• n%2
• 0
• t
• 1

27.②处应填（） {{ select(27) }}

• x-step,y-step
• x,y-step
• x-step,y
• x,y

28.③处应填（） {{ select(28) }}

• x-step,y-step
• x+step,y+step
• x-step,y
• x,y-step

29.④处应填（） {{ select(29) }}

• n-1,n%2
• n,0
• n,n%2
• n-1,0

30.⑤处应填（） {{ select(30) }}

• 1<<(n+1)
• 1<<n
• n+1
• 1<<(n-1)

七

**（计数排序）**计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序，将n对10000以内的整数，从小到大排序。

例如有三对整数(3,4)、(2,4)、(3,3),那么排序之后应该是(2,4)、(3,3)、(3,4) 。

输入第一行为n,接下来n行，第i行有两个数a[i]和b[i],分别表示第i对整数的第一关键字和第二关键字。

从小到大排序后输出。

数据范围 1<n<$10^7$, 1<a[i],b[i]<$10^4$

提示：应先对第二关键字排序，再对第一关键字排序。数组ord[]存储第二关键字排序的结果，数组res[]存储双关键字排序的结果。

试补全程序。

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 10000000;
const int maxs = 10000;

int n;
unsigned a[maxn], b[maxn],res[maxn], ord[maxn];
unsigned cnt[maxs + 1];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) 
        scanf("%d%d", &a[i], &b[i]);
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < maxs; ++i)
        ①; // 利用 cnt 数组统计数量
    for (int i = 0; i < n; ++i) 
        cnt[i + 1] += cnt[i];
    for (int i = 0; i < n; ++i)
        ②; // 记录初步排序结果
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; ++i)
        ③; // 利用 cnt 数组统计数量
    for (int i = 0; i < maxs; ++i)
        cnt[i + 1] += cnt[i];
    for (int i = n - 1; i >= 0; --i)
        ④ // 记录最终排序结果
    for (int i = 0; i < n; i++)
        printf("%d %d", ⑤);

    return 0;
}

31.①处应填（） {{ select(31) }}

• ++cnt [i]
• ++cnt[b[i]]
• ++cnt[a[i] * maxs + b[i]]
• ++cnt[a[i]]

32.②处应填（） {{ select(32) }}

• ord[--cnt[a[i]]] = i
• ord[--cnt[b[i]]] = a[i]
• ord[--cnt[a[i]]] = b[i]
• ord[--cnt[b[i]]] = i

33.③处应填（） {{ select(33) }}

• ++cnt[b[i]]
• ++cnt[a[i] * maxs + b[i]]
• ++cnt[a[i]]
• ++cnt [i]

34.④处应填（） {{ select(34) }}

• res[--cnt[a[ord[i]]]] = ord[i]
• res[--cnt[b[ord[i]]]] = ord[i]
• res[--cnt[b[i]]] = ord[i]
• res[--cnt[a[i]]] = ord[i]

35.⑤处应填（） {{ select(35) }}

• a[i], b[i]
• a[res[i]], b[res[i]]
• a[ord[res[i]]]j b[ord[res[i]]]
• a[res[ord[i]]]j b[res[ord[i]]]

八

（矩形计数） 平面上有 𝑛 个关键点，求有多少个四条边都和 x 轴或者 y 轴平行的矩 形，满足四个顶点都是关键点。给出的关键点可能有重复，但完全重合的矩形只计一 次。

试补全枚举算法。

36.①处应填（ ） {{ select(36) }}

• a.x != b.x ? a.x < b.x : a.id < b.id
• a.x != b.x ? a.x < b.x : a.y < b.y
• equals(a, b) ? a.id < b.id : a.x < b.x
• equals(a, b) ? a.id < b.id : (a.x != b.x ? a.x < b.x : a.y < b.y)

37.②处应填 ( )

{{ select(37) }}

• i == 0 || cmp(A[i], A[i - 1])
• t == 0 || equals(A[i], A[t - 1])
• i == 0 || !cmp(A[i], A[i - 1])
• t == 0 || !equals(A[i], A[t - 1])

38.③处应填 ( ) {{ select(38) }}

• b - (b - a) / 2 + 1
• a + b + 1) >> 1
• (a + b) >> 1
• a + (b - a + 1) / 2

39.④处应填 ( ) {{ select(39) }}

• !cmp(A[mid], p)
• cmp(A[mid], p)
• cmp(p, A[mid])
• !cmp(p, A[mid])

40.⑤处应填 ( ) {{ select(40) }}

• A[i].x == A[j].x
• A[i].id < A[j].id
• A[i].x == A[j].x && A[i].id < A[j].id
• A[i].x < A[j].x && A[i].y < A[j].y