「NOIP」初赛相关知识整理

初赛题型:

  1. 单选 / 多选 (
  2. 动词应用 (填空
  3. 阅读理解 (阅读程序求解
  4. 完形填空 (完善程序

复赛题型:

  1. 作文

预备知识 (单选 / 多选)

这部分不知道为什么考的不多惹= =

这部分内容略作了解即可(

一些硬件知识

BIOS\text{BIOS} (Basic Input Output System\text{Basic Input Output System}) 计算机基本输入输出系统(软件)

只存储一些系统启动的基本信息 不包含驱动程序等

CPU\text{CPU} (Central Processing Unit\text{Central Processing Unit}) 中央处理器(或中央处理单元)

能直接运行机器语言

微处理器由 Intel\text{Intel} 最早发明(CPU\text{CPU} 不是 Intel\text{Intel} 最早发明的)

位数只说明字长 不一定说明速度快慢

RAM (Ramdom Access Memory)\text{RAM (Ramdom Access Memory)} 随机存储器

随机不是位置随机 是随时访问

读取和写入所需时间和信息所在位置无关

一般 PC\text{PC} 在同一时刻只能存取一个特定的内存单元

Memory\text{Memory} 主存 在内存中 Cache\text{Cache} 高速缓存 Register\text{Register} 寄存器都在 CPU\text{CPU}

寄存器是中央处理器内的组成部分。寄存器是有限存贮容量的高速存贮部件,它们可用来暂存指令、数据和位址。

高速缓存 的目的是为了让数据访问的速度适应CPU的处理速度,其基于的原理是内存中“程序执行与数据访问的局域性行为”,即一定程序执行时间和空间内,被访问的代码集中于一部分。

闪存( Flash Memory\text{Flash Memory} )是一种长寿命的非易失性(在断电情况下仍能保持所存储的数据信息)的存储器由于其断电时仍能保存数据,闪存通常被用来保存设置信息,如在电脑的 BIOS\text{BIOS}

多任务系统可以使单个 CPU\text{CPU} 框架

在操作系统管理下,一个完整的程序在运行过程中可以被部分存放在内存中

输入设备

  • 键盘(Keyboard)
  • 鼠标(Mouse)
  • 手写笔
  • 触摸屏
  • 麦克风
  • 扫描仪(Scanner)
  • 视频输入设备
  • 条形码扫描器
  • ...

输出设备

  • 显示器(Monitor)
  • 打印机(Printer)
  • 绘图仪
  • 音箱
  • ...

网络 Internet

网络协议之所以由很多层不是为了兼容,而是根据网络分层模型来的。

分层模型在各个层之间都有连接且是双向的。

TCP/IP\text{TCP/IP} ( Transmission Control Protocol/Internet Protocol\text{Transmission Control Protocol/Internet Protocol}) 传输控制协议/因特网互联协议

TCP\text{TCP} :传输层 IP\text{IP}:网络层

每个主机都要有IP地址 即使注册了域名

Unicode\text{Unicode}(统一码、万国码、单一码)是一种通用的字符编码,它为世界上绝大部分语言设定了统一并且唯一的二进制编码,以满足跨语言、跨平台的文本交换。目前已经收录了超过十万个不同字符

ASCII\text{ASCII} (American Standard Code for Information Interchange\text{American Standard Code for Information Interchange}美国信息交换标准代码 ) 是基于拉丁字母的一套电脑编码系统,主要用于显示现代英语和其他西欧语言。它是现今最通用的单字节编码系统,并等同于国际标准 ISO/IEC 646\text{ISO/IEC 646}

W3C\text{W3C} (World Wide Web Consortium\text{World Wide Web Consortium})万维网联盟

Web\text{Web} 技术领域最具权威和影响力的国际中立性技术标准机构

GSM:全球移动通信系统,它的信令和语音信道都是数字式的,属于第二代移动通信技术。

TD-SCDMA:时分同步码分多址。中国提出的3G标准。

CDMA2000:是一个3G移动通讯标准。

WCDMA:一种3G蜂窝网络,利用码分多址复用。

SMTP是发送协议 POP/POP3是接收协议

IPv4 -> 3232

IPv6 -> 128128

语言相关

高级语言(High-level programming language\text{High-level programming language})相对于机器语言(machine language\text{machine language}),是一种指令集的体系。使用一般人易于接受的文字来表示。但高级语言还要转化成机器语言,才能让电脑运行,而这个转化的过程需要时间,但是汇编语言不用转化,因此运行效率更高

自然语言通常是指一种自然地随文化演化的语言;如英语、中文等

解释性语言编写的程序不进行预先编译,以文本方式存储程序代码。一般来说,现有的解释性语言都是采用的逐行解释一句,执行一句这样的方式来构建的。这样解释性语言每执行一次就要翻译一次,效率比较低

运行编译型语言是相对于解释型语言存在的,编译型语言的首先将源代码编译生成机器语言,再由机器运行机器码(二进制)。像 C/C++ 等都是编译型语言。

C 是面向过程语言 面向对象语言:C++simula 67SmalltalkEIFFELJavaC#

编译器:将一种语言翻译成另一种语言。工作流程为:源代码 (source code\text{source code}) → 预处理器 (preprocessor\text{preprocessor}) → 编译器 (compiler\text{compiler}) → 目标代码 (object code\text{object code}) → 链接器(Linker\text{Linker}) → 可执行程序 (executables\text{executables})

一些奖项

图灵奖 (A.M. Turing Award\text{A.M. Turing Award}) 由ACM于1966年设立

被誉为 "计算机界的诺贝尔奖" 奖励那些对计算机事业做出重要贡献的个人

约翰•冯•诺依曼奖 由 IEEE\text{IEEE}(电气和电子工程师协会)于 1990\text{1990} 年成立 表扬在计算机科学和技术上具有杰出成就的科学家

高德纳奖 (Donald E. Knuth Prize\text{Donald E. Knuth Prize}) 始于1996 1.5\text{1996 1.5}年颁发一次 .授予为计算机科学基础做出杰出贡献的人

1948\text{1948} 年,克劳德•香农(Claude Shannon\text{Claude Shannon})将热力学中的熵引入信息通信领域,标志着信息论研究的开端

1956\text{1956} 年,诺贝尔物理学奖授予肖克利(William Shockley\text{William Shockley})、巴丁(John Bardeen\text{John Bardeen})和布拉顿(Walter Brattain\text{Walter Brattain}),以表彰他们对半导体的研究和晶体管效应的发现

比赛创建时间
NOI\text{NOI}1984
IOI\text{IOI}1989
NOIP\text{NOIP}1995
APIO\text{APIO}2007

关于系统

UNIX 操作系统,是一个强大的多用户、多任务操作系统,属于分时操作系统

Microsoft Windows NT(New Technology)\text{Microsoft Windows NT(New Technology)}Microsoft19931993 年推出的面向工作站、网络服务器和大型计算机的网络操作系统,也可做 PC\text{PC} 操作系统

Netware\text{Netware}NOVELL\text{NOVELL} 公司推出的网络操作系统。最重要的特征是基于基本模块设计思想的开放式系统结构

DOS\text{DOS},磁盘操作系统,是个人计算机上的一类操作系统

Linux下可执行文件没有默认扩展名

文件名中不能包含< > / \ | : * ?

拓展名相关系统
.exeWindows\text{Windows}
.comMSDos\text{MSDos}

杂项

数据库存放数据的逻辑结构

数据库逻辑结构
层次型数据库(IMS\text{IMS})
关系型数据库(oracle ,SQL sever,Acess,My SQL,foxpro,sybase\text{oracle ,SQL sever,Acess,My SQL,foxpro,sybase})二维表
网状型数据库(DBTG\text{DBTG})链接指针

视频文件格式:MPEG, AVI, RM, ASF, WMV, MOV


进制 & 位运算 (动词应用)

HEXHexadecimal\text{Hexadecimal})—— 1616 进制

DECDecimal\text{Decimal})—— 1010 进制

OCTOctonary\text{Octonary})—— 88 进制

BINBinary\text{Binary})—— 22 进制

进制基数
十进制0 1 2 3 4 5 6 7 8 9
二进制0 1
八进制0 1 2 3 4 5 6 7
十六进制0 1 2 3 4 5 6 7 8 9 A B C D E F

转十进制

二进制数、八进制数、十六进制数转换为十进制数: 按权展开求和

二进制转十进制

栗子:

(1011.01)2=(1×23+0×22+1×21+1×20+0×1+1×22)10=(8+0+2+1+0+0.25)10=(11.25)10\begin{aligned}(1011.01)_{2} &= (1\times 2^3 + 0\times 2 ^ 2+ 1\times 2 ^ 1 + 1\times 2^0 + 0\times^{-1}+1\times 2^{-2})_{10}\\&=(8+0+2+1+0+0.25)_{10}\\&=(11.25)_{10}\end{aligned}

其他进制转十进制

按照每一位的权值算即可 (

十进制转二进制

整数就不断除以二, 然后最后按照余数从下往上写就可以辣qwq

(89)10=(1011001)2(89)_{10}=(1011001)_2
除数被除数余数
289-
244\rightarrow 1
222\rightarrow 0
211\rightarrow 0
25\rightarrow 1
22\rightarrow 1
21\rightarrow 0
-0\rightarrow 1

小数转二进制稍微有些麻烦qwq,我们需要每次乘以 22

×\times乘数二进制
20.625-
21.25\rightarrow 1
20.5\rightarrow 0
21.0\rightarrow 1
-0-

二进制 & 八进制

八进制二进制
0000
1001
2010
3011
4100
5101
6110
7111

二进制 \rightarrow 八进制

从小数点开始,整数部分向左、小数部分向右

33 位为一组用一位八进制数的数字表示,不足 33 位的要用 0 补足 33 位,就得到一个八进制数

八进制 \rightarrow 二进制

把每一个八进制数转换成3位的二进制数,就得到一个二进制数

栗子:

(114.514)8(114.514)_8 我们查表, 发现 001 001 100 101 001 100 于是, 最后的数字为 (1001100.101001100)2(1001100.101001100)_2

二进制 & 十六进制

十六进制二进制
0000
1001
2010
3011
4100
5101
6110
7111
81000
91001
A1010
B1011
C1100
D1101
E1110
F1111

二进制 \rightarrow 十六进制

从小数点开始,整数部分向左、小数部分向右,每 44 位为一组用一位十六进制数的数字表示,不足 44 位的要用 0 补足 44 位,就得到一个十六进制数

十六进制 \rightarrow 二进制

把每一个八进制数转换成 44 位的二进制数,就得到一个二进制数

位运算

带符号数的表示方法

带符号二进制数的表示方法:

带符号二进制数用最高位的一位数( 符号位 )来表示符号:00 表示正,11 表示负。

含符号位二进制数位数数值范围十六进制范围表示法
8位二进制数128+127-128 \to +12780H7FH80H \to 7FH
16位二进制数32768+32767-32768 \to +327678000H7FFFH8000H\to 7FFFH
32位二进制数2147483648+2147483647-2147483648 \to +214748364780000000H7FFFFFFFH80000000H\to 7FFFFFFFH

2、符号位的表示:最常用的表示方法有原码、反码和补码。

  1. 原码表示法:一个机器数 xx符号位有效数值 两部分组成,设符号位为 x0x_0xx 真值的绝对值 x=x1x2x3xn|x|=x_1x_2x_3\cdots x_n
  2. 反码表示法:一个负数的原码符号位不变,其余各位按位取反就是机器数的反码表示法。正数的反码与原码相同。 按位取反的意思是该位上是 11 的,就变成 00 ,该位上是 00 的就变成 11 。即 1=0,0=11=0, 0=1
  3. 补码表示法: 首先分析两个十进制数的运算:7838=4178-38=4179+62=14179+62=141. 如果使用两位数的运算器,做 79+6279+62 时,多余的 100100 因为超出了运算器两位数的范围而自动丢弃,这样在做 783878-38 的减法时,用 79+6279+62 的加法同样可以得到正确结果 模是一个计量系统的测量范围,其大小以计量进位制的基数为底数,位数为指数的幂。如两位十进制数的测量范围是 191\to 9,溢出量是 100100,模就是 102=100102=100,上述运算称为模运算

正数的反码是其本身

负数是除了符号位之外依次取反

正数的补码是本身

负数的补码 是 反码加1

下表列出 88 位二进制原码,反码和补码

真值原码反码补码补码
+127+127011111110 111 1111011111110 111 1111011111110 111 11117F7F
+39+39001001110 010 0111001001110 010 0111001001110 010 01112727
+0+0000000000 000 0000000000000 000 0000000000000 000 00000000
0-0100000001 000 0000111111111 111 1111000000000 000 00000000
39-39101001111 010 0111110110001 101 1000110110011 101 1001D9D9
127-127111111111 111 1111100000001 000 0000100000011 000 00018181
128-128自闭了自闭了100000001 000 00008080

简单的图论 (动词应用)

还要考什么手跑 dij 之类的(

  1. 完全图:任意两点均有连边的图,其中边数为 n×(n1)2n\times (n - 1) \over 2,其中 nn 为图中节点个数
  2. 连通图:任意两点之间都能直接或间接通过边到达的图
  3. 树:任意两点之间的简单路径有且仅有一条(或有 nn 个点,n1n-1 条边的连通图)
  4. 欧拉图:可以一笔画出来的图
  5. 一个图是欧拉图的充要条件(无向图):度为奇数点的点的个数 2\le 2

一些关于树的结论

  1. 高度为 nn 的满二叉树的节点数为 2n12^n - 1nn 个节点的完全二叉树高度为 ceil(logn)\text{ceil}(\log n) 我们注意到满二叉树第 ii 层的节点数为 2i12^{i - 1} 那么,前 nn 层节点数量就是 20+21++2n12^0 + 2^1 + \cdots + 2^{n - 1}2n12^n - 1 (等比数列)
  2. 先序遍历、中序遍历、后序遍历这个只要给出了中序遍历和其他一个遍历就能确定这课二叉树(
  3. 完全二叉树 对满二叉树的结点进行连续编号,约定编号从根结点起,自上而下,自左至右。深度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树编号从1至n的结点对应时,称为完全二叉树

数学 (动词应用)

常见题型 & 公式

nn 条直线最多将平面分成多部分?

f(n)=f(n1)+n=n(n+1)2+1f(n)=f(n-1)+n=\frac{n*(n+1)}{2}+1

nn 个平面最多将空间分成的部分

g(n)=g(n1)+f(n1)=n3+5n+66g(n)=g(n-1)+f(n-1)=\frac{n^{3}+5n+6}{6}

nn 条封闭曲线最多将平面分成的部分

f(n)=f(n1)+2(n1)=n2n+2f(n)=f(n-1)+2(n-1)=n^{2}-n+2

nn 条折线最多将平面分成的部分

f(n)=f(n1)+2(2(n1)+1)1f(n)=f(n-1)+2(2(n-1) + 1) - 1

nnZ 型折线最多将平面分成的部分

f(n)=f(n1)+3(3(n1)+1)2f(n)=f(n-1)+ 3(3(n-1)+1)-2

斐波那契数列

f(n)=f(n1)+f(n2)=15((5+12)n(512)n)f(n)=f(n-1)+f(n-2)=\tfrac{1}{\sqrt{5}}((\tfrac{\sqrt{5}+1}{2})^{n}-(\tfrac{\sqrt{5}-1}{2})^{n})

卡特兰数

f(0)=1,f(1)=1f(n)=i=0n1f(i)f(n1i)f(0)=1,f(1)=1\rightarrow f(n)=\sum_{i=0}^{n-1}f(i)f(n-1-i)

完形填空

做完题之后一定要整理思路检查一次!

因为一个陌生的题当我们模拟完之后就比较熟悉,这个时候重走一遍不仅轻车熟路,更可以找到第一次模拟疏忽的地方,避免错误

注意对称写代码,以及造个小数据带进去试试

填程序空的时候注意不要被给的代码带歪了。。。因为给的代码都很奇怪,到最后自己可能被带的也填了奇怪的东西。。。要按 目前需要做什么 来填,比如填取最优什么的,根据你自己对算法的理解,结合上下文填空。我最后一个空就因为给的代码太简单导致我以为简单到不用更新最优解。。。其实按这个算法的流程来说就应该是取最优,不能被带歪了。。。

注意边界问题,代进去看一看是否能取到边界,很多时候初始化的值和题目描述是有点不符的,特别是最后一个空,一般是某个指针 1-1 ,这个 1-1 就是坑人的。。。而且经常有把全局变量初始化为 00 的情况,得仔细看看符不符合,若是一个空填上之后会越过边界,比如什么 i+pi + p 发现会超过 nn 什么的,可能是填错了,做这种题的技巧就是尽量去填给你的代码中本来就有的,有一些是形式上具有对称性,还有一些是比较特殊的,定义了一个 end2=nend2 = nend2end2 始终没改变过,所以填 nnend2end2 都一样,但是答案还是写了 end2end2 。。。(13年填空1)

注意填空的对称性,比如要判断两个变量哪个先写到if里面,变量名的顺序都是能从前的代码里能看出的

初赛代码经常有 for 不打花括号什么的奇怪操作,有时候会影响到理解(比如说一句要填的空在不在循环里面什么的)

1
2
3
4
for (int i = 1; i <= n; i++)
xxxxx;
for (int j = 1; j <= n; j++) xxxxx;
QAQ;

如果说填代码的时候,显然会算的超过题目边界,即使这样没多大影响,估计也是填错了,比如 1515 年最后一个填空题最后一个空,显然 0022 是需要遍历的,据此可得 i1i-1i+1i+1,并不是说无所谓就不用遍历。。。

如果看到一个很奇怪的地方, 不要轻易地认为是出题人故意写出来坑人什么的,除非真的能确定,“聪明反被聪明误” 例如 1010 年完型 T1T1 那个 swapswap ,因为传了个指针我就以为这是个无效的操作,但其实我根据 swapswap 这个名就该明白这是出题人干扰我的,如果不交换这个程序输出什么啊。。。

阅读理解

好好读题好好读题好好读题,从题干中挖掘一些信息!做题的时候一定要专注冷静认真,别再犯低级错误了!

注意阅读程序的时候很有可能坑人,比如数组下标从 00 开始存

RE: 从零开始的数组下标

先找规律,找到解决小范围问题的办法,然后多造几个数据观察一下有什么关系,最好先读一遍代码看看是做什么的,再去模拟

解决那种很难思考的递归程序要么猜那个程序是干什么的,要么暴力算

但是暴力算也有技巧,比如不要用深度优先的方式去展开搜索树,很容易乱,用广搜的方式展开搜索树有条不紊,还容易看出规律。并且记着加一些记忆化,算的次数越少越不容易错!(1717 年阅读 T1T1

总的来说就是深度优先发现规律,广度优先计算结果

例如 1010 年阅读 T4T4,本质是博弈,但是其实挺难看出来的,如果用广度优先的方式展开估计是算不完的,但是如果以深度优先的方式,找最特殊的,很容易就会发现 r(6)=1,r(7)=1r(6) = -1,r(7) = 1,然后就会发现规律

但是因为题型不定,有时深搜反而不好找规律,灵活变换才是通法

明确数组代表的含义 后再做一遍

有的题注意 把过程图像化 ,比如 1717 年阅读程序最后一题

写递归的时候注意写下各种状态参量,比如 i=1i = 1q=3q = 3 什么的,不要怕麻烦,也别急着返回,把第 00 层递归写出来

比如 f(0,1,6)f(0,1,6) f(0,2,6)f(0,2,6) 这样的,一目了然,不容易错

千万不要“松懈”,有疑惑的地方一定要抓住然后重新推导解决疑惑,好多次我犯了明显的错误还是因为懒得推放过了不大明确的地方,还有是求到最后一步不想干了,直接胡想答案上去(潜意识中),也没考虑其正确性,从第一步到最后一步都要认真的做,然后回头再检查一遍,看得清楚一点!

关于心态

不要一个题做不出来就郁闷,也不要一个题轻易看出解法就十分得意,这个时候往往容易掉进坑里,比如13年填空最后一题第三个和第四个,我根据我所谓的对称性,想都没想,类比上面的代码反着写了一波,然后发现不用反着写,因为他这两部分形式上是一样的。。。检查的时候还没发现这个问题(当时心态飘了),至少也得仔细看看思考一下吧。。。


参考资料:

  1. NOIP 初赛整理 - By Zolrk
  2. 关于NOIP初赛的一些错题和知识点整理 - By CalvinJin_
  3. noip初赛复习(全) - 飞翔狼人
坚持原创技术分享,您的支持将鼓励我继续创作!