CSP-J 2020 第一轮试题

三、完善程序（单选题，每小题 $3$ 分，共计 $30$ 分）

1.（质因数分解）给出正整数 $n$，请输出将 $n$ 质因数分解的结果，结果从小到大输出。

例如：输入 $n=120$，程序应该输出 2 2 2 3 5，表示：$120 = 2 \times 2 \times 2 \times 3 \times 5$。输入保证 $2\le n \le 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;
}

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

输入第一行包含两个整数 $n$ 和 $m$ （$1\le n \le 5000,1\le m \le 10^9$）

接下来 $n$ 行，每行两个整数 $a_i,b_i$ （$0\le a_i,b_i \le 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;
}