历年CSP-J初赛真题解析 | 2020年CSP-J初赛完善程序（34-43）

标签：__ le 真题 int 初赛 答案 处应 解析 CSP

学习C++从娃娃抓起！记录下CSP-J备考学习过程中的题目，记录每一个瞬间。

附上汇总贴：历年CSP-J初赛真题解析 | 汇总_热爱编程的通信人的博客-CSDN博客

---

（质因数分解）给出正整数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 = __1__; __2__ < = n; i ++) {
        __3__ {
            printf("%d ", i);
            n = n / i;
        }
    }
    if(__4__)
        printf("%d ", __5__);
    return 0;
}

第34题

1处应填（ ）

A.1

B.n-1

C.2

D.0

【答案】：C

【解析】

从2开始的每个因数，拿来试除n，选C

第35题

2处应填（ ）

A.n / i

B.n / (i * i)

C.i * i

D.i * i * i

【答案】：C

【解析】

质因数分解只试除到小于等于 n \sqrt{n} n ​的那些质因子，选C

第36题

3处应填（ ）

A.if (n % i == 0)

B.if (i * i <= n)

C.while (n % i == 0)

D.while (i * i <= n)

【答案】：C

【解析】

若n%i==0，则反复除，获得多个质因数，选C

第37题

4处应填（ ）

A.n > 1

B.n <= 1

C.i < n / i

D.i + i <= n

【答案】：A

【解析】

试除完所有小于等于√n的因子后，n还有剩（没有被除成1），说明这个此时n的值就是那个唯一大于√n的质因子

第38题

5处应填（ ）

A.2

B.n / i

C.n

D.i

【答案】：C

【解析】

参考第4题，此时就应该输出n。例如n=5时，输出5

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

输入第一行包含两个整数n和m ( 1 ≤ n ≤ 5000 , 1 ≤ m ≤ 1 0 9 ) (1\le n\le 5000, 1\le m\le 10^9) (1≤n≤5000,1≤m≤109)。

接下来n行，每行两个整数 a i a_i ai​， b i ( 0 ≤ a i , b i ≤ m ) b_i(0\le a_i,b_i\le m) bi​(0≤ai​,bi​≤m)。

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

试补全程序。

#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 (__1__)
			{
				segment t = A[j];
				__2__
			}
}

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 (__3__)
			A[p++] = A[i];
	n = p;
	int ans = 0, r = 0;
	int q = 0;
	while (r < m)
	{
		while (__4__)
			q++;
		__5__;
		ans++;
	}
	cout << ans << endl;
	return 0;
}

第39题

1处应填（ ）

A.A[j].b>A[j-1].b

B.A[j].a<A[j-1].a

C.A[j].a>A[j-1].a

D.A[j].b<A[j-1].b

【答案】：B

【解析】

冒泡排序，每次循环将左端点最大的线段排到最右边

第40题

2处应填（ ）

A.A[j+1]=A[j];A[j]=t;

B.A[j-1]=A[j];A[j]=t;

C.A[j]=A[j+1];A[j+1]=t;

D.A[j]=A[j-1];A[j-1]=t;

【答案】：D

【解析】

如果左侧线段的左端点更大，左右交换

第41题

3处应填（ ）

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

B.A[i].b<A[i-1].b

C.A[i].b>A[i-1].b

D.A[i].b<A[p-1].b

【答案】：A

【解析】

把被其他更大范围的线段覆盖的线段删除

第42题

4处应填（ ）

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

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

C.q<n&&A[q].a<=r

D.q<n&&A[q].b<=r

【答案】：A

【解析】

下下一个线段存在且左端点在已覆盖区间右边界左侧，则下个线段就被跳过。所以出while循环时，会保留最后一个线段左端点在已覆盖区间右边界左侧

第43题

5处应填（ ）

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

B.r=max(r,A[q].b)

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

D.q++

【答案】：B

【解析】

确定新的已覆盖区间右边界

标签：__,le,真题,int,初赛,答案,处应,解析,CSP
From： https://blog.csdn.net/guolianggsta/article/details/143672413