初赛复习知识点

-

• 初赛复习知识点
• • @[TOC](-)
  • 一些盆友的初赛总结
  • 逻辑运算
  • 计算机基本结构
  • 卡特兰数
  • 二叉树的基本概念
  • 遍历二叉树
  • 二叉树的性质
  • 图的一些定义和概念
  • 关于 ∏ \prod ∏
  • 十进制转二进制（小数部分）
  • NOI竞赛历史
  • 原码反码补码
  • 因特网提供的服务
  • 整形数据与字节
  • 链表

一些盆友的初赛总结

(T)JH姐的初赛总结

LTH 大 佬 {\color{white}大佬} 大佬的初赛提纲¿

逻辑运算

& (并且) 有false则false
| (或者) 有true则true
! (非) 非false则true，非true则false
^ (异或) 相同为false，不同为true
&& (短路与) 有false则false,若&&左边表达式或者值为false则右边不进行计算
|| (短路或) 有true则true,若||左边表达式或者值为true则右边不进行计算

计算机基本结构

ROM（只读存储器）只能读出无法写入信息。信息一旦写入后就固定下来，即使切断电源，信息也不会丢失，所以又称为固定存储器
RAM（随机存取存储器）即一旦断电所存储的数据将随之丢失。RAM在计算机和数字系统中用来暂时存储程序、数据和中间结果
美国AMD半导体公司专门为计算机、通信和消费电子行业设计和制造各种创新的微处理器

卡特兰数

卡特兰数 C(2n,n)/(n+1)

h n = 1 n + 1 ( 2 n n ) h_{n}=\frac{1}{n + 1}\begin{pmatrix}2n\\n \end{pmatrix} hn​=n+11​(2nn​)

二叉树的基本概念

∅表示空二叉树
O表示仅有根结点的二叉树

遍历二叉树

前序遍历（根左右）
中序遍历（左根右）
后序遍历（左右根）

二叉树的性质

在二叉树的第i层上最多有 2 i − 1 2^{i-1} 2i−1个结点( k > = 1 k>=1 k>=1)
深度为k的二叉树至多有 2 k − 1 2^{k-1} 2k−1个结点( k > = 1 k>=1 k>=1)
对任意一棵二叉树，如果其叶结点数为 n 0 n_{0} n0​，度为2的结点数为 n 2 n_{2} n2​则一定满足： n 0 = n 2 + 1 n_{0} = n_{2} + 1 n0​=n2​+1
具有n个结点的完全二叉树的深度为 f l o o r ( l o g 2 n ) + 1 floor(log_{2}^{n}) + 1 floor(log2n​)+1
对于一棵n个结点的完全二叉树，对任一个结点(编号为i)，有两种情况
1、如果 i = 1 i=1 i=1，则结点 i i i为根，无父节点；如果 i > 1 i>1 i>1，则其父节点编号为 i / 2 i/2 i/2
如果 2 ∗ i > n 2 * i > n 2∗i>n，则结点i无左孩子(当然也没右孩子，结点 i i i为叶结点）;否则左孩子编号为 2 ∗ i 2 * i 2∗i
2、如果 2 ∗ i + 1 > n 2 * i + 1 > n 2∗i+1>n，则结点 i i i 无右孩子；否则右孩子编号为 2 ∗ i + 1 2 * i + 1 2∗i+1

图的一些定义和概念

有向图：图的边有方向，只能按箭头方向从一点到另一点
无向图：图的边没有方向，可以双向
结点的度：无向图中与结点相连的边的数目，称为结点的度
结点的入度：在有向图中，以这个结点为终点的有向边的数目
结点的出度：在有向图中，以这个结点为起点的有向边的数目
权值：边的“费用”，可以形象地理解为边的长度
连通：如果图中结点U,V之间存在一条从U通过若干条边、点到达V的道路，则称U、V是连通的
回路：起点和终点相同的路径，称为回路，或“环”
完全图：一个n阶的完全无向图含有n * (n - 1) / 2 条边；一个n阶的完全有向图含有n * (n - 1) 条边
强连通分量：有向图中任意两点都连通的最大子图；特殊地，单个点也算一个强连通分量

关于 ∏ \prod ∏

∏ k = 1 n \prod_{k=1}^{n} ∏k=1n​ a k a_{k} ak​表示 a 1 a 2 ⋅ ⋅ ⋅ a n a_{1}a_{2}···a_{n} a1​a2​⋅⋅⋅an​

例如 ∏ k = 1 4 \prod_{k=1}^{4} ∏k=14​= (1 + 2)(2 + 2)(3 + 2)(4 + 2) = 3 × 4 × 5 × 6 = 360

十进制转二进制（小数部分）

例子： ( 0.25 ) 10 (0.25)_{10} (0.25)10​

0.25 × 2 = 0.5 0.25 × 2 = 0.5 0.25×2=0.5 （整数部分为 0 ）
然后不要整数部分，变成 0.5 0.5 0.5
0.5 × 2 = 1.0 0.5 × 2 = 1.0 0.5×2=1.0（整数部分为 1 1 1）
然后不要整数部分，变成 0.0
结束，顺着数，就是 ( 0.01 ) 2 (0.01)_{2} (0.01)2​

​

NOI竞赛历史

1984年，DXP：“计算机的普及要从娃娃做起。”，第一届NOI举办

1995年，第一届NOIP

1989年，IOI，保加利亚

1995年，WC

1999年，NOI网络同步赛

2007年，APIO

2011年，NOIP取消保送

2014年，CSP认证（Certified Software Professional，软件能力认证）

2019年，CSP非专业级别的能力认证

原码反码补码

原码
第一位为符号位，正数为0，负数为1
后面就是接它的二进制数

反码
正数的反码就是它的原码
负数的反码就是它的原码除符号位外取反
例如110010是原码，那么反码就是101101

补码
正数的补码和它原码一样
负数的补码 = 它的反码最后 + 1

因特网提供的服务

万维网（www）：是一个全球规模的信息服务系统

电子邮件（E-mail）：具体格式为（收件人邮箱名+@邮箱所在主机的域名）

文件传输协议（FTP）：用于在计算机间传输文件

远程登录（Telnet）：指通过Internet与其他主机连接

整形数据与字节

编译器可以dao根据自身硬件来选择内合适的容大小，但是需要满足约束：short和int型至少为16位，long型至少为32位，并且short型长度不能超过int型，而int型不能超过long型。这即是说各个类型的变量长度是由编译器来决定的，而当前主流的编译器中一般是32位机器和64位机器中int型都是4个字节

链表

链表不是线性的.不需要事先计算存储空间
因为他是一个一个结点连成的,.你要加一个结点,就增长一点空间.
插入删除不需要移动元素
所需空间与线性表长度成正比

就先写到这吧，本蒟蒻会间断更新的。。。记得多来康康