NOIP2017提高组初赛滚粗记&&初赛分析

滚粗过程

本蒟蒻报了NOIP2017提高组,这是我第一次参加提高组…初赛之前把之前10年的题都刷了,NOIP2016提高组初赛甚至做了98.5分。本来以为我初赛稳了,结果NOIP2017年初赛滚粗了。
考试前去吃了顿自助餐吃到撑,然后回到学校又看了看复习资料就进考场了。想到NOIP2016初赛的题我1个小时就做完了,我就故意放慢了点速度,结果没想到NOIP2017初赛选择题里数学题这么多,有些组合数学问题还不会做。。。结果过了一个小时我才开始看问题求解。第二题问题求解忘了最短路计数,一条一条数,结果花了很多时间还GG了。后来老师说还有40分钟考试结束的时候我发现我读程和填程题都没动过。。。然后我慌了,开始抓紧时间做题,结果读程第二道行列写反,第四道题目看错。。。最后虽然在考试结束前2分钟左右做完了,但是GG了。成绩出来73.5分(巫蛊偶大佬94分),还好分数线72.5分,勉强进复赛了(然后复赛270分拿了个二等奖又滚粗了)。
其实这篇博客应该在去年NOIP结束之后写的,但是没写,所以NOIP2018初赛之前写了。

题解

单选题

  1. 从()年开始,NOIP 竞赛将不再支持 Pascal 语言。
    A. 2020 B. 2021 C. 2022 D. 2023
    好像是C,没什么好说的。
  2. 在 8 位二进制补码中,10101011 表示的数是十进制下的()。
    A. 43 B. -85 C. -43D. -84
    8位2进制补码是模256意义下的同余,$171\equiv -85$,所以选B。
  3. 分辨率为 1600×900、16 位色的位图,存储图像信息所需的空间为()
    A. 2812.5KB B. 4218.75KB C. 4320KB D. 2880KB
    $1600* 900* 16 /8/1024=2812.5$选A。
  4. 2017 年 10 月 1 日是星期日,1949 年 10 月 1 日是()
    A. 星期三 B. 星期日 C. 星期六 D. 星期二
    这题有点变态,简单来说要求2017-1049+(1050~2017年中的闰年个数)模7的值,由于2000年是闰年,所以1050~2017中闰年的个数就是模4为0的数的个数就是$[2017/4]+[1049/4]$,最后算出来这个数值是1,然后倒回去,就是星期六。
  5. 设 G 是有 n 个结点、 m 条边(n ≤ m)的连通图,必须删去 G 的()条边,才能使得 G 变成一棵树。
    A. m – n + 1
    B. m – n
    C. m + n + 1
    D. n – m + 1
    n个点的树一定要有n-1条边,把多余边减掉即可,选A。
  6. 若某算法的计算时间表示为递推关系式:
    T(N) = 2T(N / 2) + N log N
    T(1) = 1
    则该算法的时间复杂度为( )。
    A. O(N)
    B. O(N log N)
    C. O(N log^2 N)
    D. O(N^2 )
    第一眼感觉是$\Theta(nlg^2n)$的,然后我们用数学归纳法法来证一下:
    对n进行归纳证明,假设$T(n)\le 2nlg^2n+1$(c为常数)。
    当n=1时,成立,
    当n>1时,
    $T(n)=2T(n/2)+nlgn$
    $\le 2(2n/2lg^2(n/2)+1)+nlgn$
    $=2n(lgn-1)^2+nlgn+2$
    $=2nlg^2n-4nlgn+2n+nlgn+2$
    $\le 2nlg^2n+1$
    成立。所以这个时间复杂度是$O(nlg^2 n)$的,然后我们可以用类似的方式证明它是$\varOmega(nlg^2n)$的,所以这道题其实CD都对的,但是可能很多选手都用O来表示$\Theta$,所以就选个C吧。
  7. 表达式 a * (b + c) * d 的后缀形式是()。
    A. a b c d * + * B. a b c + * d *
    C. a * b c + * d D. b + c * a * d
    表达式树建一下,后序遍历一下就完了,选B。
    8.由四个不同的点构成的简单无向图的个数是()。
    A.32 B.35 C.38 D.41
    考试的时候数到心态爆炸,还数错了,其实转念一想发现这是道水题。四个点的简单无向图边的种类只有六种,枚举边的条数,如果是4条,5条,6条,所有情况都合法,如果是3条,只有4种情况不合法,如果是0条,1条,2条,全部不合法,所以答案是
    $C_6^4+C_6^5+C_6^6+C_6^3-4=38$
    显然选C
  8. 将 7 个名额分给 4 个不同的班级,允许有的班级没有名额,有()中不同的分配方案。
    A. 60 B. 84 C. 96 D. 120
    插板法,先令每个班多分一个,这样每个班必须有名额,现在问题是11个名额分给4个班,就相当于10个空插3个板的方案数。$C_{10}^3=120$。选D。
  9. 若 $f[0] = 0, f[1] = 1, f[n + 1] = (f[n] + f[n – 1]) / 2$,则随着 i 的增大,$f[i]$将接近于()。
    A.1/2 B.2/3 C.$(\sqrt{5}-1)/2$ D.1
    考试时候模拟了一下脑抽选了C,其实我们可以尝试一下改变这个式子。
    从之前的式子可得f(n+1)-f(n)=-1/2(f(n)-f(n-1)),设d(n)=d(n+1)-d(n)则易得,$d(n)=(-1/2)^{n-1}$,这样我们就把原问题转化为了一个等比数列求和的问题,最后结果是2/3。
  10. 设 A 和 B 是两个长为 n 的有序数组,现在需要将 A 和 B 合并成一个排好序的数组,请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做()次比较。
    A. n^2 B. n log n C. 2n D. 2n-1
    生成的数组每填一位一次比较,最后一次不用比较,所以选D。
  11. 在 n(n ≥ 3)枚硬币中有一枚质量不合格的硬币(质量过轻或质量过重),如果只有一架天平可以用来称重且称重的硬币数没有限制,下面是找出这枚不合格的硬币的算法。请把 a-c 三行代码补全到算法中。
    原题格式比较多,不方便复制,这题比较水,选D。
  12. 有正实数构成的数字三角形排列形式如图所示。
    第一行的数为 a 11 ;第二行的数从左到右依次为
    a 21 , a 22 ;…第 n 行的数为 a n1 , a n2 , …, a nn 。从 a 11
    开始,每一行的数 a ij 只有两条边可以分别通向
    下一行的两个数 a (i+1)j 和 a (i+1)(j+1) 。用动态规划算
    法找出一条从 a 11 向下通到 a n1 , a n2 , …, a nn 中某
    a nn个数的路径,使得该路径上的数之和达到最大。
    令 $C[i,j]$是从 a 11 到 a ij 的路径上的数的最大和,并且 $C[i,0]=C[0,j]=0,$,则 $C[i,j]=()$。
    A.$ max{C[i-1,j-1], C[i-1,j]} + a ij$
    B. $C[i-1,j-1] + C[i-1,j]$
    C.$ max{C[i-1,j-1], C[i-1,j]} + 1$
    D. $max{C[i,j-1],C[i-1,j]} + a ij$
    格式问题不方便复制,也是水题,选A
    14.小明要去南美洲旅游,一共乘坐三趟航班才能到达目的地,其中第 1 个航班准点的概率是 0.9,第 2 个航班准点的概率为 0.8, 第 3 个航班准点的概率为0.9。如果存在第 i 个(i=1,2)航班晚点,第 i+1 个航班准点,则小明将赶不上第 i+1 个航班,旅行失败;除了这种情况,其他情况下旅行都能成功。请问小明此次旅行成功的概率是()。
    A. 0.5 B. 0.648 C. 0.72 D . 0.74
    $E(第一次准点)* (E(第二次晚点)* E(第三次晚点)+E(第二次准点))$
    $+E(第一次晚点)* E(第二次晚点) * E(第三次晚点)=0.74$,选D
  13. 欢乐喷球:儿童游乐场有个游戏叫“欢乐喷球”,正方形场地中心能不断喷出彩色乒乓球,以场地中心为圆心还有一个圆形轨道,轨道上有一列小火车在匀速运动,火车有六节车厢。假设乒乓球等概率落到正方形场地的每个地点,包括火车车厢。小朋友玩这个游戏时,只能坐在同一个火车车厢里,可以在自己的车厢里捡落在该车厢内的所有乒乓球,每个人每次游戏有三分钟时间,则一个小朋友独自玩一次游戏期望可以得到()个乒乓球。假设乒乓球喷出的速度为 2 个/秒,每节车厢的面积是整个场地面积的 1/20。
    A. 60 B. 108 C. 18 D. 20
    一共360个球,每个球1/20的概率接到,所以期望18个球。选C。

多选题

  1. 以下排序算法在最坏情况下时间复杂度最优的有()
    A. 冒泡排序 B. 快速排序
    C. 归并排序 D. 堆排序
    冒泡和快排最差情况下都是$\Theta(n^2)$的,选CD。

  2. 对于入栈顺序为 a, b, c, d, e, f, g 的序列,下列()不可能是合法的出栈序列。
    A. a, b, c, d, e, f, g
    B. a, d, c, b, e, g, f
    C. a, d, b, c, g, f, e
    D. g, f, e, d, c, b, a
    随便模拟一下发现只有C不行。

  3. 下列算法中,()是稳定的排序算法。
    A. 快速排序 B. 堆排序
    C. 希尔排序 D. 插入排序
    稳定是指互不小于的数排序前后相对位置不变,这里只有插入排序符合这个性质。
  4. 以下是面向对象的高级语言的有(
    A. 汇编语言 B. C++
    C. Fortran D. Java
    汇编不可能,C++和Java是的,Fortran我记得好像是第一个高级语言,肯定不可能面向对象的,所以选BD。
    5.以下和计算机领域密切相关的奖项有()。
    A. 奥斯卡奖 B. 图灵奖
    C. 诺贝尔奖 D. 王选奖
    肯定选BD,没什么好说的。

问题求解

本人翻车的开始。。。
1. 如右图所示,共有 13 个格子。对任何一个格子进行一次操作,会使得它自己以及与它上下左右相邻的格子中的数字改变(由 1 变 0,或由 0 变 1)。现在要使得所有的格子中的数字都变为 0,至少需要_________次操作。
blob.jpg
暴力枚举边上状态,然后填进去,发现至少3次。
2. 如下图所示,A 到 B 是连通的。假设删除一条细的边的代价是 1,删除一条粗的边的代价是 2,要让 A、B 不连通,最小代价是_________(2 分),最小代价的不同方案数是_________(3 分)。(只要有一条删除的边不同,就是不同的方案)
blob.jpg
平面图最小割,把块作为点,块间相邻的边作为边跑最短路即可。(可以用反证法证明其正确性)然后第二个空最短路计数(考试时候慌了没想到,瞎数还数错了)。

读程题

1.

输入8 4
这题数据范围比较小,记忆化搜索即可。
2.

输入:3
一看就是让你填一个5阶幻方,但是它的行和列是反的。。。然后我就被扣了8分。

输入:6
2 6 3 4 5 1
从函数名就看出来是归并排序,然后好像要求个逆序对,算一下就好了。
4.

此题比较变态,我们发现x和y的影响不是很大,相当于在两个长度分别为n和m的坑里x和y以1的速度来回走,求第一次同时碰壁时x和y分别是多少。其实就求一下lcm(n,m),然后判断一下x和y在哪边就可以了。

填程题

填程题比较简单,不作解释

Tagged with:

1 thought on “NOIP2017提高组初赛滚粗记&&初赛分析”

发表评论