洛谷讲课手稿

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系列赛事中的重中之重)
  • 充分了解计算机科学相关常识(在选择题中所占的比例还是有一些的,同时对于以后有兴趣在大学中继续学习计算机相关专业的同学,这些都是挺重要的专业常识)
  • 多做题!多做题!多做题!(锻炼题感,熟悉一般的套路和解题技巧,做到临危不乱)

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

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序员叨叨叨

6.4 移位操作符

Cg语言中的移位操作符,功能和C语言中的一样,也可以作用在向量上,但是向量类型必须是int类型。例如:

1182
来自专栏程序人生

谈谈状态机

题记:上周做 BBL 里讲了我们 Tubi TV 内部做 DSL 的一些简单实践,大家反馈不错。有同事建议我给大家先补补 FSM,之后再进阶 CFG,可能会更顺...

3407
来自专栏程序员互动联盟

【编程基础第七讲】如何编写有界面的程序?

存在问题: 好多小伙伴都有一个疑问,我我们学编程貌似都是看输出,怎么才能搞个像window上程序带个又界面的,眼见为实嘛 解决方案: 很多群友都在问学习了C语言...

4587
来自专栏跟着阿笨一起玩NET

求本年、本月、本周等数据

本文转载:http://www.cnblogs.com/ethan-qi/archive/2013/05/14/3077371.html

701
来自专栏battcn

一起学设计模式 - 策略模式

策略模式: 是对算法的包装,是把使用算法的责任和算法本身分割开来,委派给不同的对象管理。策略模式通常把一个系列的算法包装到一系列的策略类里面,作为一个抽象策略类...

882
来自专栏小樱的经验随笔

元胞自动机实现多数分类算法

元胞自动机(Cellular automaton) 元胞自动机是由元胞组成的网格,每个元胞都根据邻域的状态来选择开或关。所有的元胞都遵循同样的规则,也称为元胞的...

3295
来自专栏ACM算法日常

乐乐的RPG难题(递推) - HDU 2045

人称“AC女之杀手”的超级偶像LELE最近忽然玩起了深沉,这可急坏了众多“Cole”(LELE的粉丝,即"可乐"),经过多方打探,某资深Cole终于知道了原因,...

1513
来自专栏PPV课数据科学社区

用 Python 做文本挖掘的流程

作者:肖智博 来源:https://zhuanlan.zhihu.com/p/19630762 点击阅读原文可进入超链接。 收集数据 数据集。如果是已经被人做...

4548
来自专栏数据小魔方

R语言数据清洗实战——世界濒危遗产地数据爬取案例

最近重复新翻阅R语言领域唯一一本关于网络数据采集的参考书——《基于R语言的自动数据收集》,开篇就是一个数据爬取的案例。 尽管之前已经粗略的看过一遍,但是仍感书中...

5726
来自专栏架构师之路

洗稿,技术上怎么判断文章相似性?

这几天“差评洗稿”的事情,闹得沸沸扬扬,楼主本身也是内容创作的手艺人,简单说两句。

1724

扫码关注云+社区

领取腾讯云代金券