【算法•日更•第三十六期】初赛偷懒攻略

淩亂°似流年 2023-06-03 02:51 15阅读 0赞

**▎写在前面**

洛谷是个好东西，又能上课，又能刷题，还能测初赛题，小编测了一下，才发现小编的初赛水平太菜了。

小编决定好好补一补，不过也发现了很多实用的技巧。

那么我们就以NOIP2018其中的部分题目作为例子讲解吧。

**▎Number 1**

> 下列四个不同进制的数中，与其它三项数值上不相等的是
> 
>  A. (269)16  
>   B. (617)10  
>   C. (1151)8  
>   D. (1001101011)2

这道题我们绝对是要转进制的（ 如果你不会转进制的话是真的菜），但是我们如何转才能节省时间呢？

注意到了吗？这道题有四种进制，但是有三种都是一家，那就是16进制，8进制，2进制，因为这些2的次方。

比如说(269)16，由于16是2的四次，所以每一位都表示成二进制的四位，那么( 2 6 9)16就应该表示为 0010 0110 1001。

同理(1151)8也是001001101001。

那么D就是正确答案，这种办法完美的解决了大计算量的问题。

**▎Number 2**

> 下列属于解释执行的程序设计语言是
> 
>  A. C  
>   B. C++  
>   C. Pascal  
>   D. Python

这种题并不是不知道就凉凉了，我们可以排除法，C和C++一看就是一家的，要么都选，要么都不选，显然单选题就都不选呗，平时在网上都会发现算法也是常常见有人用pascal来写的，和C++在一起放着，那么pascal也排除。

当然是python啦，选D。

**▎Number 3**

> 中国计算机学会于（ ）年创办全国青少年计算机程序设计竞赛。
> 
>  A. 1983  
>   B. 1984  
>   C. 1985  
>   D. 1986

这种题小编表示就自求多福了，看第六感吧。

选B。

**▎Number 4**

> 表达式 a \* d - b \* c 的前缀形式是（ ）。
> 
>  A. `a d * b c * -`  
>   B. `- * a d * b c`  
>   C. `a * d - b * c`  
>   D.  `- * * a d b c`

首先来画一棵表达式树，按照计算的顺序来画（后用到的在上面）：

![1551435-20190808150740823-387500697.png][]

前缀形式就是先序遍历，后缀就是后序遍历。

选B。

**▎Number 5**

> 假设一台抽奖机中有红、蓝两色的球，任意时刻按下抽奖按钮，都会等概率获得红球或蓝球之一。有足够多的人每人都用这台抽奖机抽奖，假如他们的策略均为：抽中蓝球则继续抽球，抽中红球则停止。最后每个人都把自己获得的所有球放到一个大箱子里，最终大箱子里的红球与蓝球的比例接近于（ ）。
> 
>  A. 1 : 2  
>   B. 2 : 1  
>   C. 1 : 3  
>   D. 1 : 1

这种题小编表示不懂概率这种东西怎么算，但是哪来的条件出来的什么2和3，当不会的时候就要选最正常的那个选项，而不是猜。

选D。

**▎Number 6**

> 2-3 树是一种特殊的树，它满足两个条件：
> 
> 1.  每个内部结点有两个或三个子结点；
> 2.  所有的叶结点到根的路径长度相同。
> 
> 如果一棵2-3 树有10 个叶结点，那么它可能有（ ）个非叶结点。
> 
>  A. 5  
>   B. 6  
>   C. 7  
>   D. 8

这种现场给你概念的题只要暴力枚举就好，不过有些浪费时间，那么我们就应该使用极限策略，要让这棵树的节点多，那么就试图尽量两个点连一个父亲，多就3个点连一个父亲，最少是7，最多是8，那么选C和D。

转载于:https://www.cnblogs.com/TFLS-gzr/p/11321101.html

[1551435-20190808150740823-387500697.png]: /images/20230601/0501c0bbc28d4c7ea86758a3fecd8802.png