NOIP（划掉）CSP2019一轮知识点

今年似乎变动很大呢……

去年总结的

历年真题

以下标题中打*的是我认为的重点内容

*一、关于计算机

（一）计算机组成

计算机的工作原理跟人的大脑很相似，而且还是大脑功能的延伸，所以习惯上叫它电脑。

硬件组成：

1. 控制器(Control):是整个计算机的中枢神经，其功能是对程序规定的控制信息进行解释，根据其要求进行控制，调度程序、数据、地址，协调计算机各部分工作及内存与外设的访问等。

2. 运算器(Datapath):运算器的功能是对数据进行各种算术运算和逻辑运算，即对数据进行加工处理。

3. 存储器(Memory):存储器的功能是存储程序、数据和各种信号、命令等信息，并在需要时提供这些信息。

4. 输入(Input system):输入设备是计算机的重要组成部分，输入设备与输出设备合称为外部设备，简称外设，输入设备的作用是将程序、原始数据、文字、字符、控制命令或现场采集的数据等信息输入到计算机。常见的输入设备有键盘、鼠标器、光电输入机、磁带机、磁盘机、光盘机等。

5. 输出(Output system):输出设备与输入设备同样是计算机的重要组成部分，它把外算机的中间结果或最后结果、机内的各种数据符号及文字或各种控制信号等信息输出出来。微机常用的输出设备有显示终端CRT、打印机、激光印字机、绘图仪及磁带、光盘机等。

CPU:

CPU（中央处理器）=运算器+控制器+（寄存器）

存储器：

存储器=内存储器（主存）+外存储器

随机存储器RAM的“随机”指“随时访问”

随机存取存储器（英语：Random Access Memory，缩写：RAM），也叫 主存 ，是 与CPU直接交换数据 的内部存储器。它可以 随时读写 （刷新时除外），而且 速度很快 ，通常作为操作系统或其他正在运行中的程序的 临时数据 存储介质。RAM工作时可以随时从任何一个指定的地址写入（存入）或读出（取出）信息。它与ROM的最大区别是数据的易失性，即 一旦断电所存储的数据将随之丢失 。RAM在计算机和数字系统中用来暂时存储程序、数据和中间结果。

只读存储器（英语：Read-Only Memory，简称：ROM）。ROM所存数据，一般是装入整机前事先写好的，整机工作过程中 只能读出 ，而不像随机存储器那样能快速地、方便地加以改写。ROM所存数据稳定 ， 断电后所存数据也不会改变 ；其结构较简单，读出较方便，因而常用于存储各种固定程序和数据。

​BIOS是英文"Basic Input Output System"的缩略语，直译过来后中文名称就是"基本输入输出系统"。其实，它是一组固化到计算机内主板上一个ROM芯片上的程序，它保存着计算机最重要的基本输入输出的程序、系统设置信息、开机后自检程序和系统自启动程序。 其主要功能是为计算机提供最底层的、最直接的硬件设置和控制。

快存：高速缓冲存储器是存在于主存与CPU之间的一级存储器， 由静态存储芯片(SRAM)组成，容量比较小但速度比主存高得多， 接近于CPU的速度。在计算机存储系统的层次结构中，是介于中央处理器和主存储器之间的高速小容量存储器。它和主存储器一起构成一级的存储器。高速缓冲存储器和主存储器之间信息的调度和传送是由硬件自动进行的。

外储存器是指除计算机内存及CPU缓存以外的储存器，此类储存器一般断电后仍然能保存数据。常见的外存储器有硬盘、软盘、光盘、U盘等。又称为辅存。

断电后可以保存数据：硬盘，ROM

断电后不可以保存数据：显存（显卡内存），RAM，CPU

面向过程语言 ：C、Fortran、Pascal

面对对象的高级语言：C++、Java

解释执行的程序设计语言（脚本语言）：Python、PHP

软件系统：

关于操作系统：

UNIX 诞生于1969年

Windows 诞生于1985

Linux 诞生于1991年

Windows 和 Linux 都参考了 UNIX

操作系统（operating system,OS）是管理计算机硬件与软件资源的计算机程序，同时也是计算机系统的内核与基石。操作系统需要处理如管理与配置内存、决定系统资源供需的优先次序、控制输入设备与输出设备、操作网络与管理文件系统等基本事务。操作系统也提供一个让用户与系统交互的操作界面。

（二）计算机发展史

（这部分中部分内容参考洛谷日报第45期。感谢）

（三）计算机中各存储单位的进位关系：

1TB=1024GB

1GB=1024MB

1MB=1024KB

1KB=1024Byte

1Byte（字节）=8bit（位）

bit不常用

*二、二进制原码、反码与补码

（这部分中部分内容参考https://blog.csdn.net/jq_ak47/article/details/45338061。感谢）

（一）原码

在计算机中（以八位机为例），我们知道都用二进制来存储数

如5，二进制为00000101

那么负数怎么存储？将最高位设为符号位，正数为0，负数为1

如-5，二进制为10000101

-6，为10000110

以上叫做原码

（二）反码

反码表示法规定：正数的反码与其原码相同；负数的反码是对其原码逐位取反，但符号位除外。

如7，原码为00000111，反码为00000111

如-10，原码为10001010，反码为11110101

（三）补码

正数的补码是其本身，负数的补码是反码加一

补码有什么用呢？解决负整数加减法

比如我们计算16-8 或是 16+（-8）

如果用原码计算

0 0 0 0 1 0 0 0

+1 0 0 0 0 1 0 0

————————

1 0 0 0 1 1 1 1

将10001111转换为二进制，结果为-24，显然不对

如果用补码呢？

0 0 0 0 1 0 0 0

+ 1 1 1 1 1 1 0 0

————————

1 0 0 0 0 0 1 0 0

*注意，此处用八位二进制，而计算结果是九位二进制，所以最高位自动省略

这样结果是8，正确

若要将补码转化为原码，正数不变，负数先-1再取反码就可以了

三、P问题、NP问题与NPC问题

（这部分中部分内容参考http://www.matrix67.com/blog/archives/105。感谢）

我就说的简略一点了（主要是怕自己忘了），详见上面网址

（一）P问题

每个问题的算法都有时间复杂度

O(1),O(N),O(NlogN),O(n ² )等n不在指数为的复杂度为多项式级复杂度

O(N!),O(2 ⁿ ）等复杂度是非多项式级的

可以找到一个多项式级复杂度算法的问题是P问题

NOI系列考的绝大多数问题都是P问题

注：如果一个问题不存在多项式空间的算法，那它一定不是 P 类问题（详见NOIP2012提高组初赛第20题）

（二）NP问题

一个解可以用多项式级复杂度检验的问题是NP问题

注：找不到多项式复杂度解的(非P问题) 不一定 是NP问题

易得NP=P。即所有P问题都是NP问题

至于P=NP，大家感兴趣的话可以自己研究研究（滑稽护体）

（三）NPC问题（NP-完全问题）

先讲一下“归约”

有两个问题，问题A和问题B

若可以用问题B的算法来解决问题A，那么问题A可以归约为问题B

比如，一元一次方程可以归约为一元二次方程

归约具有传递性，即A可以归约成B，B可以归约成C，那么A一定可以归约成C

可以看出，在不断归约的过程中，算法的时间复杂度逐渐增高，解决的问题也越来越广

大胆猜测，是否可以将所有的NP问题都归约成一个问题？解决了这个问题就能解决所有NP问题？

答案是肯定的！

而且这不仅是一个问题，还是一类问题

这类问题叫做NPC（NP-完全）问题。

一个问题满足以下两条，它就是NPC问题：

1、它是NP问题

2、所有NP问题都能在多项式时间复杂度内归约到它

NPC问题的鼻祖是逻辑电路问题，有兴趣的读者可以自行了解。

另外说一下NP-hard问题，它满足NPC问题的第二条但不一定满足第一条。它包含NPC问题。

*四、进制转换

（一） 二 、 八 、 十六 互转通用方法：

以八进制转二进制为例

先把关系表列出来：

二转八：

例如：10010011.1011

2^ 3 =8

所以使用 三位一合 的方法。若整数部分位数不是三的倍数，在最高位前补0；若小数部分位数不是三的倍数，在末尾补0。接着以小数点为分界， 从左到右 分别转化小数部分和整数部分。

对照上面的表 10 010 011. 101 100

2   2      3 .   5     4

所以(10010011.1011) ₂ =(223.54) ₈

八转二：

同理， 一位三分 法

例如：7643

对照上面的表 7    6      4     3

111  110  100  011

注：十六进制等进制中，A代表10，B代表11，以此类推

（二） 二转十和十转二

二转十：个位*2^0，十位*2^1，百位*2^2…… 若是小数，十分位*2^-1，百分位*2^-2……然后加起来就行了

十转二：整数部分：不断除以2，直到商为0，倒取各阶段余数

小数部分：不断乘以2，直到积为1，正取各阶段整数

如10.25转化为二进制

10÷2=5……0

5÷2=2……1

2÷2=1……0

1÷2=0……1

倒着取余数，1010即为整数部分

0.25*2=0.5……0

0.5*2=1……1

正着取整数，0.01即为小数部分

将两部分合起来，得到10.25=(1010.01) ₂

（三）其它

符号：二进制是B，八进制是O，十进制是D，十六进制是H

其它2^n的进制如要转化为十进制，先转化为二进制，再转化为十进制。

十进制转化成它们同理。

**五、排序算法

基本是每年必考！

（这部分中部分内容参考http://blog.csdn.net/whuslei/article/details/6442755/ 和 https://blog.csdn.net/xiazdong/article/details/8462393。感谢）

这个讲的实在太好了%%%

九大排序算法：（加上桶排序就是十个）

计数排序            O(n+k)             O(n+k)               O(n+k)           O(n+k)          稳定             简单

排序算法稳定，指排序前后数值相同的两个数相对位置不会改变

稳定：插、归、冒、基、计

不稳定：快、堆、希、选

需要额外空间：归、基、计

不需要额外空间：插、希、冒、快、堆、选

运用分治思想的：归、快

时间复杂度是O(NlogN)的：堆、快、归（希尔排序的时间复杂度依赖于增量的选择，这里不做讨论）

最慢是O(N ² )的：插、冒、快、选

最快是O(N)的：插、冒（改进后）

最快最慢相同的：冒（不改进）、选、堆、归、基，计

需要进行关键字比较：冒、堆、插

不需要：基

example：（NOIP2017提高组t11）

void merge(int l,int mid,int r)

{

    int i=,p1=l,p2=mid+;

    while(p1<=mid && p2<=r)

    {

        if(a[p1]<a[p2])

        {

            f[++i]=a[p1];

            p1++;

        }

        else

        {

            f[++i]=a[p2];

            p2++;

        }

    }

    while(p1<=mid)

    {

        f[++i]=a[p1++];

    }

    while(p2<=r)

    {

        f[++i]=a[p2++];

    }

    for(i=;i<=r-l+;i++)

    {

        a[l+i-]=f[i];

    }

    return ;

}

void merge_sort(int l,int r)

{

    if(l>=r) return ;

    int mid=l+r>>;

    merge_sort(l,mid);

    merge_sort(mid+,r);

    merge(l,mid,r);

    return ;

}

#include <iostream>

using namespace std;

void fun(char *a, char *b) {

    a = b; //a变为c2的地址。注意，指针=指针时地址中的值不变，变的只是指针

    (*a)++; //将a地址（c2）中的值+1

}

int main() {

    char c1, c2, *p1, *p2;

    c1 = 'A';

    c2 = 'a';

    p1 = &c1; //p1是c1的地址

    p2 = &c2; //p2是c2的地址

    fun(p1, p2); //（NOIP的函数好像都叫fun……）

    cout << c1 << c2 << endl;//输出为Ab

    return 0;

}