版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/Njhemu/article/details/101868253
快要CSP2019初赛了，再次总结一些初赛知识及技巧，供自己与大家复习。

一、计算机理论类：

1、单位：位（bit），字节（Byte），以及许多字节的缩写：KB、MB、GB、TB、PB，更大的应该不会考了。换算关系为：

1 Byte = 8 bit
1 KB = 1024 Byte
1 MB = 1024 KB
1 GB = 1024 MB
1 TB = 1024 GB
1 PB = 1024 TB
注：10TB大约为正常人脑储存量。

2、编程语言：大致有两个分法。

面向对象：C++、Java、EIFFEL、Python等

面向过程：C、Fortran等

注：Pascal似乎既可以面向对象也可以面向过程。

编译性语言：C、C++、Pascal、Delphi等

解释性语言：Java、VB、Python、Ruby、Matlab等

注：编译型语言指直接将源代码翻译成机器语言的语言，解释语言则是一行一行翻译。

3、计算机系统组成：

一个图可以展现所有的细节了，图片来自互联网：

需要记忆的知识点：硬件组成：运算器、控制器、存储器、输入输出设备。

CPU包括运算器、控制器、存储器。

存储器包括内、外存储器。

断电后能保存数据：ROM（只读存储器）、硬盘

断电后不能保存数据：RAM（随机存储器）、CPU、显卡

4、计算机发展历史：电子管计算机、晶体管计算机、中小规模集成电路计算机、大规模集成电路计算机。

注：世界上第一台计算机ENIAC是由美籍匈牙利科学家冯诺伊曼设计，其被称为计算机之父，另一个计算机大神是英国科学家阿兰图灵，被称为人工智能之父。图灵奖是计算机领域最高奖项，中国只有一位科学家即姚期智先生得此殊荣。

5、CCF宣传题：关注CCF官网即可。如考试要求等。

二、算法类

1、进制：会比较各种进制下个数的大小，会即可。如十进制下的a转化为n进制，每次使m=a%n，a/=n，一直到零，最后将每个m从后往前连起来便是n进制下的a。

2、二进制：符号数有三种表示方法：原码、反码与补码。原码指原二进制码，反码指正数下的原码与负数下将原码除符号位以外每一位的01取反。特别注意的是，计算机中的最后一位表示的是数字的符号，1表示负数，0表示正数。

补码就比较复杂了，正数及0为其原码，负数则‘取反加1’，即将其置为反码后加1即可。

另外，反码与补码是专门用来处理二进制下正负数加减问题，反码会产生0与-0的问题，故舍去了。

一篇博文：https://www.cnblogs.com/author/p/8954127.html详细解释了反码与补码，建议参考。

3、时间复杂度计算：一般都是递推形式，自己算一算就行，实在不行就暴力打表找规律。

4、树：性质：是连通图且若有n个定点则有n-1条边。似乎挺好证明：选定一个根节点，此时0条边，此后每多一个点就连一条边，肯定是n-1条边。

无环(废话)

两个节点间有且只有一条简单路径。

在完全二叉树中第n个顶点的左儿子为2n，右儿子为2n+1，完全n叉树以此类推，当然只适用于有序树。

初赛中树的题似乎暴力打表都能解决，不能解决的都能算出来。

另外树的遍历中，DFS是沿着儿子搜索，BFS是同辈间每层逐个搜索。先序遍历即指DFS序，中序遍历先访问左儿子再访问根节点再访问右儿子，后序则是先访问左儿子再访问右儿子再访问根节点，注意以上遍历顺序是在每一个子树中进行在递归上更大的子树。详细参考资料。推荐：https://blog.csdn.net/cocoiehl/article/details/80959143，有图详细易懂。

树的种类：大约分为有序树（节点编号与顺序有关）、无序树（节点编号与顺序无关，又称自由树）、完全树（仅适用于n叉树，表示每层从左到右一个一个排下去）、满n叉树（仅适用于n叉树，即每层都排满的树，若有m层（m>1），则一定共有1+n+n2+n3+…+n(m-1)，特殊的，满二叉树***有2m-1个顶点）、哈夫曼树（带权路径最短的二叉树，又称最优二叉树）等。

5、图论：概念：

有向图：每条路径都是单向的的图。

无向图：每条路径都是双向的图。

度数：无向图中每个顶点所连边的边数。

出度：有向图中每个顶点出边边数。

入读：有向图中每个顶点入边边数。

强连通：若有向图中有两点能互相到达则称这两点强连通。

强连通图：任意两点强连通的有向图称为强连通图。

强连通分量：任意有向图的极大强连通子图成为强连通分量。

算法：

初赛中应该也就考最短路径和最小生成树了吧。

最短路径有Floyd、Dijkstra、SPFA等，可参考博文：https://blog.csdn.net/Njhemu/article/details/81351849、https://blog.csdn.net/Njhemu/article/details/79779361、https://blog.csdn.net/qq_41758381/article/details/86570358

最小生成树有Prim、Kruskal等，可参考博文：https://blog.csdn.net/Njhemu/article/details/80159212、https://blog.csdn.net/Njhemu/article/details/82930572

6、基本算法：

二分、分治、高精、动态规划、差分、搜索、背包、图上各种算法、KMP、快速幂及一些基本数论、概率等，当然还有模拟与打表。

三、数学题部分

初赛中会有十分的数学题，一定要对。要掌握的知识有：排列组合、基本代数、基本数论、位运算、逻辑推理、暴力打表等（似乎不会考几何）。

建议把每年的两道数学题做一遍，洛谷有题中会有2007至今的所有初赛卷附答案。附上地址：洛谷有题

四、看程序写结果

1、暴力模拟：第一、二题甚至第三题都可以这样死做出来，注意不要算错，建议考试时画格子记录好每个变量的取值。

2、找规律：这也很重要，如果数据很大只能找规律时可使用类似于数学归纳法的方法，在自造几个较小数据得出答案在爆找规律。

3、读懂程序：大佬才能做到，且初赛中时间有限，但若一眼看出来这题也就秒掉了，另外，关注变量名、函数名对理解程序有好处。

注：这道题一题8分份量极大，一定要做。

五、补全程序

这就主要看实力了，但有几条技巧：

1、注意所给程序的变量名与函数名，如dp，ans等，会很有好处。

2、对照上下程序，如分治、DFS前后会有类似的语句出现。

3、思考自己会使用什么方法通过此题，不要想卡常、骗分，直接想正解。

大约就这些了，如有补充可在评论区指出，谢谢各位了。

最后祝大家考试顺利。
————————————————
版权声明：本文为CSDN博主「Njhemu」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/Njhemu/article/details/101868253