共48道题,当前是第1

初赛真题

阅读以下程序,完成相关问题

01 #include<bits/stdc++.h>
02 using namespace std;
03 
04 const int MAXN = 1e5;
05 int a[MAXN], b[MAXN];
06 int main() {
07     int n, m, x, y;
08     cin >> n >> m;
09     for (int i = 1; i <= n; i++) {
10         cin >> x >> y;
11         a[x]++;
12         a[y + 1]--;
13     }
14     int cnt = 0, ans = 0;
15     for (int i = 0; i <= m; i++) {
16         cnt += a[i];
17         ans += cnt;
18     }
19     cout << ans;
20     return 0;
21 }
//注:输入流中 1<=x<=y<=m


1. B。
2. B。
3. B。
4. A。
5. A。
6. D。
这道题实际上是在通过差分的方式来维护在区间加一的操作下的序列,最后的 ans 则是在计算数列内所有元素的和。所以即便我们将区间向左平移一个单位,仍然会得到相同的结果,最终影响答案的是每一次操作下有多少数字被加一了,而不是哪些数字被加一了。需要注意的是,如果输入的 x, y 是满足条件的,那么最大值肯定是每次都给整个区间加一,最小值是每次都给单点加一。如果输入的 x, y不满足条件,那么最小值时我们可以通过令 x = m + 1, y = 0 的方式来给整个数列减去 m + 1 ,最大值类似。

Question

1.输入的 x 和 y 可以是全体整数。( )

2.将 14 行 int cnt = 0, ans = 0; 的清零过程除去没有问题。( )

3.将 16 行 cnt += a[i]; 与 17 行 ans += cnt; 交换位置不会影响最终结果。( )

4.将 11 行的 x 改成 x-1 并把 12 行的 y + 1 改成 y 不会影响最终结果。( )

5.现在已知输入的 n 与 m,则答案的极差为( )

6.在 (1) 的基础上,除去“注”中的条件,则答案的极差为( )

陈伦制作 版权所无 粤ICP备16127491号-1