[exaqp]初赛复习大纲

2023-11-22 17:13:40

初赛复习大纲

基础知识

  • 1MB=1024*1024字节

  • 图像文件的字节数=图像分辨率*颜色深度/8

  • 断电之后仍能保存数据的有 硬盘,ROM

  • 断电之后不能保存数据的有 寄存器,显存,内存,高速缓存

  • NOIP 不推荐使用： Visual C++,Turbo C,Turbo Pascal

  • H(Hexadecimal)——16进制 D(Decimal)——10进制 O(Octonary)——8进制 B(Binary)——2进制

第一届竞赛时间

全国青少年信息学奥林匹克竞赛（NOI） 1984

全国青少年信息学奥林匹克联赛(NOIP)  1995

国际信息学奥林匹克竞赛(IOI) 1989

亚太地区信息学奥林匹克竞赛（APIO）2007

人物

冯·诺依曼(Neumann) 
"计算机之父",ENIAC和EDVAC的技术顾问
存储程序原理:将程序像数据一样存储到计算机内部存储器中的一种设计原理首次提出了存储程序控制原理，称为“冯·诺依曼结构”

戈登·摩尔(Gordon Moore) 英特尔公司创始人之一,摩尔定律

查尔斯·巴比奇(Babbage)  发明了世界上第一台机械计算机器——差分机

克劳德·香农(Shannon)  信息论之父、发明了术语比特 

姚期智 2000年图灵奖 华裔

阿达·洛芙莱斯(Ada Lovelace) “第一位给计算机写程序的人”

艾伦·图灵（英）：计算机科学/人工智能之父，首次提出了计算机科学理论。计算机界的最高奖项“图灵奖”以他命名，被称为“计算机界的诺贝尔奖”。


克劳德·香农（美）：创造了信息论，提出了某种信息从一处传送到另一处所需的全部设备所构成的系统。

Ada·Lovelace：第一位程序员/第一位软件设计工程师。

Ada 同时是美国军方发明的语言，为了纪念第一个女程序员

操作系统

操作系统是一种系统软件，直接控制和管理计算机系统的所有软、硬件资源，以方便用户充分而有效地利用这些资源的程序集合

常用的计算机操作系统有：
1.Windows系列操作系统（咱们最常用的）
由微软公司生产；
2.Unix类操作系统
如SOLARIS,BSD系列（FREEBSD，openbsd，netbsd，pcbsd）；
3.Linux类操作系统
如UBUNTU，suse linux，fedora，等
4.Mac操作系统
由苹果公司生产（Darwin），一般安装于MAC电脑。
其他: Symbian(塞班公司为手机而设计) 

Linux下的文件不需要扩展名。一切皆文件

计算机相关

主机:CPU和内储存器

U盘是闪存盘的一种
寄存器是CPU的有限存贮容量的高速存贮部件，它们可用来暂存指令、数据和地址
CPU中 高速缓冲存储器 提高系统整体的执行效率

CPU=控制器+运算器+寄存器
CPU 的主要任务是执行数据运算和程序控制

控制器: 控制机器各个部件协调工作
存储器: 存储各种控制信息 

ROM是只读存储器（Read-Only Memory），只能读出事先所存数据的固态半导体存储器，一旦储存资料就无法再将之改变或删除 
随机存取存储器（英语：Random Access Memory，缩写：RAM） -> 内存、主存

BIOS
Basic Input Output System 基本输入输出系统
保存着计算机最重要的基本输入输出的程序、系统设置信息、开机后自检程序和系统自启动程序
为计算机提供最底层的、最直接的硬件设置和控制

CPU、存储器、I/O设备是通过 总线 连接起来的。

网络相关

为计算机网络中进行数据交换而建立的规则、标准或约定的集合称为网络协议。
HTTP、TCP/IP、FTP是网络协议。
TCP属于传输层协议 IP 属于网络层协议
TCP/IP: 
数据链路层：ARP,RARP
网络层： IP,ICMP,IGMP
传输层：TCP ,UDP,UGP
应用层：Telnet,FTP,SMTP,SNMP.

属于电子邮件收发的协议 SMTP,IMAP,POP3
SMTP-发送   IMAP,POP3-接收 

IP地址
先判断它是不是由4段数字用点号“.”分隔开，再判断每段数字的十进制是不是在0-255之间，满足条件就是正确的IP地址
IP地址是一个32位的二进制数，通常被分割为4个“8位二进制数”（也就是4个字节）

每一个字节都为0的地址（“0.0.0.0”）对应于当前主机；
IP地址中的每一个字节都为1的IP地址（“255.255.255.255”）是当前子网的广播地址
IP地址中不能以十进制“127”作为开头

IPv4 协议使用 32 位地址，随着其不断被分配，地址资源日趋枯竭。因此，它正逐渐被 使用 128 位地址的 IPv6 协议所取代

P类/NP类/NPC类问题

1、P类问题：如果一个问题能找到一个在多项式时间内解决它的算法，那么这个问题就是P问题。

2、NP类问题：注意：NP问题不是非P类问题，而是在多项式时间内验证一个解的问题。或者，我们可以将其理解为在多项式时间内猜出一个解的问题。

3、NPC类问题：定义如下：如果一个问题是NP问题，而且所有的NP问题都可以约化到它。那么它就是NPC类问题。再来介绍一下关于约化的定义：如果一个问题A可以约化为问题B，含义就是这个问题A可以用问题B的解法来解决。

P是NP,NP不一定是P

语言

C是一种面向过程的高级计算机语言
C++  JAVA C#  Pascal 面向对象 
汇编语言 直接对硬盘 

面向过程程序设计通常采用自顶向下设计方法进行设计

Java、Python、Matlab 解释型语言，不需要编译
C、C++、Pascal 编译型语言 编译的时候直接编译成机器可以执行或调用的程序，如exe、dll或ocx等类型 

第一个高级语言是fortran，Ada是美国军方发明的语言，取名Ada是为了纪念第一个女程序员
第一个支持面向对象的语言是simula67

排序相关

稳定排序:两个相等的数不会交换位置

堆排序、快速排序、希尔排序、直接选择排序是不稳定的排序算法，
基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法

基数排序 基于桶排序

运算符

按位与运算符（&）

参加运算的两个数，按二进制位进行“与”运算。

运算规则：只有两个数的二进制同时为1，结果才为1，否则为0。（负数按补码形式参加按位与运算）

即 0 & 0= 0 ，0 & 1= 0，1 & 0= 0， 1 & 1= 1。 例：3 &5 即 011 & 101 = 1 ，所以 3 & 5的值为1。

按位或运算符（|）

参加运算的两个数，按二进制位进行“或”运算。

运算规则：参加运算的两个数只要两个数中的一个为1，结果就为1。

即 0 | 0= 0 , 1 | 0= 1 ， 0 | 1= 1 , 1 | 1= 1 。

例：2 | 4 即010 | 100 = 110 ，所以2 | 4的值为 6 。

异或运算符（^）

参加运算的两个数，按二进制位进行“异或”运算。

运算规则：参加运算的两个数，如果两个相应位为“异”（值不同），则该位结果为1，否则为0。

即 0 ^ 0=0 ， 0 ^ 1= 1 ， 1 ^ 0= 1 ， 1 ^ 1= 0 。

例： 2 ^ 4 即 010 ^ 100 =110 ，所以 2 ^ 4 的值为6 。
位运算符 名称 算法
& 按位与 两个二进制数相应位都为 1，则该位的结果为 1，否则为 0
| 按位或 两个二进制数相应位有一个为 1 时，结果位就为 1
^ 按位异或 两个二进制数相应位不同时，结果为 1
~ 按位取反 对二进制进行取反，即 1 取反为 0 ， 0 取反为 1
<< 按位左移 将二进制数左移 n 位，相当于乘以 2 的 n 次方
>> 按位右移 将二进制数右移 n 位，相当于除以 2 的 n 次方，如果不能整除，则向下取整

排序算法

  1. 插入排序
    [exaqp]初赛复习大纲 
#include<iostream>
using namespace std;
void InsertSort(int a[], int n){ //插入排序 
    for (int j=1;j<n;j++){
        int key=a[j]; 
        int i=j-1;  
        while (i>=0&&key<a[i]){
            //从后向前逐个比较已经排序过数组，如果比它小，则把后者用前者代替
            a[i+1]=a[i];
            i--;
        }
        a[i+1]=key;//找到合适的位置了，赋值,在i索引的后面设置key值。
    }
}
  1. 冒泡排序
    [exaqp]初赛复习大纲 
#include<bits/stdc++.h>
using namespace std;
void bubbleSort(int a[],int n){ //冒泡排序 
    for(int i=1;i<n;i++){
        bool flag=true;
        for(int j=1;j<=n-i;j++){
            if(a[j]>a[j+1]){
                swap(a[j],a[j+1]);
                flag=false; //发生交换，则排序还未完成 
            }
        } 
        if(flag)  return ;//没有交换则说明已排好 
    }
}
  1. 选择排序
    [exaqp]初赛复习大纲 
#include<bits/stdc++.h>
using namespace std;
void selectSort(int a[],int n){ //选择排序 
    for(int i=1;i<n;i++){ //n-1次下标 
        int minn=i; //最小值的下标 
        for(int j=i+1;j<=n;j++){
            if(a[j]<a[minn])  minn=j;
        }
        if(minn!=i){
            swap(a[i],a[minn]);
        }
    } 
}
  1. 快速排序
    [exaqp]初赛复习大纲 
#include<bits/stdc++.h>
using namespace std;
void quickSort(int a[],int start,int end){ //快速排序，等同于sort()函数 
    int mid=a[(start+end)/2],l=start,r=end;
    while(l<r){
        while(a[l]<mid)  l++;
        while(a[r]>mid)  r--;
        if(l<=r)  swap(a[l++],a[r--]);
    } 
    if(start<r) quickSort(a,start,r);
    if(l<end)  quickSort(a,l,end);
}
  1. 归并排序
    [exaqp]初赛复习大纲 
#include<iostream>
#include<algorithm>
using namespace std;
int a[10010],r[10010],n;
void msort(int s,int t)
{
	if(s==t) return ;
	int mid=(s+t)/2;
	msort(s,mid);
	msort(mid+1,t);
	int i=s,j=mid+1,k=s;
	while(i<=mid&&j<=t)
	{
		if(a[i]<=a[j]) r[k++]=a[i++];
		else           r[k++]=a[j++];
	}
	while(i<=mid)   r[k++]=a[i++];
	while(j<=t)   	r[k++]=a[j++];
	for(int i=s;i<=t;++i)
	    a[i]=r[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]<<" ";
    cout<<endl;
	return 0;
}
  1. 桶排序
#include<iostream>
using namespace std;
void countingSort(int a[],int n){ //桶排序 
    //maxnum 值的最大范围
    int b[maxnum]={0},minn=a[1],maxn=a[1];
    for(int i=1;i<=n;i++){
        b[a[i]]++;
        minn=min(a[i],minn);
        maxn=max(a[i],maxn);
    } 
    for(int k=0,i=minn;i<=maxn;i++){
        for(int j=1;j<b[i];j++){
            a[++k]=i;
        }
    }
}
  1. 堆排序
#include<iostream>
using namespace std;
void MaxSort(int a[], int i, int n)
{
    int j=2*i+1;//找到当前结点的左孩子
    int temp=a[i];
    while(j<n){
        if(j+1<n&&a[j]<a[j+1])//判断条件，第一个条件是判断是不是最后一个结点。                    
            j++;
        if(temp>a[j])//因为我们是MaxSort所以如果父结点本身就大不用判断直接跳出循环。
            break;
        else{
            a[i]=a[j];
            i=j;
            j=2*i+1;
        }
    }
    a[i]=temp;//交换 
}
void HeapSort(int a[], int n){ //堆排序 

    for(int i= n/2-1;i>=0;i--)//从最后一个结点的父结点开始向前遍历
        MaxSort(a,i,n);
    for(int i=n-1;i>=1;i--)
    {
        MaxSort(a,0,i);
    }
}
  1. 希尔排序
#include<iostream>
using namespace std;
void shellSort(int a[],int len){ //希尔排序   (len代表数组长度) 
    for(int i=len/2;i>=1;i/=2){//增量 
        for(int j=0;j<i;j++){//分组 
            for(int k=i+j;k<len;k+=i){//排序 
                int temp=a[k];
                int x=k-i;
                while(x>=0&&temp<a[j]){
                    a[x+i]=a[x];//移动增量个单位 
                    x-=i;
                }
                a[x+i]=temp;
            }
        }
    } 
} 

交换排序
核心思想：根据序列中两条记录键值的比较结果，判断是否需要交换记录在序列中的位置。
其特点是将键值较大（或较小）的记录想序列的前端移动，将键值较小（或较大）的记录想序列的后端移。

冒泡排序
核心思想：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
也就是说，每一轮冒泡，就找出了序列中未排序的最大（或最小）的数。

冒泡排序优化
其实冒泡排序在每轮排序中，除了将最小（或最大）的数据放到靠后的位置之外，还使较小的数据放到靠近合适的位置。但是，如果在冒泡排序的过程中，已经获得了有序的序列，但是循环还没有结束，那么从这轮循环之后的循环都是无用功。如何避免这段时间的消耗呢？
其实，只需要在代码中设置一个简单的标志位即可。

直接插入排序
核心思想：将一个记录插入到已排序好的有序表中，从而得到一个新、记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。
要点：设立哨兵，作为临时存储和判断数组边界之用。

直接插入排序的优化
在直接插入排序中，主要的时间消耗在数据的比较和移动上。那么有没有什么办法来降低数据比较的次数呢？
由于前半部分的序列已经有序，在为新数据寻找插入点时，可以采用折半查找的方法来提高寻找的速度。

简单选择排序
核心思想：在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

归并排序
核心思想：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

快速排序
核心思想：
选择一个基准元素,通常选择第一个元素或者最后一个元素；
通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大；
此时基准元素在其排好序后的正确位置；
然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

希尔排序
核心思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

堆排序
核心思想：从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。
建立堆的过程，对每个非叶子节点进行渗透函数的调用；渗透函数的过程，非叶子节点与其子节点中的大者（或小者）比大小，若大于（或小于），则进行交换。

更好的排序讲解

其他常用代码

  1. 最大公因数、最小公倍数
#include<bits/stdc++.h>
using namespace std;
int gcd1(int a,int b){ //辗转相除递归解法 
    if(b==0)  return a;
    return gcd1(b,a%b); 
} 
int gcd2(int a,int b){ //辗转相除法求解 
    while(b!=0){
        int r=a%b;
        a=b;
        b=r;
    }
    return a;
} 
int lcm(int a,int b){ //最小公倍数 
    return a*b/gcd1(a,b);
}
  1. 质数判断
#include<bits/stdc++.h>
using namespace std;
bool isPrime(int num){ //质数判断 
    if(num<2)  return false;
    for(int i=2;i*i<=num;i++){
        if(num%i==0)  return false;
    } 
    return true;
}
  1. 埃式筛
#include<bits/stdc++.h>
using namespace std;
const int MAX=1e9;
bool isPrime[MAX]; 
void eraSieve(int MAX){ //埃式筛 
    //计算MAX范围内所有的质数 
    memset(isPrime,true,sizeof(isPrime)); 
    isPrime[0]=isPrime[1]=false;
    for(int i=2;i<=MAX;i++){
        if(isPrime[i]){
            for(int j=2;j*i<=MAX;j++){
                isPrime[j*i]=false;
            }
        }
    } 
}
  1. 欧拉筛
#include<bits/stdc++.h>
using namespace std;
const int MAX=1e7;
bool isPrime[MAX];
int prime[MAX]; 
void EulerSieve(int MAX){ //欧拉筛 
    memset(isPrime,true,sizeof(isPrime)); 
    isPrime[0]=isPrime[1]=false;
    int cnt=0; //质数个数 
    for(int i=2;i<=MAX;i++){
        if(isPrime[i]){
            prime[cnt++]=i;
        }
        for(int j=0;j<cnt&&prime[j]*i<=MAX;j++){
            isPrime[prime[j]*i]=false;
            if(i%prime[j]==0)  break;
        }
    } 
}
  1. Floyd
#include<iostream>
using namespace std; 
void Floyd(){ //Floyd核心代码 
  for(int k=1; k<=n; k++)
    for(int i=1; i<=n; i++)
      for(int j=1; j<=n; j++)
        if(e[i][j]>e[i][k]+e[k][j])
          e[i][j]=e[i][k]+e[k][j];
}

各种复习网址

希尔排序(缩小增量排序)

时空复杂度

递推

进制转换

当小球遇上盒子

卡特兰数

卡特兰数详讲

斯特林数

常用模板集合(1)

常用模板集合(2)

CSP初赛知识点(1)

CSP初赛知识点(2)

CSP初赛知识点(3)

CSP初赛知识点(4)

CSP初赛知识点(5)

CSP初赛知识点(6)

CSP初赛知识点(7)

CSP初赛知识点(8)

经典九大排序(1)

经典九大排序(2)

博弈论之取石子游戏的学习

高中数学

Tarjan

矩阵乘法

找规律

学习图论

noi笔试题库

CSP 2020 第一轮（初赛）模拟

SCP 2021 第一轮（初赛）模拟

原创：精神小伙！（洛谷）

2021/10/21 稍作修改,增加了阅读体验感

上一篇：C++容器 vector


下一篇：《算法进阶指南》- 0.2递推与递归