洛谷讲课手稿

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 输出到多行？
      • 是否存在修约？保留几位小数？
      • 是否存在场宽等特殊排版格式？
      • …………

复习方法：

• 多做题，锻炼细心程度和手感

完善程序

分析：

• 不同于自己编写程序，在完善程序题目中，我们需要去尝试理解别人的程序和别人的脑回路。
• 同时，按照近年来的套路，也常常是对一些基本算法思想的考察（算法基本功很重要！很重要！很重要！）。
• 此外，近年来，完善程序一般都会告诉选手所采用的算法，这一定程度上算是降低了难度。

在你有了基本的算法基础之后，我们可以采取如下战术：

• 对于没有任何算法提示的题目，可以先想一想如果自己写的话，会采取什么样的算法，使用什么样的数据结构。
• 对于有算法提示的题目，可以先想一想如果自己采用这一算法去写这个题目的话，程序大概会是个怎样的结构。

需要注意的点：

• 在句末，要注意看原程序是否有分号。如果必要时甚至可以全部写上分号（实际程序中，多个分号也是可以运行的；但是少了分号将导致程序无法运行）
• 一定要注意程序中是否有一些细节上的改动（部分关键位置上的细节变化可能导致整个填空方式大不一样）

总体：

• 巩固数据结构、算法、数学基本功（可以说是整个NOI系列赛事中的重中之重）
• 充分了解计算机科学相关常识（在选择题中所占的比例还是有一些的，同时对于以后有兴趣在大学中继续学习计算机相关专业的同学，这些都是挺重要的专业常识）
• 多做题！多做题！多做题！（锻炼题感，熟悉一般的套路和解题技巧，做到临危不乱）

好的以上就是这些，谢谢大家。

大家有什么疑问的话可以现在提出来。