版权声明:本文为博主原创文章,遵循 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