OK啊，这里是CSP-J初赛知识汇总，是我上课做的，可能有些没记上，大家可以在这里@我，我就会补充

CSP- J

CSP- J

位运算

1.& 按位与，都是1是才是1

2.^异或，相同为0，不同为1

lowbit() 函数，获取2进制中最右边的 1

printf("%0nd", x);

// 右对齐，不足 n 位，前面用 0 代替

printf("%-nd", x);

// 左对齐，不足 n 位，后面都是空格

C++ 里面的字符串是一个 类（class

指针

// 值传递

// 因为值传递前，首先进行一遍 copy 操作

// 然后把 copy 以后的值传入，不是变量本身

void swap(int a, int b) {
	int t = a;
	a = b;
	b = t;
}

// 引用传递

// 因为传递的是变量本身

// 因此对 a, b 操作，然后影响主函数里面的 a, b

void swap(int &a, int &b) {
	int t = a;
	a = b;
	b = t;
}

指针必须要用箭头 ->

结构变量 或者 对象用 .

结构体/联合体

union student {
	int h;		// 身高 
	int w;		// 体重 
	char g;		// 性别 
}a;
int main() {
	a.w = 100;
	cout << a.h << "\n" << a.g;
	return 0;
}

时间复杂度

常数 < 对数 < 线性 < 线性对数 < 平方 < 立方 < 指数 < 阶乘

二分的经典题型：

求 XXX 最大值的最小情况 求 XXX 最小值的最大情况

【L3】 章节 23. 二分查找与答案 - 课堂作业 章节 24. 二分查找与答案 - 训练计划 【砍木头，跳石头，吃香蕉】课后练习去思考分别是怎么实现的

去思考一下二分怎么写【P4944. 王者农药】

线性数据结构

线性数据结构：

逻辑上数据元素呈一对一的线性次序：有唯一前驱、唯一后继。

使用 at() 可以访问 vector<> 里面的元素

	还可以访问 map< , > 里面的元素 

push()：翻译---> 压入

pop()： 翻译---> 弹出

⚠️clear() 不可以用于【栈】或者【队列】

计算这个前缀表达式的值：- + 1 * 2 3 / 4 5

计算前缀表达式需要从右往左遍历 - + 1 * 2 3 (4 / 5)

		- + 1 (2 * 3) (4 / 5) 

		- (1 + 2 * 3) (4 / 5)

		(1 + 2 * 3) - (4 / 5)

		 + 2 * 3 - 4 / 5

		 =   6.2

树/二叉树

叶子结点：左右子树全都为空的结点，就是叶子。

核心公式：n0 = n2+1（叶子结点 = 度2结点+1）

n0:叶子（度0）；n1:度1；n2：度2

总结点数n = n0+n1+n2

二叉树的遍历：

前序遍历：根—— 左—— 右

后序遍历：左—— 右—— 根

中序遍历：左—— 根—— 右

分析逻辑：

先根据后序遍历确定【根结点】

再根据[根结点]和[中序遍历]确定【左子树】【右子树】

图

• DFS：递归 / 栈，一路往深处走，走不通回溯

• BFS：队列，一层一层向外扩散（最短路）

链表 可以看作特殊的【图】

树 也可以看作特殊的【图】

邻接矩阵———点少边多

邻接表————点多边少

初等数论

判断题：自然数不是质数就是合数？？？

0、1 是自然数，但是都不是质数，也不是合数

L3 章节 37. 初等数论 - 课堂作业 章节 38. 初等数论 - 训练计划

这种选法（或者放法）的时候，当题目出现了一模一样的词汇

那么就需要采取分类讨论思想

（本质上加法计数原则）

空串 也是 子串

空集 也是 子集

捆绑法，插空法，分类讨论，定序问题处理，因数，最大公因数，最小公倍数，加法原理，乘法原理，排列组合，组合公式的对称性与化简计算

加法：直达

乘法：我先到X，再到Y

0！= 1

• 捆绑法 = 必须相邻
• 插空法 = 不能相邻（隔开）