NOIp2017 提高组初赛试题 总结与错题分析

· · 个人记录

别到时候CSP一轮滚粗退役就好玩了

得分情况：73.5 / 100

单项选择题

  1. 从（ ）年开始，NOIP 竞赛将不再支持 Pascal 语言。

    A. 2020 
B. 2021 
C. 2022 
D. 2023

正确答案： C

解析：背吧。。。

  1. 由四个不同的点构成的简单无向连通图的个数是（ ）。

    A. 32 
B. 35 
C. 38 
D. 41

正确答案：C

解析：易知由四个不同的点构成的完全图（边数最多的情况）的边数是4*3/2=6条，构成的生成 树（边数最少的情况）的边数是4 - 1 = 3条。

则考虑从6条边内选3,4,5,6条边组合成一张连通图。那么总共有C_{6}^{3}+C_{6}^{4}+C_{6}^{5}+C_{6}^{6}=42种。想 想看是不是有什么不对？对了，从完全图的6条边任选3条边可能会组成一个三角形，换言之：会有 一个点被孤立（不连通），所以总共有42-4=38（每个点都可能被孤立）种图。

  1. 设 A 和 B 是两个长为 n 的有序数组，现在需要将 A 和 B 合并成一个排好序的 数组，请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做 （ ）次比较。

    A. n^2 
B. nlogn 
C. 2n 
D. 2n-1

正确答案：D

解析：由于原数组有序，故每一个数都会比较两次，并且最后一个数不用比较。共2n-1次。

  1. 小明要去南美洲旅游，一共乘坐三趟航班才能到达目的地，其中第 1 个航班 准点的概率是 0.9，第 2 个航班准点的概率为 0.8, 第 3 个航班准点的概率为

    上第 $i+1$ 个航班，旅行失败；除了这种情况，其他情况下旅行都能成功。请 问小明此次旅行成功的概率是（ ）。 ``` A. 0.5 B. 0.648 C. 0.72 D. 0.74 ```

正确答案：D

解析：注意到题目中定义旅行失败为：当且仅当第 i 个(i=1,2)航班晚点，第 i+1 个航班准点时旅行失败。换言之：第1个航班与第2个航班同时晚点是不算旅行失败的（傻逼出题人）。

分类讨论。

考虑第一种情况：航班1晚点而航班2不晚点。此时概率为0.1*0.8=0.08。

考虑第二种情况：航班2晚点而航班3不晚点。此时概率为0.2*0.9=0.18。

所以失败概率为0.08+0.18=0.26，则成功概率为1-0.26=0.72。

不定项选择题

  1. 以下排序算法在最坏情况下时间复杂度最优的有（ ）。
  A. 冒泡排序 
  B. 快速排序 
  C. 归并排序 
  D. 堆排序

正确答案：CD

解析：

排序方法 平均时间复杂度 最坏时间复杂度 稳定性
冒泡排序 O(n^2 ) O(n^2) 稳定
快速排序 O(nlogn) O(n^{2}) 不稳定
归并排序 O(nlogn) O(nlogn) 稳定
堆排序 O(nlogn) O(nlogn) 不稳定

问题求解

  1. 如下图所示，A 到 B 是连通的。假设删除一条细的边的代价是 1，删除一条粗的边的代价是 2，要让 A、B 不连通，最小代价是（），最小代价的不同方案数是（）。（要有一条删除的边不同，就是不同的方案）

正确答案：4， 9

解析：第一个空很显然。第二个空正解是最小割转对偶图（wdnmd我不会网络流啊。。。），当然我们也可以枚举代价为4的断边方案判断是否能断成不连通图。

阅读程序写结果

  1. #include <iostream>
using namespace std;
int n, s, a[100005], t[100005], i;
void mergesort(int l, int r)
{
   if (l == r)
       return;
   int mid = (l + r) / 2;
   int p = l;
   int i = l;
   int j = mid + 1;
   mergesort(l, mid);
   mergesort(mid + 1, r);
   while (i <= mid && j <= r)
   {
       if (a[j] < a[i])
       {
           s += mid - i + 1;
           t[p] = a[j];
           p++;
           j++;
       }
       else
       {
           t[p] = a[i];
           p++;
           i++;
       }
   }
   while (i <= mid)
   {
       t[p] = a[i];
       p++;
       i++;
   }
   while (j <= r)
   {
       t[p] = a[j];
       p++;
       j++;
   }
   for (i = l; i <= r; i++)
       a[i] = t[i];
}
int main()
{
   cin >> n;
   for (i = 1; i <= n; i++)
       cin >> a[i];
   mergesort(1, n);
   cout << s << endl;
   return 0;
}
    输入：6
2 6 3 4 5 1
输出：_________

    正确答案：8

    解析：一看就知道是归并排序，然而这个题是归并排序求逆序对的板子（并不是什么排成升序数列）。。

  2. #include <iostream>
using namespace std;
int main()
{
   int n, m;
   cin >> n >> m;
   int x = 1;
   int y = 1;
   int dx = 1;
   int dy = 1;
   int cnt = 0;
   while (cnt != 2)
   {
       cnt = 0;
       x = x + dx;
       y = y + dy;
       if (x == 1 || x == n)
       {
           ++cnt;
           dx = -dx;
       }
       if (y == 1 || y == m)
       {
           ++cnt;
           dy = -dy;
       }
   }
   cout << x << " " << y << endl;
   return 0;
}
    输入 1：4 3
输出 1：_________
输入 2：2017 1014
输出 2：_________
输入 3：987 321
输出 3：_________

    正确答案：1 3

    ​ 2017 1

    ​ 1 321

    解析：

    对于输入1，我们可以画图如上，有n个点但只有n-1条边。cnt初始化为0，必须有2个边界被同时到达才可输出。考虑最小公倍数。将路径拉长，lcm(2,3)=6，所以两个动点同时走了6个单位长度时第一次到达了"公共边界"。此时应输出答案。长度为3的走了6÷3=2次，是偶数次，所以回到了1；长度为2的走了6÷2=3次，是奇数次，所以走到了3。所以第一组数据应输出1 3

    同理，第二组数据lcm(2016,1013)是2016的奇数倍，1013的偶数倍，所以答案是2017 1

    第三组数据lcm(986,320)是986的偶数倍，320的奇数倍，所以答案是1 321

    实际上手玩是能看出规律的，但是我第一组都玩错了那咋办嘛。。

总结

初赛主要是考查概念 组合数学 概率 图论模型的抽象和程序的理解能力。这套题我的错误基本集中在组合数学 程序理解和图论抽象上。或许应该集中解决这方面的问题了。比如程序理解就应该多掏题解