洛谷讲课手稿

HansBug

发布于 2018-04-11 02:57:37

1K0

文章被收录于专栏：HansBug's LabHansBug's Lab

Hello大家好，我是洛谷的HansBug。首先自我介绍下，我现在在北京航空航天大学，计算机科学与技术专业读大二，我参加过2013-2015年的提高组NOIP和NOI2015。

整体状况

初赛举办于大概每年的十月中旬，大概在一个月后（光棍节前后）会进行NOIP复赛。
近些年初赛的门槛也越来越高，在江浙地区，有些市有些年份甚至普及组分数线可以高达95，而其他时候也至少得90才基本能保证进入复赛。

可以说在中强省，初赛的要求越来越严格。那么NOIP初赛有哪些基本的前置要求呢？

初赛基本要求

熟练运用比赛用语言（Pascal、C、C++，2020年开始NOI不再支持Pascal和C，2022年开始NOIP将不再支持Pascal和C），掌握最基本的语法知识
了解基本的计算机基础知识，并且能进行简单的运算
了解基本的算法和数据结构知识，并且能进行一定程度的运用（可以说是整个NOI系列竞赛的核心内容，时间关系不在本节详细讲述）
了解一些数学知识，并能进行简单的运算

下面我们来看看初赛大致是怎样的题型分布。

题型

NOIP初赛主要题型分为四种：

选择题
- 共占30分
- 20题，每题1.5分
- 普及组全部为单选题，提高组为15个单选题和5个多选题（多选题完全正确对才给分）
问题求解
- 共占10分
- 两道题，近年来一般为填空题形式，每题5分
读程序
- 共占32分
- 4题，每题8分
- 前三题一般为单个填空，最后一道题有时会分成几个点作答
完善程序
- 共占28分
- 分两道完善程序题，将完整的程序挖掉一些空进行填空
- 每空2-3分，因评分标准而异

由此看来，选择题、读程序和完善程序都占了大约三分之一不到一点的比例，哪一块都是不能忽视的。

选择题

主要考点：

百科题、时事热点题（2017提高组单选第1题，多选第4、5题）
- 计算机行业的前沿技术新闻和CCF、NOIP相关的新闻（CCF官网、NOI官网）
计算机基础知识计算题（2017提高组第2、3、4题）
- 多做题，了解一般性的计算机基础知识
（重点）算法、数据结构、数学题（2017提高组第5、6、7、8、9、10、11、12、13、14、15，多选1、2、3题）（时间关系不在本节详细讲述）

那么接下来，我来科普一些NOIP初赛选择题常考的计算机基础知识。

计算机基础知识

计算机发展史

第一代计算机：电子管计算机（代表：ENIAC，约占地170平方米，运算速度每秒约5000次）
第二代计算机：晶体管计算机（体积依然挺大的，和现代的计算机样子大不一样，仍在使用纸带编写程序，运算速度每秒几十万次）
第三代计算机：中小规模集成电路计算机（已经有了一些现代电脑的模样，每片集成不超过1000个逻辑门，每秒几百万次到几千万次）
第四代计算机：大、超大规模集成电路计算机（目前的计算机，2.0GHz，十亿次运算每秒）
未来计算机：人工智能计算机？生物计算机？量子计算机？

说到这，不得不提一下计算机内部的存储结构。

计算机存储单位及换算关系

现代计算机均为2进制计算机（唯一的非2进制计算机——ENIAC，采用十进制）
最小单位为2进制位(Bit)，基本单位为字节(Byte)
换算关系（那么接下来就是换算关系）
- 1 Byte = 8 Bit
- 1 KB = 1024 Byte (1 Kb = 1024 Bit)
- 1 MB = 1024 KB
- 1 GB = 1024 MB
- 1 TB = 1024 GB
- 1 PB = 1024 TB
- …………
- 1 Word = 16 / 32 / 64 / 128 Bit （视计算机字长而定，这个数字也被称为字长，目前主流为32和64，部分GPU中可能存在128或者更高位数的情况）

还有一类初赛百考不厌的题型就是进制转换

进制转换

十进制转化为其他进制
其他进制转化为十进制
2^X进制与二进制之间的快速转换（通过将每一位拆开，分别转化为二进制再拼接即可，转回来则为逆过程）

快速转换的意义：对于有些比较多个不同进制下的数的大小的题目，我们可以将8、16进制的数快速转化为2进制，10进制的数转化为2进制，再在二进制下比较，这样可以大大节省计算时间。

还有一类频繁出现在卷子上的知识点就是数的表示法——原码、反码、补码。

原码、反码、补码

（均以8位二进制为例）

原码
- 首位为符号位，0表示正，1表示负
- 后面的若干位为数值位，表示数字的绝对值大小
- 特点
  - 0有两种表示法：1000000, 0000000
  - 8位二进制原码只能表示255个不同的数
  - -128无法表示
反码
- 首位为符号位，0表示正，1表示负
- 后面的若干位为数值位
  - 当数字为_正数_时，和原码一样
  - 数字为负数时，为绝对值的二进制取反
- 例如
  - 127 -> 01111111
  - 23 -> 00010111
  - -127 -> 10000000
  - -23 -> 11101000
  - 0 -> 00000000
  - -0 -> 11111111
- 特点
  - 0有两种表示法
  - 8位二进制反码只能表示255个不同的数
  - -128无法表示
补码
- 首位为符号位，0表示正，1表示负
- 后面的若干位为数值为
  - 当数字为_正数_时，和原码一样
  - 数字为负数时，在反码的基础上+1
  - 10000000表示-128
- 例如
  - 127 -> 01111111
  - 23 -> 00010111
  - -127 -> 10000001
  - -23 -> 11101001
  - 0 -> 00000000
  - -128 -> 10000000
- 特点
  - 0只有一种表示法
  - 8位二进制补码能表示256个不同的数
  - 可以表示-128
  - 对于负数运算，可以直接进行二进制加法运算，完美解决了负数运算的问题，故计算机中有符号整数类型一般都采用这一表示法

还有一类特别喜欢考的就是位图(Bitmap)。

位图

在X位色的位图中，每个像素点的存储将占用X个二进制位(Bit)
- 例如，灰度色（0-255黑白）的图片每个像素将占用8Bit(1字节)，32位色的图片每个像素将占用32Bit(4字节)
在长宽分别为Width, Height的位图中，将一共需要存储Width * Height个像素点
综上，在不考虑文件头文件尾等存储空间的情况下，位图存储空间为(Width * Height * X / 8)字节（一般考试中问到的存储空间指的也是这个），其他
平年、闰年：设年份为X，当年份满足((X % 4 == 0) AND (X % 100 != 0)) OR (x % 400 == 0)时，该年为闰年，即2月有29天，一年有366天。否则为平年，2月仅有28天，一年365天。
冯诺依曼的贡献：五大部件体系结构（控制器、存储器、运算器、输入输出系统）、存储程序工作原理、2进制
其他的一些计算机常识例如：
- 邮件协议，SMTP(简单邮件传输协议)、IMAP(交互邮件访问协议)、POP3(邮局协议版本3)（2017年）
- NOI是什么意思？(全国青少年奥林匹克_竞赛_)（2017年）
- Microsoft Office的软件有哪些（2016年）
- 大小写锁定，键盘操作（2016年）
- 输入输出设备分类（即是输入又是输出的设备：光驱、触摸屏）
- 各种协议的中文全称（TCP/IP，传输控制协议/网际协议；HTTP，超文本传输协议；FTP，文件传输协议……）
- A/B/C/D/E类IP地址
- …………

除此之外还考过很多其他的相关点。

所以给大家的建议是：

关注前沿计算机技术方面的新闻
关注CCF和NOI系列竞赛政策类新闻
多做题，熟悉各类基本知识
考试时要敢猜

问题求解

首先我们来看下问题求解都有哪些考察点：

数论
图论
离散数学知识

问题求解类题目的特点：

方法很多样，不太容易总结一般性的套路
观察近年来的题目可以发现，答案数字大都不是很大。大部分题目，只要足够细心和耐心，都是可以暴力解决的
对于有些题目，不妨采用类似写程序时采用的算法来解决

比如这样一道例题：

所以说很多时候不要被限制住了思维。换个角度想问题，或者说用自己最熟悉的方式想问题才是上策。

复习方法：

多做题，熟悉一般排列组合题目的套组
算法和数据结构知识要做到活学活用
锻炼细心和耐心

读程序

分析：

读程序题一道题8分
意味着在江浙等初赛要求较严格的地区，只要错一道读程序题就凶多吉少了
读程序要力求零失误

战术：

对于相对简单相对短的程序，要认真计算，不能出现失误
对于相对长、循环次数很多、递归结构较复杂（总之逐步手算很困难）的程序，要尝试寻找规律
- 策略一：观察程序的结构，弄清楚程序每一步都在干什么，推测出程序最终要实现的功能
- 策略二：当不太容易一下子看出功能时，也可以考虑先按照程序手算上几个来回，并且仔细观察各项数据的变化规律，往往这个时候也容易发现一些规律。
- 注意
  - 不要想当然！不要想当然！不要想当然！ 一定要注意带有一定功能的程序在一些细节上是否有变化。（很多时候一个小细节的变化，甚至可能导致整个程序功能发生重大变化）
  - 仔细观察输入输出的格式！
    - 输出到一行 or 输出到多行？
    - 是否存在修约？保留几位小数？
    - 是否存在场宽等特殊排版格式？
    - …………