普及组算法汇总

🚀 优质资源分享 🚀

名词

OI: olympiad in informatics 信息学奥林匹克竞赛

IOI: international olympiad in informatics 国际信息学奥林匹克竞赛

NOI: national olympiad in informatics 全国信息学奥林匹克竞赛

NOIP: national olympiad in informatics in province 全国信息学奥林匹克竞赛省赛

CSP: 非专业计算机能力认证 -J, -S。

J: junior: 低级的

S: senior: 高级的

进入提高组复赛，且得分非0的选手可以参加NOIP

CCF: China computer fundation 中国计算机协会

---

SMTP: 简单邮件传输协议(simple mail transport protocol)

POP3: 邮局协议版本3(Post Office Protocol - Version 3)

IMAP: 交互邮件访问协议（Internet Message Access Protocol)

小知识

面向过程: 只有C语言面向对象: 除了C语言的所有语言(C++, python, Java)

编译型语言和解释型语言编译型语言: C,C++,Pascal解释型语言: python, Java, PHP

计算机系统windows系统类unix系统: 除了windows系统以外的所有系统: android, ios, macOS, linux…

码

原码、反码、补码：8位二进制数表示的有符号整数

最左边一位是符号位(1:负数,0:正数)

反码: 原码的符号位不变，其他位取反

补码: 反码+1

补码:10101011

反码:10101010

原码:11010101

==> -85

-52

原码:10110100

反码:11001011

补码:11001100

运算符

x<

x>>y=x2y

∨:或 -> 只要有一个为真，则表达式为真

∧:且 -> 两个都是真才为真，有一个假为假

﹃（）﹃（¬）：非 -> 假为真，真为假

数学知识

集合论基础

1. 集合：若干个互异无序元素。集合有两种记录方法，如 为偶数A={1,2,3},T={i|i为偶数}
2. 空集：没有函数的集合。计作：∅
3. 属于与不属于: 表示一个元素是否属于该集合。如 1∈A,4∉A
4. 子集：如果集合A中包含集合B中的所有元素，则称B为A的子集。记作 B⊂A。若A不是B的子集，记为A⊄B。
5. 真子集：如果B是A的子集，且B与A并不相等，则称B是A的真子集。记作 B⊆A。若A不是B的真子集，记为A⊈B。
6. 并 集：字面意思为将两个集合合并后的结果。即如果元素x在集合A或集合B中，那么x在集合A与集合B的并集中。A与B的并集可以记作 X=A∪B
7. 交 集：字面意思为两个集合相交的部分。即如果元素x既在集合A中，又在集合B中。那么元素x在集合A与B的交集中。A与B的交集可以记作 Y=A∩B。

---

8. 区间：区间是一种特殊的集合，表示一个连续的部分的所有元素。如 、、、[1,2]、(4,5)、[9,10)、(2,+∞)
9. 闭区间、开区间与半开半闭区间：
10. 用[]表示的是闭区间，表示区间左右两端的元素都在集合中，如[1,2]，1也是集合的一个元素；
11. 用()表示的是开区间，表示区间左右两端的元素都不在集合中，如(4,5)，4和5都不在集合中；
12. 一边中括号一边小括号的是半开半闭区间，中括号那一端的元素在集合中，小括号那一端的不在集合中。
13. 带有无穷符号的区间：有+∞ 与 −∞ 。无穷符号那一端的必须是小括号，且正无穷的正号不能省略。
14. 几个重要的集合: 实数集：R , 自然数集合：N, 整数集合: Z, 正整数集合: N+
15. 集合与不等式的转化：如 1≤x≤10 可以写成 [1,10]，x>3 可以写成 (3,+∞)

概率论基础

1. 事件：一个不受主观意念控制的事情。如“天要下雨”，“彩票中一千万”, “CSP初赛全部靠蒙考满分”, "明天太阳照常升起"是事件，“我今天吃肯德基”, “CSP凭实力0分”, "我晚上通宵写代码"不是事件。在概率论中，我们常用一个字母表示一个事件，如事件A为天要下雨。
2. 概率：事件发生的可能性。一般用P表示，事件A发生的概率记为P(A) 。
3. 频数与频率。在计算一个事件发生的概率时，需要进行多次随机试验。事件发生的次数就是频次，事件发生频次的比例就是频率。如事件A为扔硬币扔出正面。我扔了10次硬币，9次正面，则频次为9，频率为90%。
4. 积事件：若事件C为事件A与事件B同时发生，那么事件C就是事件A与事件B的积事件。记为C=A∩B，P©=P(A∩B)=P(AB)
5. 独立事件：两个事件的发生没有相关关系，则这两个事件为独立事件。如"今天下雨"与"扔硬币扔出正面"是独立事件。"今天下雨"与"今天空气湿度高于50%"不是独立事件。
6. 独立事件的概率：P(AB)=P(A)⋅P(B) 。注意只有事件A与B独立该式才成立。
7. 和事件的概率：P(A+B)=P(A)+P(B)−P(AB) 。和事件为两个事件至少发生一个的概率。
8. 条件概率：P(A|B) 表示在B事件发生的条件下，A事件发生的概率。即“如果今天下雨，门口路上堵车的概率。”、“扔一次骰子扔出的数字是偶数，那么扔出的数字是2的概率”。
9. 贝叶斯公式：P(AB)=P(A|B)⋅P(B)=P(B|A)⋅P(A)
10. 互斥事件：不可能同时发生的事件。如“扔一次骰子扔出1”与“扔一次骰子扔出2”，“扔一次硬币为正面”与“扔一次硬币为反面”。
11. 对立事件：其中至少一个会发生的互斥事件。如”扔一次骰子扔出1“与“扔一次骰子扔出2”不是对立事件，“扔一次硬币为正面”与“扔一次硬币为反面”是对立事件。事件A的对立事件记为A¯。那么P(A)+P(A¯)=1。
12. 全概率公式：P(A)=P(A|B)⋅P(B)+P(A|B¯)⋅P(B¯)
13. 数学期望：随机事件的结果。如果一个随机试验会出现多种结果（或事件）X1,X2,…,Xi，每种事件可以获得Vi的收益。那么随机试验X 的数学期望为 E(X)=∑i=1nP(Xi)⋅Vi。

平面直角坐标系

1. 平面直角坐标系由横轴与纵轴组成。横轴为x轴，纵轴为y轴，点的坐标由括号组成的二元组表示，如(x, y)。
2. 点A对x轴作垂线到达的位置为A的横坐标，对y轴作垂线到达的位置为B的纵坐标。

三角函数

1. 勾股定理：在直角三角形中，假设三条边长度为 a,b,c(a≤b
2. “小角对小边”：在直角三角形中，角度较小的角所对的边较短
3. 角度制：一种表示角度的方法，一般写为 30∘,75∘等。
4. 单位圆：圆心在原点，半径为1的圆。
5. 弧度制：高中的数学表示方法。角对应的单