前言
\(NOIP2018\)初赛已经结束了,接下来就要准备复赛了。
不过,在此之前,还是先为初赛写一篇解题报告吧。
单项选择题
- 送分题。()可以考虑将它们全部转化为\(10\)进制,则\((269)_{16}=(617)_{10}=(1151)_8\),而\((1001101011)_2=(619)_2\)。故选\(D\)。
- 常识题。显然\(C,C++,Pascal\)都是编译执行的,只有\(Python\)是解释执行的。故选\(D\)。
- 一道没什么意义的题目,随便蒙了一个答案。应选\(B\)。
- 显然,深度为\(0\)的有\(1\)个节点,深度为\(1\)的有\(k\)个节点,深度为\(2\)的有\(k^2\)个节点,一次类图,深度为\(h\)的有\(k^h\)个节点,于是总节点数\(=k^0+k^1+k^2+...+k^h=\frac{k^{h+1}-1}{k-1}\)。故选\(A\)。
- 由于\(T(0)=1,T(n)=T(n-1)+n\),所以可得\(T(n)=\frac{n(n+1)}2+1\),这是近似于\(O(n^2)\)的。故选\(D\)。
- 比较基础的一道题。应选\(B\)。
- 显然,如果固定左端点在最左边,则随机选取一个右端点后线段长度期望为\(\frac12\),再选择一个点,则线段长度期望肯定小于\(\frac12\),而答案中只有\(B\)一个选项是小于\(\frac12\)的。故选\(B\)。
- 仔细观察,可以发现\(B\)选项和\(C\)选项本质上是一样的,因此可以排除。\(A\)和\(D\)选项自己手算验证一下,便能发现\(A\)是错误的。故选\(A\)。
- 感性理解一下,不管你摸几次球,每次摸到两个球的概率是一样的,所以应该是\(1:1\)。故选\(D\)。
- 手算代入验证一下即可(其实就相当于\(x-=x\&-x\))。应选\(B\)。
不定项选择题
- 常识题。特别注意即使是关机的手机也不能带进考场,草稿纸同理。故选\(AB\)。
- 自己画画图即可,这里就不多说了。应选\(CD\)。
- 关于此题,\(ABD\)选项选项显然是对的,而\(C\)选项显然有问题。故选\(ABD\)。
- 这题应该也是挺显然的。应选\(ABD\)。
- 这种题目考前刚好复习过。应选\(BCD\)。
问题求解
- 根据第③点,由于丙去了,所以丁一定不去;根据第④点,由于丁不去,而丙去了,说明甲一定去了;根据第②点,由于丁不去,说明乙肯定也没去;根据第①点,由于乙不去,而甲去了,说明周末没下雨。因此答案为:去了 没去 没去 没下雨。
- 首先要知道一个性质:若设\(a\le b\),则\(a=a\ or\ b,b=a\ and\ b\)(我也不会证)。对于\(b\)含\(1\)的位数\(x\)进行枚举(从\(0\sim5\)),可以发现\(a\)有\(2^x\)种选择(每一位选与不选),因此答案就是\(\sum_{i=0}^5C_5^i2^i\),计算得\(243\),但由于我们考虑的是\(a\le b\)的情况,因此最终答案应为\(243*2-32=454\)(注意去重)。
阅读程序写结果
- 模拟即可。答案应为\(4\)。
- 这题本质上就是让你求一张图上有几个环。答案应为\(6\)。
- 熟悉哈希的人都知道,\(magic()\)函数就是一个哈希的过程,因此就是要求出有多少个不同的子串,这应该还是很好数的。答案应为\(16\)。
- 不难发现\(getNext()\)函数就是求当前排列的下一个排列。,也可以像奆佬\(hl666\) 一样用康拓展开求解。答案应为\(2\ 1\ 3\ 5\ 6\ 4\)和\(3\ 2\ 5\ 6\ 1\ 4\)。
完善程序
(1)既然它读入\(x\)了,就不可能是\(a[i]=x\)(否则可以直接读入\(a[i]\))。故答案应为\(a[x]=i\)。
(2)根据双向链表的的对称性可以轻松求解。故答案应为\(i+1\)。
(3)同上。故答案应为\(R[a[i]]\)。
(4)同上。故答案应为\(a[i]\)。
(5)自己带几组数据算一下即可。故答案应为\(R[i]\)。
这题是一个先贪心、再\(DP\)的过程(其实一开始的贪心是完全多余的)。
(1)根据此题代码的大致思路,显然可以看出第一个空该填什么。故答案应为\(a[i]*0.95<=b[i]\)。
(2)这应该也是比较显然的。故答案应为\(total\_a>=threshold\)。
(3)这一空与上一空差不多,也是判断当前是否已经满足\(\ge threshold\)。故答案应为\(total\_a+j+a[i]\)。
(4)显然,此空填的应该是在第二个商店买东西的总价。故答案应为\(f[j]+total\_b-total\_b\_prefix\)。
(5)只要会背包的应该都知道,既然它判断了\(j>=a[i]\),就肯定是要进行转移了。故答案应为\(f[j-a[i]]\)。
后记
这次初赛应该能压线过的。
希望在\(NOIP2018\)中能够取得一个好成绩!