NOIP(CSP)初赛知识总结

mac2022-06-30  113

快要CSP2020初赛了,再次总结一些初赛知识及技巧,供自己与大家复习。

一、计算机理论类:

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官网即可。如考试要求等。

6、(2019.10.18更新)计算机网络:TCP/IP是网络的一组通信协议。

网络主要功能:资源共享、信息传递、分布处理、综合信息服务。

网络分类:局域网(LAN)、城域网(MAN)、广域网(WAN)。广域网有多种拓扑结构(星形、总线型等),一般关于网都是网状型(不规则)。

体系结构:分为4层:应用层、传输层、国际互联层、网络接口层(一说5层,多一个物理层,大家自行度娘)。

IP地址:形式:a.b.c.d,其中a、b、c、d是0~255中的整数。注意:10.0.0.0~10.255.255.255、172.16.0.0~172.31.255.255、192.168.0.0~192.168.255.255全部为私有,其他为公用地址。

分为三类私用地址:A类、B类与C类:

A类:10.0.0.0~10.255.255.255             B类:172.16.0.0~172.31.255.255           C类:192.168.0.0~192.168.255.255

7、(2019.10.18更新)Internet知识:服务:WWW(万维网)、E-mail(电子邮件)、FTP(文本传输协议)、Telnet(远程登录)

注:WWW网页用超文本标记语言(即HTML)在超文本传输协议(即HTTP)下支持运行的。电子邮件中:传输协议(SMTP)、扩展协议(MIME)、收邮件(POP3)协议、邮件访问协议(IMAP)。

8、B/S(Brower/Server)服务与C/S(Client/Server)服务:前者通过浏览器进行文件传输,后者通过服务器进行传输。

二、算法类

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个顶点的左儿子为2*n,右儿子为2*n+1,完全n叉树以此类推,当然只适用于有序树。

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

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

树的种类:大约分为有序树(节点编号与顺序有关)、无序树(节点编号与顺序无关,又称自由树)、完全树(仅适用于n叉树,表示每层从左到右一个一个排下去)、满n叉树(仅适用于n叉树,即每层都排满的树,若有m层(m>1),则一定共有1+n+n^2+n^3+...+n^(m-1),特殊的,满二叉树中共有2^m-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、快速幂及一些基本数论、概率等,当然还有模拟与打表。

三、数学题部分

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

附一些常用公式定理供大家复习:

1、P(n,k)=n!/(n-k)!,C(n,k)=n!/[k!*(n-k)!],P为排列,C为组合。

2、容斥原理https://blog.csdn.net/m0_37286282/article/details/78869512

3、Nim游戏:记一下结论吧:有n个石头,每次最少取一个,最多取m个,取完最后一个石头人获胜,则n%(m+1)=0是先手必败,否则必胜,策略是每次取走当前石头数%(m+1)的石头(假Nim游戏)。真Nim函数:若干堆石子,每次从某对中随机取随机取石子,最后取完的人获胜(每堆石子个数为a1,a2...an),则a1 xor a2 xor ... xor an>0则必胜,否则必败。具体参看博客https://www.cnblogs.com/yifusuyi/p/9572773.html

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

四、看程序写结果

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

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

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

注:这道题一题8分份量极大,一定要做。

五、补全程序

这就主要看实力了,但有几条技巧:

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

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

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

 

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

最后祝大家考试顺利。

 

 

 

 

最新回复(0)