CSP-S 2019 初赛知识点整理

Setsugesuka · 2019-10-14 18:17:24 · 个人记录

这是我整理给自己的一份笔记，只是写博客上比较方便就写在上面，不知道为什么大家都看的到。。里面记的都是我自己没记住和我自己觉得很重要的，是 完 全 不 全 的。所以我这份东西只能参考，准备初赛还是需要自己啃初赛一本通，刷历年真题。

计算机基础知识常识

计算机常识

冯诺依曼理论

1. 计算机硬件设备由存储器、运算器、控制器、输入设备、输出设备五部分组成

2. 储存程序思想

第一台采用二进制的冯诺依曼结构计算机 EDVAC，由冯诺依曼设计。

图灵 英国人 计算机科学理论基础第一人

摩尔定律 英特尔创始者之一戈登摩尔提出 计算机性能将以每两年翻一番的速度向前发展。

计算机硬件

计算机硬件设备由存储器、运算器、控制器、输入设备、输出设备五部分组成

CPU由运算器、控制器和一些寄存器组成

运算器 算术运算和逻辑运算

控制器 是计算机的指挥系统

CPU主要性能指标 主频和字长

存储器分为主存储器（内存储器）和辅助存储器（外存储器）

内存储器分为 RAM、ROM、Cache 三种

常见的外存储器 软盘、硬盘、闪存、光盘

总线和分为数据总线（DB）、地址总线（AB）、控制总线（CB）

数据总线 双向 连接了CPU与各个部件 具体的传送方向由CPU控制

地址总线 传送地址信息 通常是单向的 20条地址总线控制1MB

控制总线 传送控制信号 协调各部件操作

常用性能指标

1. 字长 指一台计算机呢个处理的二进制码的位数 越长功能越强

2. 运算速度 每秒钟所能执行的指令条数 单位是MIPS

3. 主频 CPU 的时钟频率 单位有MHz（兆赫）与GHz（吉赫）

4. 内存容量 内存储器能储存信息的总字节数 反应内存储器存储数据的能力

微机内的存储器地址是以字长编址的

微型计算机中 寄存器的存取速度最快 （不是高速缓存，因为寄存器在CPU里面）

打印机分类

1. 针式打印机 通过打印头的 24 根针击打复印纸形成字体

2. 喷墨打印机 通过加热喷嘴，使墨水产生气泡，喷到打印介质上

3. 激光打印机 利用高压静电将感光鼓表面的“墨粉图像”转印到普通纸上

4. 笔试绘图机 装有画笔的平板式绘图机

5. 喷墨绘图仪 用于输出排料图和头版的专用宽幅单色绘图仪 打印介质是墨盒

计算机语言

编写计算机程序所使用的语言称为程序设计语言

程序设计语言通常分为 机器语言、汇编语言和高级语言

机器语言 二进制代码来编写计算机程序 又称二进制语言

汇编语言 用一些符号代替机器指令所产生的语言叫做汇编语言

高级语言 有两种“翻译”方式

1. 编译方式 先将整个源程序都转成二进制代码，生成目标程序，然后把目标程序连接成可执行的程序，以完成源程序要处理的运算并得到结果。

2. 解释方式 边扫描边解释，对源程序的语句解释一条、执行一条，不产生目标程序。

编译性语言 C、C++、Pascal、Object Pascal、Delphi、Fortran

解释性语言 ASP、PHP、Java、JavaScript、VBScript、Perl、Python、Ruby、MATLAB 等

面向对象语言

借鉴了 20 世纪 50 年代的人工智能语言 LISP 它引入了动态绑定的概念和交互式开发环境的思想

始于 20 世纪 60 年代的离散事件模拟语言 Simula67 ，引入了类的要领和继承 它是世界上第一个支持面向对象的计算机语言 而 Smalltalk 是第二个

成型于 20 世纪 70 年代的 Smalltalk

面向对象语言的发展方向

1. 纯面向对象语言 Smalltalk、EIFFEL 等

2. 混合型面向对象语言 C++、Objective-C 等

最高位为 1 的便是扩充 ASCII 码 所以基本 ASCII 码和扩充 ASCII 码可以表示 0 ~ 255

一级汉字和二级汉字按使用频度分

一级汉字按拼音排序 二级汉字按部首排序

区位码->国际码 区码和位码分别加上 32

点阵每一个点用一个 bit 存取 不管笔画繁简 每个汉字所占的字节数相等

内存中数据的存取是以字节为单位的

计算机安全知识

计算机病毒特性

1. 隐蔽性

2. 潜伏性

3. 传播性

4. 激发性

5. 破坏性和危害性

易读性、安全性等都不是计算机病毒特性

大部分计算机病毒主要造成计算机软件和数据的损坏 只有少数会影响到硬件

原码 补码 反码

小数点的两种表示方式

1. 定点表示法 小数点位置固定不变，不必用记号表示出来

2. 浮点表示法 两部分 尾数和阶码 尾数表示有效数值 阶码表示小数点位置

网络的主要功能

1. 资源共享

2. 信息传输

3. 分布处理

4. 综合信息服务

网络的地理位置分类 局域网（LAN）、城域网（MAN）、广域网（WAN）

B类 128.1.0.1~191.255.255.254

C类 192.0.0.1~223.255.255.254

主机 ID 所有域不能都为 0 或 255

部分保留的专用地址

域名是字符形式的 IP 地址，格式为 开头.主机名.主机类别.国家名（可以不要）

一个域名一般有 3~5 个子段 中间用“.”隔开

域名由域名系统（DNS）统一管理 DNS 是一个分布式数据库系统，由域名空间、域名服务器和地址转换请求程序三部分组成

顶级域名有三类

1. 国家顶级域名 cn（中国）、us（美国）、uk（英国）

2. 国际顶级域名 int

3. 通用顶级域名 com、net、edu、gov

每一级域名都由英文字母和数字组成，最长不超过计划 63 个字符，层次低的写在左边，层次高的在右边，之间用英文的点号分开，完整的域名不超过 255 个字符

域名的最左边指主机名，通常用主机提供的服务表示。如果主机名被忽略，默认为 WWW

2. 电子邮件扩展协议 MIME

3. POP$ 协议 $POP

目前使用较普遍的 POP 协议为第三版 所以称之为 POP3

2. 与 &&，∧
3. 或 ||，∨
4. 异或 ^

优先级 括号 > 非 > 与 > 或、异或 （两者同级）

与运算比或运算优先级高

集合运算的一元操作符优先 也就是补的优先级比交和并都高

出栈顺序在前的入栈顺序一定在后

队尾指针指向实际队尾元素所在的位置，队列为空时 head=tail

循环队列的元素个数为 (tail-head+n) mod n

与某个点相连的边的个数是奇数个的点叫做奇点

存在欧拉路的条件 连通图 奇点数为 2

存在欧拉回路的条件 连通图 奇点数为 0

选择题常用知识

姚期智是首位华裔图灵奖得主

空间复杂度的空间是指程序运行时理论上所占的内存空间

因为四个人都不在一个月的概率是 \frac {(12×11×10×9)}{12^4}=\frac{96}{55}

所以至少两个人在一个月的概率就是用 1 减去它等于 \frac {41}{96}

提供源节点和目的节点之间的信息传输服务的是网络层

设法向量坐标是 (x,y,z) 它与三个向量都垂直 点乘都为 0 ，可以解出法向量。

快排求第 k 大最优复杂度是 O(n) 的

代入第 0 项与第 1 项

只要求 2^{2005} mod 2005

而 2005=401*5

由费马小定理，上式等于 32

显然等于 32

因此 2^{2005} mod 401*5=32

图灵奖是由美国计算机协会 ACM 设立的

数字音频采样和量化过程中所用的主要硬件是 模拟到数字的转换器（A/D 转换器）

数据结构是带有结构的数据元素的集合

汉字国际码 GB2312-80 一级汉字有 3755 个

剪贴板是内存中的一块区域

用户使用 ADSL 接入互联网时，双绞线的一端连接 ASDL Modem ，另一端连接到计算机的 网卡插口 。

计算机中汉字编码的最高位是 1 。

2. 如果整数 x,y 满足 ax+by=1 ，且 a \mid n ，b \mid n ，那么 ab \mid n
3. 若 b=qd+c 那么 d \mid b 的充要条件是 d \mid c
4. 一个数末三位与末三位以前的数之差能被 7,11,13 整数，那么这个数能被 7,11,13 整除

同余

1. a$ $mod$ $p=x$，$a$ $mod$ $q=x$，$p,q$ 互质，那么 $a$ $mod$ $pq=x

公约数

1. gcd(x,y)*lcm(x,y)=x*y

卡特兰数

1. 递归公式 f(n)=\sum_{i=0}^{n-1} f(i)×f(n-i-1)

2. 递归公式 f(n)=\frac {f(n-1)×(4n-2)}{n+1}

3. 组合公式 f(n)=\frac {C^n_{2n}}{n+1}

4. 组合公式 f(n)=C^n_{2n}-C^{n-1}_{2n}

7. 对 \prod_{i=0}^n ai 之间加任意括号，不同的运算顺序个数的答案是卡特兰数。

素数

1. 若 p 为素数，那么 (p-1)! mod p=-1 它的逆定理也成立

2. 若 p 为素数，a 为正整数，且 a,p 互质 则 a^{p-1} mod p=1

排列

1. 从 n 个不同元素中选出 r 个数作排列，我们记作P(n,r)

2. P(n,r)=\frac{n!}{(n-r)!}$ 特别地 $P(n,n)=n!

3. 从 n 个不同元素中可重复地选出 m 个元素 共 n^m 种

4. 在 n 个元素中，有 n1,n2……nm 个元素彼此相同，且 \sum_{i=1}^m ni=n 则这 n 个元素的全排列个数有 \frac {n!}{\prod_{i=1}^n ai!} 种 这是全相异元素的全排列

5. 在 n 个元素中，有 n1,n2……nm 个元素彼此相同，且 \sum_{i=1}^m ni=r 则从这 n 个元素中选出 r 个的排列有 \frac {P(n,r)}{\prod_{i=1}^n ai!} 种 这是不全相异元素的选排列

6. 错排个数递推公式 f(1)=0,f(2)=1,f(n)=(n-1)(f(n-1)+f(n-2)) (n>=3)

7. 从 n 个不同元素中选出 r 个元素，不分首尾地围成一个圈圈的排列方案数为 \frac{P(n,r)}{r}

组合

1. 我们记 C(n,r) 为从 n 个元素里无序地选出 r 个元素的方案数

2. C(n,r)=\frac{n!}{r!×(n-r)!}
3. C(n,r)=C(n,n-r)
4. C(n,r)=C(n-1,r)+C(n-1,r-1)
5. \sum_{i=0}^n C(n,i) = 2^n

6. 从 n 个不同元素中选出 r 个元素组成一个组合，且允许这 r 个元素重复使用，则称这样的组合为可重复组合，其组合数记作 H(n,r)

7. H(n,r)=C(n+r-1,r)

8. 记 S(n,k) 是把 n 个元素划分到 k 个相同集合里，每个集合都不为空的方案数 有 S(n,1)=S(n,n)=1 且 S(n,k)=kS(n-1,k)+S(n-1,k-1)

最少任意交换次数为 n-置换环的个数

最少相邻交换次数为逆序对数

从 1 到 n 这 n 个数中选出若干个数，不能取相邻的数，至少取一个，方案数 f[n]=f[n-1]+f[n-2]+1

哈夫曼树的最小带权路径长度为\sum 叶节点权值×叶节点到根的距离

阅读理解常用知识

新约瑟夫问题

2. 从尾端向前遍历，找到第一个位置 j 满足 val[j]>val[i]

3. 交换两个元素的位置，翻转 [i+1,n]

递归转递推

int solve(int n,int m)
{
    if(m==1) return 1;
    int sum=0;
    for(int i=1;i<n;i++)
    {
        sum+=solve(i,m-1);
    }
    return sum;
}

而 solve(n-1,m)=\sum_{i=1}^{n-1} solve(i,m-1)

所以 solve(n,m)=solve(n,m-1)+solve(n-1,m-1)

模型转换

小球从 (1,1) 开始 45° 角在 n×m 的矩阵内，遇到矩阵的边界则反弹，碰到死角停止，问小球最终会停止在哪里。

不难发现这个问题和我们从起点开始穿过一堆矩阵，第一次到达一个矩阵的右上角停下，是等价的。所以我们求出右上角的那个位置，然后对横纵坐标分别求小球经过了多少矩阵。以横坐标为例，假设横坐标是 x ，我们用 x 去除 n 如果是奇数，那最后的那个点横坐标为 n ，否则就为 1。而这个右上角的点位置就是 (lcm(n,m),lcm(n,m)) 这也是很容易看出来的。

记 T 为一队列,初始时为空,现有 n 个总和不超过 32 的正整数依次入列。如果无论这些数具体为何值,都能找到一种出队的方式,使得存在某个时刻队列T中的数之和恰好为 9,那么 n 的最小值是

我们设队列里的元素为 a1,a2,a3...an ，这些元素的前缀和为 s1,s2,s3...sn。那么原问题等价于，用 1 到 32 这些数构成 s 数组，问当 n 为多大时一定会出现 i<j i,j \in [1,n] 且 s[j]-s[i]=9 。不难想到用抽屉原理，以 (1,10),(2,11)... 为元素分组，只要有任意两个元素属于同一组时，就会有一种方案使得队列之和为 9，一共有 17 组，所以 n 的最小值是 18

条件反射猜用处

int work(int a,int b)
{
    if(a%b)
        return work(b,a%b);
    return b
}

条件反射，一看就知道是求最大公约数

c[i][j]=c[i-1][j-1]+c[i-1][j];

求组合数

if(flag) cout<<"(";
for(int j=k;j<i;j++) cout<<b[j];
if(flag) cout<<")";

想到求除法，输出无限循环小数的循环节。

if(str[i]!=str[n-i-1]) flag=false

判断回文

for(int j=1;j<m;j++)
    num=next(num);
cout<<num<<" ";
alive[num]=0;
if(i<n) num=next(num);                   

约瑟夫环

不会证的结论

1. f(i,j)$ 指 $i$ 和 $j$ 的二进制位不同的个数 有 $\sum_{i=1}^{2^n-1} \sum_{j=1}^{2^n-1} f(i,j)=n×2^{2n-1}

补充程序全算法

递归进阶

非递归枚举全排列

#include <bits/stdc++.h>
using namespace std;
const int MAXN=10;

int a[MAXN];
int n,tot;

inline void print()
{
    for(int i=1;i<=n;i++)
        cout<<"    "<<a[i];
    cout<<endl;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) a[i]=i;//初始化
    print();//先输出最先的排列
    tot=1;
    for(int i=2;i<=n;i++) tot=tot*i;//计算一共有多少种排列
    tot-=1;//删去已经生成的一个
    for(int i=1;i<=tot;i++)
    {
        int j=n-1;
        while(a[j]>=a[j+1]) j--;//找到第一个比右边大的数作为目标位置
        int k=n;
        while(a[k]<=a[j]) k--;//从后往前找到第一个比目标位置的数大的数
        swap(a[j],a[k]);//交换两个数
        reverse(a+j+1,a+n+1);//翻转目标位置后一格到最后这一段数组
        print();
    }
    return 0;
}

快速排序

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;

int a[MAXN];
int n;

void qsort(int l,int r)
{
    int mid=a[(l+r)>>1];//取中间的数作为基准值
    int i=l,j=r;
    while(i<=j)
    {
        while(a[i]<mid) i++;
        while(a[j]>mid) j--;
        if(i<=j)
        {
            swap(a[i],a[j]);//找到一对不符合的 交换
            i++;
            j--;
        }
    }
    //如果没有交换就排完了
    if(l<j) qsort(l,j);
    if(i<r) qsort(i,r);
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    qsort(1,n);
    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    return 0;
}

快速排序求第 k 大

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e4+10;

int a[MAXN];
bool vis[MAXN];
int n,k,ans=-1,cnt=0;

int solve(int l,int r,int k)
{
    if(l==r) return l;
    int tmp=rand()%(r-l)+l;
    swap(a[tmp],a[l]);
    int value=a[l];
    int i=l,j=r;
    while(i<j)
    {
        while(i<j&&a[j]<value) j--;
        if(i<j){a[i]=a[j];i++;}else break;
        while(i<j&&a[i]>value) i++;
        if(i<j){a[j]=a[i];j--;}else break;
    }
    a[i]=value;
    if(i<k) return solve(i+1,r,k);
    if(i>k) return solve(l,i-1,k);
    return i;
}

int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        int sr;
        cin>>sr;
        if(!vis[sr])
            a[++cnt]=sr,vis[sr]=1;
    }
    if(k>cnt)
    {
        puts("NO RESULT");
        return 0;
    }
    ans=solve(1,cnt,cnt-k+1);
    cout<<a[ans]<<endl;
    return 0;
}

归并排序

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;

int a[MAXN],cc[MAXN];
int n;

void msort(int l,int r)
{
    if(l==r)
        return;
    int mid=(l+r)>>1;
    msort(l,mid);//递归处理左右两边
    msort(mid+1,r);
    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r)
    {
        if(a[i]<=a[j])
            cc[k++]=a[i++];
        else
            cc[k++]=a[j++];
    }
    while(i<=mid)//处理还没排进去的
        cc[k++]=a[i++];
    while(j<=r)
        cc[k++]=a[j++];
    for(int i=l;i<=r;i++)//赋值给原数组
        a[i]=cc[i];
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    msort(1,n);
    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    return 0;
}

动态规划