NOIP2012
CPU是由硅制成的。
ENIAC属于电子管计算机。
CPU 的寻址空间 \(=2^{位数}\) 位。
3G 移动技术：CDMA 系列和 Wimax。
时间复杂度的表示：
\(O(f(n))\) 表示当程序的规模大于某个常数时，总是有一个常数 \(S\) 使得 \(S \times f(n) \ge\) 实际用时，即时间复杂度上界。
\(\Theta(f(n))\) 表示当程序的规模大于某个常数时，总是有两个常数 \(S\) 和 \(T\) 使得 $S \times f(n) \ge $ 实际用时 \(\ge T \times f(n)\)，即渐近时间复杂度。
\(\Omega(f(n))\) 表示当程序的规模大于某个常数时，总是有一个常数 \(S\) 使得 \(S \times f(n) \le\) 实际用时，即时间复杂度下界。
E-mail 服务协议有 SMTP 与 POP3。
NOIP2013
香农提出了信息熵的概念。
IPv4 使用32位地址，IPv6使用 \(128\) 位地址。
GBK 2312 是国标编码，用于表示汉字。
BIG5 是五笔编码，用于表示五笔拼音。
Unicode 是最大最全的国际文字编码。
强制转换类型或者 \(double\) 爆精度的舍去：符号位不变，只会丢弃数据，因此可能变大也可能变小。
主定理用于计算递归的渐近时间复杂度，见66行的运用。
P 类问题：
批注：多项式时间复杂度：数据的规模在时间复杂度式子中占底数位置的复杂度。如 \(O(n^2),O(n^3ln(n))\)。而 \(O(a^n),O(n!)\) 就不是多项式复杂度。
标准定义：可以用确定型图灵机在多项式时间内解决的问题。
人话：你家电脑能在计划时间内跑出来的。
NP 类问题：
标准定义：用不确定的图灵机以多项式时间界可解的问题称为NP类问题。
人话：你家电脑得爆搜的问题。
也就意味着，P 类问题可以在有限的时间和有限的空间内跑出程序，而当规模增加，想要跑出 NP 类问题是几乎不可能的。所以 P 类问题全部属于 NP 类问题。
NOIP2014
C++ 是面向对象的高级语言。
FORTRAN 是面向科学计算的高级语言。
Basic 是面向对象的程序设计语言。
TCP 协议属于传输层协议。
IPV4它只有4段数字，每一段最大不超过255。所以，当一个地址的任意段表示的数大于 \(255\) 时它就显然不合法。
编译器的主要功能是将源程序翻译成指令。
要求最小的比较次数，我们显然应当对原序列分治。于是考虑在序列上建出线段树，对于第一次，我们只需要 \(n\) 次比较就可以求出两数里的最大值与最小值。对于接下来的比较，每次需要对两个区间的最大值与最小值都做一次比较，于是次数就是:
通过等比数列求和公式可以求得该式的答案为 \(3 \times n-2\)。
\(∨\) 表示或，\(∧\) 表示与，\(-\) 表示非。
Oracle 是神谕全球最大的信息管理公司。
NOIP2015
链表的地址连续或者不连续都可以。
根据No_fishing需求再讲一遍前缀后缀相关知识。
先序遍历：在一颗树上按照根左右的顺序取出的序列就是这棵树的先序遍历。
如图。
开始时我们在 \(1\) 处。
先取出根，序列变为 {\(1\)}。
然后向左边走，此时根为 \(2\)，取出根，序列变为 {\(1,2\)}。
此时的根节点没有左儿子，于是我们向右走，走到位置 \(4\)，取出根，序列变为{\(1,2,4\)}。
然后向左边走，走到 \(7\)，序列变为{\(1,2,4,7\)}。
遍历 \(7\) 的左右儿子，序列变为 {\(1,2,4,7,12,11\)}。
然后一直回退，以此类推，这棵树的先序遍历应当为 {\(1,2,4,7,12,11,3,5,6,10,8,9\)}。
中序遍历：在一棵树上按照左根右的顺序取出的序列就是这棵树的中序遍历。
具体地说，就是把上文的先取出根节点的顺序改为先向右边下去，走完回退时就将根节点加入序列。
上图的中序遍历应为 {\(2,12,7,11,4,1,6,5,10,3,8,9\)}。
后续遍历：在一棵树上按照根左右的顺序取出的序列就是这棵树的后序遍历。
前缀表达式：一棵表达式树的先序遍历就是它的前缀表达式。
通过前缀表达式建树：由于前缀表达式的顺序是根左右，所以我们应该将最先遇到的东西放在根的位置，比如说：
表达式:\(\times +1 2 3\)
一开始我们在根处，由于根左右的顺序，我们先将 \(\times\) 放在根部，然后我们向左边行走，将 \(+\) 放在 \(\times\) 的左儿子处，然后将 \(1\) 放在 \(+\) 的左儿子处，由于 \(1\) 是数字，我们此时开始回退，将 \(2\) 放在 \(+\) 的右儿子处。同理回退，在 \(\times\) 的右儿子处放下 \(3\)，建树完成。
通过后缀与中缀的建树同理。
哈夫曼算法：每次取出权值最小的两棵树进行合并，这样得到的树一定有着最优的效率。由于每次的操作相同且可以划分为子问题，是贪心做法。
所有的视频格式。
NOIP2016
主定理的示范运用：16题：
由于 \(log_{4}^{2}n= \sqrt{n}\)，所以取主定理中的第二种情况，在 \(\sqrt{n}\) 的基础上乘一个 \(log\)，时间复杂度为 \(\sqrt{n}log(n)\)。
可以将单个计算机接入到计算机网络中的网络接入通讯设备是网卡。
从2022年起，NOIP 竞赛将不再支持 Pascal 语言。
补码表示的数：是该数保留符号位后取反得到的结果。