初赛复习提纲
一、 单项选择题（15*1.5=22.5）
NOIP官网的基础知识【1题】
NOIP官网最近热点问题：
? NOIP2018二试时间：2018年11月11日（周日），提高组8:30-12:00。
? CCF官网近日进行了一次改版新版上线后，原版网址的地址改为http://history.noi.cn
? 7月16日-22日，由中国计算机学会（CCF）主办，长沙市雅礼中学承办的第35届全国青少年信息学奥林匹克竞赛（NOI2018）在星城长沙隆重举行。（点燃梦想，燃烧激情——NOI2018在长沙顺利举行）
? NOI科学委员会(Scientific Committee，简称SC)是CCF设立的负责NOI竞赛技术工作的机构
? 2020年开始，除NOIP以外的NOI系列其他赛事（包括冬令营、CTSC、APIO、NOI）将不再支持Pascal语言和C语言从2022年开始，NOIP竞赛也将不再支持Pascal语言。即从NOIP2022开始，NOI系列的所有赛事将全部取消Pascal语言。
? 从2018年起，CCF奖项推荐的有效期延长至三年，
? CCF设立中国计算机学会奖（简称CCF奖）。CCF奖包括学术（技术）、教育、产业和服务四类。（CCF奖励条例） P.S.推荐大家看看《CCF奖励条例》。CCF奖有：CCF终身成就奖、CCF王选奖、CCF海外杰出贡献奖、CCF优秀博士学位论文奖、CCF-IEEE CS青年科学家奖、CCF夏培肃奖（备注：女性专属）、CCF科学技术奖、CCF杰出教育奖、CCF优秀大学生奖、CCF计算机企业家奖等等
? NOI官网(www.noi.cn)和CCF官网(www.ccf.org.cn)
数据结构（树、图、队列、栈、数组等）【5题】
二进制（原码、补码等）【1题】
? 简单数学题【5题】（组合数、算日期等）
? 算法篇：
排序算法（希尔排序（不稳定）、冒泡排序（稳定）、堆排序（不稳定）、快速排序（不稳定）选择排序（不稳定））【2题】
排序算法稳定性是定义是这样的假设元素s[i]=s[j]而i<j在排序而成的序列s’中元素s[i]必须排在s[j]的前面。
而稳定性和退化之间没有必然的关系。
dp算法（简单递推公式）【1题】
? 计算时间复杂度【1题】
Master定理：
定义T（n）为算法的复杂度对于规模为n的问题可以分成a个规模为n/b的子问题，其他运算的复杂度为f(n)，crit为一个由a和b决定的数
? F(n)=O(n^c)且c<crit时
? 若存在一个非负数k，使得 那么
和计算机相关的：奖项（图灵奖、中国计算机学会创新奖、CCF的出版物、信息学奥林匹克（NOI）、王选奖、计算机先驱奖、D-Link荣膺PC Magazine杰出技术奖）微软公司出版的软件（Acess、VB、power point、word、excel）CPU（等零部件）IP地址（0<=x<=255）
几个协议（TCP/IP、FTP、Email、HTTP（超文本传输协议）、SMTP、POP3）
计算机相关【好多题】：
第一代（1946~1958） 第二代（1958~1964） 第三代（1964~1975） 第四代（1975~至今）
核心部件 电子管 晶体管 中小规模集成电路 大/超大规模集成电路
内存 汞延迟线 磁芯存储器 半导体存储器 半导体存储器
外存 穿孔卡片、纸带 磁带 磁带、磁盘 磁盘、光盘
速度（指令数/秒） 几千条 几百万条 几千万条 数亿条
还有关于计算机中各存储单位的进位关系：
1TB=1024GB，1GB=1024MB，1MB=1024KB
1KB=1024B，1B（字节）=8bit（位）
第一种抽象计算模型：图灵机
冯诺依曼提出的：存储程序在存储器中、运算器为中心论、二进制思想
反吗补码：
原码：符号位为0表示正数，符号位为1表示负数，其余各位表示数值部分。
反码：对于正数，它的反码与原码相同，对于负数，反码符号位与原码相同，其余的按位取反
补码：对于正数，它的补码与原码相同，对于负数，先得到相应的反码，并在此基础上加1。
P.S.原码和反码0的表示方法有两种。这也就是为什么要引进补码的原因。
P问题和NP问题和NPC问题（高频）【3times】
P问题：P问题是具有多项式算法的判定问题。这里的P代表Polynomial。P问题就是可以有一个确定型图灵机在多项式时间内解决的问题。即目前那些存在O(n), O(nk), O(nlogn)等多项式时间复杂度解法的问题。比如排序问题、最小生成树、单源最短路径。直观的讲，我们将P问题视为可以较快解决的问题。
NP问题: 即多项式复杂程度的非确定性问题。简单的写法是 NP=P？，问题就在这个问号上，到底是NP等于P，还是NP不等于P。可以在多项式的时间里验证一个解的问题
NPC问题：是NP问题的一部分，满足NP问题的所有条件和结论，额外的这些问题中任何一个如果存在多项式时间的算法,那么所有NP问题都是多项式时间可解的。NP中的某些问题的复杂性与整个类的复杂性相关联.这些问题中任何一个如果存在多项式时间的算法,那么所有NP问题都是多项式时间可解的.这些问题被称为NP-完全问题(NPC问题)。
二、 问题求解（5*2=10）
数学题：找规律、排列组合、平面几何、集合、容斥原理、最优解问题、博弈论、简单递推
基本算法：最短路、拓扑排序、DP、网络流（最小割）
数据结构：图、栈、队列、二叉树、
【常考例题】
寻找假币问题（判定树、LOG3（N）上取整）
取石子游戏（主要思想是分析先手者有无必赢策略，恰好两个人之和是K的倍数）
关于xor运算 如果两人轮流在n堆石子中去取，取最后一棵的为胜者，那么吧n堆石子xor起来为0那么先取出者无必胜策略。
容斥原理：
抽屉原理（鸽巢问题）
递推问题：
1． 前缀和、等差数列、等比数列 an=a1q^(n-1) Sn=a1(1-q^n)/(1-q)
2． 错位排列 Fn=(n-1)(F(n-1)+F(n-2))
3． 第二列斯特林数（含n元素集合划分成k个非空集合）
S(N,K)=S(N-1，K-1)+K*S(N-1，K) pascal三角 (i,j)左上角加上j*正上方元素
4.汉诺塔问题 F[n]=2F[n-1]+1 F[1]=1
5.平面分割问题
线分平面 n(n+1)/2+1 二次函数
折线分平面 (n-1)(2n-1)+2n 二次函数
封闭曲线分平面 n^2-n+2 二次函数
6.卡特兰数列 Hn=C（n,2n）/(n+1)
【方法】
尝试法解题
数学归纳法解题
三、 阅读程序题（4*8=32）
简单送分题：一定要好好读程序，谨慎写答案。（NOIP2016 逗号惨案）
循环结构题：关键是这种题一定是有规律的，你要根据小输入（题目给的或者你自己构造的）来猜测规律然后求解。（小样例最重要猜规律）
递归搜索题：分析程序想干什么暴力的话就是画树形图分析每一层。
四、 程序填空（2*14=28）
而在初赛的这个地方，你必须完全按着写代码的人的思路来。不过幸好，出题人心情好会出模板题。在这类题型上，就是要注意多读几遍题目和程序，不要急于去填空。不过其实有些空是可以猜出来的。
后记：这里把大篇幅的内容放在了选择题上，并不代表后面的三道题型不重要，得选择题者得天下，注重选择题的分数是有必要的NOIP初赛的下线率是比较大的，希望做好这样的思想准备。在NOIP2018初赛还有若干天这个节点，我在此写这篇文章，目的是提醒参加NOIP的OIers初赛这个东西必须要过，要花大力气，顺便奠一下NOIP2016（pj）的重大初赛失误，希望NOIP2018能过发挥的更好吧。
By ljc20020730 HGOI
Date：2018 09 07 21:17 完稿
原文：https://www.cnblogs.com/ljc20020730/p/9607112.html