NOIP初赛基础知识

从今天起至10月11日，持续连载。

关于计算机

ENIAC

• 出现于1946年。
• 是最早的计算机。
• 是电子管计算机。

其他

• 阶码，即浮点数的指数部分。
• IPv6是128位的。
• 求补码：二进制下：各位取反再加1 或 把原码减1再取反。

关于算法

各种排序的时间复杂度

• 快速排序：$O(nlogn)$，最坏为$O(n^2)$。
• 冒泡排序：$O(n^2)$。
• 归并排序：$O(nlogn)$。
• 计数排序：$O(n)$。
• 插入排序：$O(n^2)$。

关于树

• 完全二叉树 vs 满二叉树：完全二叉树最后一层不一定满。
• 前序遍历：中左右；中序遍历：左中右；后序遍历：左右中。
• 节点数为n的二叉树上，有两个节点的至多有$[(n+1)/2]$个。
• 节点数为n的完全二叉树有$log(n)$层，节点序号大于$n\ div\ 2$的为叶节点。

计算机史

• 熵在1948年由克劳德·香农引入信息通信领域。

杂项

3G网络

• 三种标准：CDMA2000、WCDMA、TD-SCDMA。

4G网络

• 类别：TD-LTE和FDD-LTE。

N/NP问题

• P：复杂度类P包含所有那些可以由一个确定型图灵机在多项式表达的时间内解决的问题。
• NP：是指可以在多项式时间内被非确定机(他可以猜,他总是能猜到最能满足你需要的那种选择,如果你让他解决n皇后问题,他只要猜n次就能完成----每次都是那么幸运)解决的问题。

NOIP申诉条件（操蛋去年居然考了！）

1. 非公示期限内提出的申诉，不予受理；
2. 与个人名次、他人成绩和他人名次有关的申诉，不予受理；
3. 未通过NOI科学委员会提交的、来自非正规渠道的申诉，不予受理；
4. 因操作系统、语言环境的具体差异引起成绩变动的申诉，不予受理；
5. 对使用随机数和随机算法的程序的申诉，不予受理；
6. 发布成绩与选手使用非规范环境和数据、参数评测出的成绩不同，并因此提出的申诉，不予受理；
7. 在与标准测试环境相同的机器上，自测用时超过题目时限的5%，并由此提出的申诉，不予受理；
8. 以修改过的程序或答案为依据的申诉，不予受理；
9. 因选手错误而导致答案文件名错误，或者源文件存放目录结构不规范，且所提出的申诉与此有关的，不予受理。
10. 未描述清楚自测状况，如“与老师评测有出入”，“感觉评测结果有错”等，不予受理。

其他

• NOIP官网：http://www.noi.cn/。
• 中国互联网信息中心的缩写：CNNIC。