CSP-J/S初赛
2022更新的初赛知识汇总
基础算法
链表
插入删除数据，操作数据O（1），遍历是O(n),可以进行动态调整。
指针指向的是上下节点，链表储存 数据 下一个节点 上一个节点。
动态调整：插入一定量的节点，进行调整。
插入节点：考虑信息覆盖（这些信息后面是否会再被用到）。
寻找和读取比较慢一些。
队列、栈
栈Stack，队列queue
可以使用两个栈来模拟队列，队列也可以模拟栈。
递推和递归
递归：再函数定义中使用函数本身，可以通过堆、栈实现。 如果因为执行次数过多导致暴空间是栈。
基本图论
度：度数、入度、出度。
连通图：
不一定是直接到达。
无向连通图至少有N-1个节点。，有向图强连通至少有n条边。
只要有有向图和无向图就是混合图。
邻接矩阵：稀疏图效率低。
邻接表：记录每一个点延伸出去的边
树
并查集用树来实现的
有根树性质
- 边数=点数-1
- 有环的大多数不一定是树
二叉树
完整二叉树：每个节点度数为0或2。
完全二叉树：
满二叉树/完美二叉树：所有节点的度为2.
序列反推：已知中序遍历，和另一个任意便利方式，可以得到一棵树。
哈夫曼树
哈夫曼编码可以用来节省空间。
二叉搜索树
深搜与广搜
深搜：栈
广搜：队列
排序
逆波兰表达式
进制转换与位运算
x进制转10进制
对于整数部分
对于 n 位 X 进制整数，考虑我们刚刚所讲的满 X 进 1 的定义，我们可以从其 X 进制中求出其十进制值。令其从左往右第 i 位数码为 ??
(a1a2...an)x=a1Xn-1 + a2Xn-2+...+anX0
总结就是从低位到高位，依次累计计算答案就行了。
对于小数部分
十进制转 X 进制
整数部分
十进制整数转 X 进制，采用进制的定义即可，使用短除法。具体地，每次将当前数除以 X 的余数记下，然后将该数除以 X 后下取整，重复操作直到当前数变为 0。将记下的所有余数反着排列，就可以得到转换后的 X 进制数。例如将十进制整数 13 转为二进制
小数部分
考虑十进制小数转 X 进制，整数部分与小数部分可以分别计算，于是整数部分按照刚刚的方法计算即可。考虑数码从左到右位数变小、X 的幂次也变小，可以发现小数部分将除法改为乘法即可。具体地，提出小数部分 p，每次将 p 乘上 X，然后记下并减去整数部分，重复计算直到 p 为 0。记下的数码顺序排列就是小数部分。例如对于十进制小数 13.375，整数部分化为 1101，小数 0.375 提出计算。0.375 × 2 = 0.75, 0.75 × 2 = 1.5, 0.5 × 2 = 1记下的数字分别为：0,1,1，可得 0.375 化为二进制为 0.011。于是 13.375 化为二进制即为 1101.011
位运算
简介
程序中的所有数在计算机内存中都是以二进制的形式储存的，位
运算就是直接对整数在内存中的二进制位进行操作。
C++ 语言提供了六种位运算符来进行位运算操作：
- 按位与 &
- 按位或 |
- 按位异或 ^
- 按位非 ~
- 左移 <<
- 右移 >>
具体功能
按位与 &
按位与：C++ 中写作 &，数学公式中写作 and。将参与运算的两操作数各对应的二进制位进行与操作，只有对应的两个二进位均为 1 时，结果的对应二进制位才为 1，否则为 0。
按位与的应用：
• 通常用来将某变量中的某些位变成 0 且同时保留其他位不变。
例如 n&=0xffffff00 可以将 int 型后 8 位清 0。
• 用来获取某变量中的某一位。
例如判断 n 的从低到高第 3 位是否是 1 可以用 n&4 来判断。
代码中 if(x&1) 等价于 if(x%2==1)。
注意： && 是对 bool 进行的逻辑与，5&&7=true&&true=1
按位或 |
将参与运算的两操作数各对应的二进制位进行或操作，只有对应的两个二进位均为 0 时，结果的对应二进制位才为 0，否则为 1。
按位或的应用：
• 通常用 来将某变量中的某些位变成 1 且同时保留其他位不变。
例如 n|=0x0000ffff 可以将 int 型后 16 位变成 1 。
注意：|| 是对 bool 进行的逻辑或，5||0=true||false=1。
按位异或 ^
将参与运算的两操作数各对应的二进制位进行异或操作，只有对应的两个二进位不同时，结果的对应二进制位才为 1，否则为 0。
异或具有可差分性，即 a^b=c 可以推出 ca=b,cb=a。
代码中 if(x^1) 等价于 if(x!=1)
按位非（取反） ~
是单目运算符。其功能是将操作数中的二进制位 0 变成 1，1 变成 0。
通过编码的知识，我们可以知道 x=-(x+1)。if(x) 和 if(x!=-1) 等价
左移运算符<<
a<<b 得到的值是将 a 的二进制位全部左移 b 位后得到的值，左移时高位丢弃，低位补 0，a的值不因运算而改变。实际上左移一位就是 × 2，于是左移 n 位就是 × 2?，左移操作比乘法操作快得多。
右移运算符 >>
a>>b 得到的值是将 a 的二进制位全部右移 b 位后得到的值，右移时移出最右边的位丢弃，高位补 0，a 的值不因运算而改变。实际上右移一位就是 ÷ 2 后向下取整，右移 n 位就是 ÷ 2? 后向下取整。
例如：7>>2=3>>1=1。
有符号数的右移是算术右移，右移后符号位会赋为原符号位。所以对于负数的右移，实际上是 10xxx 右移一位变为 110xxx
运算符的优先级
本质上就是算术运算优先，其次再是位运算，最后是逻辑运算。注意位运算非的优先级很高。
基础知识
