前沿：

好像很简单又很难（

就L1到L3的内容qwp！

复赛的话就是L4吧……

猫第一次考CSP的时候是教我的老师监考（/fad

来自猫猫学姐（？）的提示：孩子你多刷刷L4及以前的题吧，阅读程序&完善程序有我们刷过的题（真题，嗯大部分考的都是递归和dp之类的喵呜。

猫笔记： CSP的初赛分为6大板块有

计算机基础知识（我想回去2013年以前考CSP2333

C++语言基础和STL

基础算法

线性数据结构（stack之类的啊

非线性数据结构

初等数论&组合数学（why put shushu on 初赛

第一章，送分题。

CSP举办时间：初赛9月份中下旬复赛10月份末（不出意外的话是这样的🤓️☝️

题目类型：单选30pts&阅读程序40pts&完善程序30pts

北京CSP-J1晋级率24.11%（记笔记……

你能看到一个无能的猫猫

CCF中国计算机协会（Chinese Can Fly）于1984年创办全国青少年信息学奥林匹克竞赛。翻译成人话就是NOI。

然后就很少出这种题了（记笔记🤓️☝️

计算机的诞生&发展

电子管计算机时代（1946~1958）逻辑元件：电子管，编程语言：机器语言，应用领域：军事研究&科学计算

晶体管计算机时代（1956~1964）逻辑元件：晶体管，编程语言：汇编语言，应用领域：科学计算&数据处理

集成电路与大规模集成电路计算机时代（1964~1970）逻辑元件：中小规模集成电路，编程语言：高级语言，应用领域：数据处理&工业自动化

超大规模集成电路计算机时代（1970~至今）逻辑元件：超大规模集成电路，编程语言：面向对象语言，应用领域：人工智能、多媒体、网络

计算机领域最高奖 ：图灵奖

yqz：中国首位图灵奖得主（bdfs

计算机基本结构

冯诺伊曼架构运算器、控制器、存储器、输入设备、输出设备

其中运算器，控制器是CPU。

CPU和存储器沟通。

存储器分为内存条&硬盘。（内存条就类似运行内存，是 $RAM$ 断电会丢失，运行速度快。容量小）

硬盘就是 $ROM$ 断电不会丢失容量较大，但是运行速度慢。

输出设备：类似打印机，显示器等等（这个需要自己分辨了qwp

输入设备：鼠标哇键盘哇都是。🤓️☝️

常见的操作系统：Linux Mac OS Windows 🤓️☝️

鸿蒙，安卓也是操作系统喵。🤓️☝️

操作系统的作用

1.分配资源（处理多个任务分配系统资源）

2.人机界面（图形化界面）

3.为应用程序开发平台（给软件开发者一个系统接口）

一个对于“中断”的定义：暂时停止当前工作。

计算机语言和应用软件

常见的编程语言：

1.机器语言：可以被机器直接读懂，执行速度快。

but：学习难度太大了。（只有0和1的代码

so 这是个低级语言……（饿

2.汇编语言：采用一些特殊符号表示机器指令，提高了编程的可读性（。

but：学习难度还是比较大，不过难度有所降低。

3.高级语言：

人话翻译：人能看懂的语言饿啊还比较简洁qwp！

高级语言分为两种语言：

面向过程语言：比如说 $C$ 和 $Fortran$ 语言🤓️☝️

面向对象语言：比如说 $C plus plus$ （c++) $python$ 等等🤓️☝️

饿啊，众所周知，我们学习的高级语言需要经过编译才能执行🤓️☝️

所以高级语言需要经过编译编程汇编语言，然后再次进行编译成为机器语言反馈给计算机。所以编译的过程就是试图让机器理解高级语言。🤓️☝️

嗯嗯但是如果我们试图成为黑客（雾，别干坏事奥）我们只能看到一大堆的机器语言，嗯嗯所以就有反编译编译成高级语言让黑客看懂然后篡改代码（雾。🤓️☝️

网络qwp！

计算机协议：大多是TCP/IP

广域网(WAN)范围：大概几十到几千公里，出现在跨省/跨国/跨洲（Internet是目前世界上最大的广域网）

城域网(MAN)范围：大概几千米到几十千米，出现在几个相邻的城市（以太网技术）

局域网(LAN)范围：大概几十米到几千米，出现在学校/企业/工作单位/家庭中（以太网技术）

个域网(PAN)范围：大概几十米以内出现在个人/家庭中（无线个域网WPAN）

IP地址

IP地址分为IPv4和IPv6

其中IPv4地址由32位二进制数组成，IPv6地址由128位组成

IPv4是32位二进制，一个字节有8位，那么32位就有4个字节（4*8=32）每八位为一段， ${2^8}$ 为 $256$ 意味着我从全是0到全是1每一段的取值范围就是0到255（按照数组下标理解）

DNS:将IP地址转化为域名的一个东西比如说打开网站不用输入IP地址输入网址就行🤓️☝️

我们常见的域名：

$edu$ 教育机构

$gov$ 政府部门

$net$ 网络组织

$com$ 营业组织

$org$ 非盈利组织

$mil$ 军事部门

$cn$ 中国的顶级域名

$hk$ 中国香港地区

$mo$ 中国澳门地区

$tw$ 中国台湾地区

$jp$ 日本（ $ATcoder$ 🤓️☝️

$sg$ 新加坡qwq

因特网

因特网的协议特别多啊列几个常见的

TCP Transmission Control Protocol 传输控制协议

IP Internet Protocol 国际互联协议

DNS Domain Name Server 域名服务器

HTTP Hyper Text Transmission Protocol 超文本传输协议

HTML Hyper Text Markup Language 超文本标记协议

FTP File Transfer Protocol文件传输协议

WWW Worls Wide Web 万维网

SMTP Simple Mail Transfer Protocol 简单邮件传输协议

POP3 Post Office Protocol 邮局协议

~~猫英语不好打字打力竭了喵~~

计算机安全

计算机病毒：木马病毒是隐藏在正常程序中具有特殊功能的恶意代码（人为编写）

如何保护计算机：安装杀毒软件，检查防火墙等等

二进制

为什么计算机使用二进制！？

两种状态的系统稳定性高，运算简单，容易实践

二进制具有可行性，可靠性，简易性，逻辑性。这四大特性（让AI给你解释一下

计算机存储

单位：

最小的单位 bit （位）

基本单位 byte （字节）==8 bit

千字节（KB）==1024 byte

兆字节（MB）==1024KB

吉字节（GB）==1024MB

太字节（TB）==1024GB

当然，这种东西肯定是有单位换算的🤓️☝️

（以下来自豆包AI）

bit ↔ Byte（位 ⇋ 字节）

字节 → 位： $\boldsymbol{\mathrm{bit}=Byte \times 8}$
位 → 字节： $\boldsymbol{\mathrm{Byte}=bit \div 8}$

示例：

$$\begin{align*} 2\ \mathrm{Byte}&=2\times8=16\ \mathrm{bit}\\ 32\ \mathrm{bit}&=32\div8=4\ \mathrm{Byte} \end{align*}$$

2. KB、MB、GB、TB 之间（考试二进制，倍率1024）

大单位 → 小单位：×1024

$$\boldsymbol{2\ \mathrm{MB}=2\times 1024 =2048\ \mathrm{KB}}$$

小单位 → 大单位：÷1024

$$\boldsymbol{4096\ \mathrm{MB}=4096 \div 1024 =4\ \mathrm{GB}}$$

完整层级：

$$\mathrm{Byte}\xrightarrow{\times1024}\mathrm{KB}\xrightarrow{\times1024}\mathrm{MB}\xrightarrow{\times1024}\mathrm{GB}\xrightarrow{\times1024}\mathrm{TB}$$

做题示范（综合连算，选择题高频）

例： $4\ \mathrm{KB} = \ ?\ \mathrm{bit}$

4\ \mathrm{KB}=4 \times 1024\ \mathrm{Byte}

=4\times1024 \times8\ \mathrm{bit}

=32768\ \mathrm{bit}

例： $16384\ \mathrm{KB}= \ ?\ \mathrm{GB}$

$$16384\ \mathrm{KB}=16384 \div1024 =16\ \mathrm{MB}$$

16\ \mathrm{MB}=16\div1024 =0.015625\ \mathrm{GB}

⚠️考试坑点

$\mathrm{B}=Byte$ 字节； $\mathrm{b}=bit$ 位，大小写不能混。
计算机理论题全部用 1024；硬盘商家才用1000，做题不要用。
最小单位：bit（位）；基本单位：Byte（字节）。

图像存储容量计算

基础概念

总像素 = 图像宽度 × 图像高度
位深度：单个像素占用bit数量
颜色总数公式：

颜色数 = 2^{\text{位深度}}

核心计算公式

容量(\mathrm{bit}) = 宽 \times 高 \times 位深度

容量(\mathrm{Byte})=\frac{宽 \times 高 \times 位深度}{8}

再结合存储换算：大→小 $\times 1024$ ；小→大 $\div1024$

注意：公式只针对未压缩BMP位图，JPG/PNG压缩图片不适用。

例题

例：分辨率 $800\times600$ ，24位真彩色BMP，求KB大小

总bit =800 \times 600 \times 24

$$Byte=\frac{800\times600\times24}{8}=1440000\ \mathrm{Byte}$$

KB=1440000 \div 1024 \approx1406.25\ \mathrm{KB}

（以下并非为AI）

如何表示字符呢！？

ASCLL码自己bdfs去吧（我觉得你们学过qwq

用数字表示字符qwq

由于美国只有26个字母所以ASCLL会更好表示qwq

你格雷码来咯（AI

格雷码 Gray Code

定义

格雷码是一种反射型二进制编码；相邻两个数的格雷码仅有1个二进制位发生改变。格雷码不属于有权编码，不能直接用位权计算十进制。

转换公式

二进制转格雷码

最高位直接复制：

G_{n-1}=B_{n-1}

其余位，异或左侧二进制位：

G_i = B_{i+1} \oplus B_i

口诀：最高位不变，后面每一位等于本位二进制异或左边二进制位。

格雷码转二进制

最高位直接复制：

B_{n-1}=G_{n-1}

B_i = B_{i+1}\oplus G_i

口诀：最高位照抄；后面每一位 = 已经算出来左边二进制异或当前格雷码位。

格雷码用途

旋转编码器、角度传感器，相邻只变1位，避免产生错误中间读数。
消除数字电路竞争冒险。
卡诺图行列编号，逻辑化简。

4位格雷码表

十进制	二进制	格雷码
0	0000
1	0001
2	0010	0011
3	0011	0010
4	0100	0110
5	0101	0111
6	0110	0101
7	0111	0100
8	1000	1100
9	1001	1101
10	1010	1111
11	1011	1110
12	1100	1010
13	1101	1011
14	1110	1001
15	1111	1000

特点：十进制0和15格雷码也只差1位，具备循环反射特性。

格雷码序列

反射递归构造规则

n位格雷码：

写出 n‑1位格雷码序列；
将n‑1序列逆序反射；
原序列前面补0，反射出来的序列前面补1，拼接得到n位格雷码。

公式：十进制n转格雷码

G(n)=n \oplus (n>>1)

1位格雷码序列

0 1

2位格雷码序列

00 01 11 10

3位格雷码序列

000 001 011 010 110 111 101 100

4位格雷码序列

十进制	格雷码
0	0000
1	0001
2	0011
3	0010
4	0110
5	0111
6	0101
7	0100
8	1100
9	1101
10	1111
11	1110
12	1010
13	1011
14	1001
15	1000

特点：相邻两个格雷码只有1bit不同；序列首尾也仅1bit不同，循环。