CSP-J 初赛知识点

· · 个人记录

CSP-J知识点：

制作时间：9-16

由@yutong_Seafloor制作嗷，不会私信羽桐即可。

不可以转载/改写

板块1：选择题（30分）

1. 运算符：以下数字在进行运算的时候要切换成2进制哦（进制转换在第二条），负数以补码的形式参与！！！

两个数进行 与 运算，在2进制中的两个数字若两个对应位同为1则这一位是1，其余取0

011000101 010010100

——————

010000100

两个数进行 或 运算，在2进制中的两个数字若两个对应位有一个是1则这一位是1，其余取0

011000101 010010100

——————

011010101

两个数进行 异或 运算，在2进制中的两个数字若两个对应位有且仅有一个是1则这一位是1，其余取0。

注意这里与按位或不同，必须是一个1一个0才是1，其余都是0！。

$ 010010100$\ ——————\ $ 001010001

做题发现：

n=-~n 其实就是 n++，n=~-n 其实就是 n--（这里的 - 是取反的意思）

一下位移运算和cin,cout没有任何关联，注意甄别

把数字整体（左移符号前的数字）向左移动几位（具体移动几位取决于后边的数字）,如果高位越界则舍弃

011000101<<3 = 000101000

经过大量不会做的题，得出：

n << 1 = 2n 1 << n = 2^n

把数字整体（右移符号前的数字）向右移动几位（具体移动几位取决于后边的数字）,如果低位越界则舍弃

011000101>>3 = 000011000

又经过大量不会做的题，得出：

n >> 1 = \lfloor \frac{n}{2}\rfloor

优先级： 括号，乘方，乘除，加减，位移，按位与，按位或，按位异或，按位或。

做为区分在这里讲一下 ∧ 和 ∨（这个是判断真假的，不要和上边的联系起来）

2. 进制转换：

把一个十进制的数字不断除以一个要转换进制的数字，余数保留，最后把得到的余数从最后的到的往后排。

eg：十转八

3778÷8=472……2\ 472÷8=59……0\ 59÷8=7……3\ 7÷8=0……7

所以最后3778转成八进制是7302

定义2进制最高一位转换十进制（这一位是1）是2^n，2进制整个数转换十进制为s，二进制这一位对应的是a

那么

s=a_1\times2^1+a_2\times2^2+a_3\times2^3+……+a_n\times2^n

如果这对应一位是0不加（听起来有些笼统还是结合栗子吧）

eg:

01100$ $0101 s=1\times2^1+0\times2^2+1\times2^3+0\times2^4+0\times2^5+0\times2^6+1\times2^7+1\times2^8 =394

建议大家记好：

2^3=8 2^4=16 2^5=32 2^6=64 2^7=128 2^8=256 2^9=512 2^10=1024

emmm这种是有技巧的

怎么说，还是上栗子。

2转4：01001

[21|21|21]()

00|10|01

发现上边有一行蓝色的数字了吗（无链接别点了），把对应区块的加起来就是这个进制的对应数字，所以01001的4进制是21

我再列8/16进制的栗子,可以自己找找规律，友情提示，这种方法只适用于2转2的几次方的方法

2转8：010110111

[421|421|421]()

010|110|111

八进制：267（2=2,6=4+2,7=4+2+1）

2转16：010110111

[8421|8421]()

1011|0111

十六进制：B7（B=11=8+2+1,7=4+2+1）

将十六进制一转四，把十六进制中的1，2，3，4，5，6，7，8，9，10（A），11（B），12（C），13（D），14（E），15（F）转化为0001，0010，0011，0100，0101，0110，0111，1000，1001，1010，1011，1100，1101，1111，然后拼数字即可。

2转8，4同理

3. 二叉树的遍历：

度：有几个子节点就有几个度（通俗的讲就是下边有几个结点就有几个子结点）

左子树：根节点左边的数（右子树同理）

完美二叉树：所有结点满的树是完美二叉树

完全二叉树：最下边两层结点度数小于2，且最下一层的节点都集中在该层的最左侧。

注意这里的左必须是左子树的左子树的左子树的左子树，直到达到了左结点才算完，然后往回找接着遍历。

具体的我们搞一个栗子（后+中）：

897465321\ 684971523

我们从后序得到根节点是1，在遍历中标记

89746532|1|\ 68497|1|523

然后我们得到84976是一颗左子树，523是一颗右子树，接着标记

89746|532|1\

68497|1|523

先单独看84976，根是6，区分

8974|6\ 6|8497

我们得到剩下的，剩下的在右子树，不断找根区分

8|97|4|6\ 6|8|4|97

然后就变成了这样，左子树搞定，看右子树（如果你没看懂一会结合下边的图自己手动模拟一下）

532\ 523

接着区分根

53|2|\ 5|2|3

然后得到5是左，3是右，遍历完了画树

然后遍历树，先序很好遍历看好这个图（从根开始）

先序和中序就按照这种一点点拆分，看不懂就多看几遍

先序和后序可能性很多，如果选择题出了就一个个带选项吧

4.时间复杂度

看这个吧

我不会告诉你因为我也不怎么会

5.数学（排列组合）

A_n^m=n(n-1)(n-2)(n-3)……(n-m+1)=\frac{n!} {(n-m)!}

排列适用于排列（需要顺序）

A_n^n=n! C_n^m=\frac {(n-1)(n-2)(n-3)……(n-m+1)}{m!}=\frac{n!} {m!(n-m)!}

组合适用于几选几（不需要顺序）

C_n^n=1
  1. 如果你遇到了教练要排序没有条件用排列
  2. 如果你遇到了挑一定人数演讲（没条件的情况下）用组合
  3. 如果遇到了xx在排序时必须站在某个地方，且为排列，那么其他人排列位置总和-1，参与人数-1。
  4. 捆绑法：n 个不同元素排成一列，要求 m 个元素必须相邻。

这里套用一个题：

有1个国画，4个水彩，5个油画，要求同种画必须排列在一起，问方案数

先拆成小问题:4个水彩内部排列有几种？5个油画内部排列有几种？1个国画内部排列有几种？

很显然，依次是

现在把一个小问题当成一个元素排列，也就转成了3种元素有几种排列方式。 那么就成了三个小问题答案相乘再乘以一个$A_3^3

最后列得A_4^4 \times A_5^5\times A_1^1\times A_3^3(我没写错吧

那现在再加个条件：国画必须放中间

那么和3条结合看，最后式子变成：

A_4^4 \times A_5^5\times A_1^1\times A_2^2
  1. 插空法：n 个不同元素排成一列，要求 m 个元素不能相邻。

还是套题：

10班一共十人要站队，羽桐和小Y有矛盾不能站在一起，小X不能和小Z站在一起这样就会和小Z聊天，问方案数

排掉羽桐，小X，小Y,小Z，剩下的人进行排列：A_6^6

然后把羽桐，小X，小Y，小Z插进去，就是A_9^4

于是就得到了：A_6^6\times A_9^4

  1. 插板法：n 个相同元素分成 m 组，每组至少有一个元素。

这种方法适用于一般的分苹果（大家都肯定做很多了），方法就是先找空（一般是n-1个），然后把隔板插进去（m-1个）就分好组了

直接上结论吧（要不然写不完了,不会的私信）：

C_{n-1} ^{m-1}

比较杂，自己看吧

  1. 质数/素数：前100个数有25个是质数，分别是：2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,972,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97，特别注意下，1不是质数，但也不属于合数（就是质数以外的数）
  2. 同余定理：主要是应付找公倍数的题，结论是(m-n)÷t是一个整数的话，m÷t 的余数和 n÷t 的余数相同（具体的用法就是把选项和题目的数字相减然后再除以是某个数倍数的数，得0就证明这两个数是其倍数），题&题解。
  3. 欧几里得算法：这个是应付找公约数的题，用除数和余数反复进行除法运算，直到余数是0，取当前算式除数即可

eg：求96和78最大公约数

96÷78=1……18 78÷18=4……6 18÷6=3……0

所以最大公约数是6

6.排序：

省流一张图：

（注：稳定性的话假如有两个相同的数，稳定的话相同的两个数最后顺序和输入相同，反之亦然）

如果你不知道具体某种排序是怎么排序的往下滑

额额额本来打算讲一遍的但是luogu不支持动图还是去看这个人的博客吧

7.先/中/后缀表达式

我先讲构建树这种的方法（我也不是很懂，有错指出）：

按照顺序构建一棵树，数字做为叶子结点，符号做为度不为0的结点。

比如 1-5\times （3+6）

前缀表达式就用先序遍历：-1\times 5+3 6\ 中缀表达式就用中序遍历：1-5\times （3+6）\ 后缀表达式就用后序遍历：1 5\times 3 6+-

然后再根据题意进行相应的操作即可\ （有其他方法欢迎投稿，虽然多半没时间了吧）

8.图像/视频计算：

顺便把单位换算也放在这里面吧：

9.数据结构：

10.杂项

IPv4：本质上是四个八位二进制数，为了方便表达改为四个十进制数 ，以 . 隔开，每一个数字取 0-255，例如 12.34.56.78。

拓展：IP 分割成 4 份是为了方便管理，每一位代表着你身处于哪一段。假设洛谷封IP段需要把 12.34.56.0 到 12.34.56.255 内的IP全部封号，只需要封 12.34.56.* 即可达到操作。

IPv6：八个十六进制数，以 : 隔开，防止 IPv4 不够用。

板块2.阅读程序建议

如果你现在阅读程序很垃圾，你可以试着一行一行注释代码，试图理解意思，或者看函数名字猜测意图，再不行带一个小样例找规律，只要你读懂了程序这题就会very easy。

板块3：补全程序建议

假设你看不懂程序一点，先读题，把题读明白了然后看函数名字肯定有很大的信息透露，实在不行联系上下文你看看有没有对子程序写

再不行你就蒙BC

祝大家全都过初赛嗷，RP++