CSP-S初赛知识点

CatWing · 2025-09-14 10:06:33 · 算法·理论

（一）计算机/系统

1. Linux

2. time指令

命令的真正执行时间：user+sys

一般来说，real=user+sys，所以可以用 real 作为执行时间

3. GCC编译选项

完全二叉树：只有叶子结点那一层可以不是满的，而且都要集中在左侧连续区域

完美二叉树（满二叉树）：所有叶节点的深度相同，且所有非叶节点都有 2 个子节点，可以理解为叶子结点满的完全二叉树

森林：每个连通块都是树，一棵树也可称为森林

dfs遍历：从根节点向下遍历到最深，到了叶子结点再回溯，一旦有“分叉”的地方就继续向下遍历

bfs遍历：从上到下逐层遍历，并在每一层按照从左到右的顺序访问节点

（三）二进制

1.原反补码

原码：第一位为 1 表示负，为 0 表示正，其余位表示值

反码：正数的反码是其本身，负数的是在其原码基础上，第一位不变，其余位取反

补码：正数的补码是其本身，负数的是反码 +1

2. 位运算

这个都会用，主要说一下优先级

①~ ②<< >> ③& ④^ ⑤|

3. 逻辑运算

逻辑非：!

逻辑与：&&

逻辑或：||

优先级从高到低排列

（四）排序

前置芝士：排序算法稳定是指数值相同数在排序后相对位置不改变，反之改变

1. 插入排序

先排好前 i-1 个数，当插入第 i 个数时，遍历第 i-1 ~ 1 个数，直到当前第 j 个数不大于第 i 个数，插入第 i 个数到 j 后面

最好全都有序：O(n)，最坏全部反序：O(n^2)

排序稳定

void InsertSort(int arr[], int len){
    // 检查数据合法性
    if(arr == NULL || len <= 0){
        return;
    }
    for(int i = 1; i < len; i++){
        int tmp = arr[i];
        int j;
        for(j = i-1; j >= 0; j--){
            //如果比tmp大把值往后移动一位
            if(arr[j] > tmp){
               arr[j+1] = arr[j];
            }
            else{
               break;
            }
        }
        arr[j+1] = tmp;
    }
}

2. 选择排序

第一次选出最小的数，和第一个数交换；第二次从剩下的数中选出最小的，和第二个数交换……直到全都排好

无论原数组顺序是怎样的，时间复杂度都是 O(n^2)

排序不稳定

void selection_sort(T arr[], int len) {
    int i, j, min;
    for (i = 0; i < len - 1; i++) {
        min = i;
        for (j = i + 1; j < len; j++)
            if (arr[min] > arr[j])
                min = j;
        swap(arr[i], arr[min]);
    }
}

3. 堆排序

众所周知，大根堆是根的值最大依次向下递减的，小根堆是根的值最小依次向下递增的

那么堆排序就是，先将未排序的数组构造成一个大根堆，此时数组的最大值是根，将末尾的数（第 n 个数）和根交换；剩余待排序的 n-1 个数再构造成一个大根堆，交换顶端的数和第 n-1 个数……直到得出有序数组

注意：升序排序用大根堆，降序用小根堆

因为构造堆是 log 的，而要构造 n 次，所以时间复杂度是 O(nlogn)

排序不稳定

#include <iostream>
#include <algorithm>
using namespace std;
void max_heapify(int arr[], int start, int end) {
    //建立父节点指标和子节点指标
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { //若子节点指标在范围内才做比较
        if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点大小，选择最大的
            son++;
        if (arr[dad] > arr[son]) //如果父节点大于子节点代表调整完毕，直接跳出函数
            return;
        else { //否则交换父子内容再继续子节点和孙节点比较
            swap(arr[dad], arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}
void heap_sort(int arr[], int len) {
    //初始化，i从最后一个父节点开始调整
    for (int i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
    //先将第一个元素和已经排好的元素前一位做交换，再从新调整(刚调整的元素之前的元素)，直到排序完毕
    for (int i = len - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}
int main() {
    int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    heap_sort(arr, len);
    for (int i = 0; i < len; i++)
        cout << arr[i] << ' ';
    cout << endl;
    return 0;
}

4. 冒泡排序

排序稳定

void bubble_sort(int arr[], int len)  
{  
    int i, j;  
    for (i = 0; i < len; i++)  
        for (j = 1; j < len - i; j++)  
            if (arr[j - 1] > arr[j])  
                swap(arr[j - 1], arr[j]);  
}

5. 快速排序

采用分治思想，对于一个序列，选择一个基准元素，通常是第一个或最后一个元素，经过一轮扫描，比它小的在它左边，反之在它右边，再用同样的方法递归排序左右两部分，直到序列中所有数据均有序

最好每次选取的基准元素都能把数组分成均匀的两部分：O(nlogn)，最坏每次选取的都是最小值或最大值：O(n^2)

排序不稳定

public static void quickSort(int nums[], int start, int end) {
    //数组有多个元素进行排序
    if (start < end) {
        int base = nums[start];//以要进行排序数组第0个元素为base
        int left = start;//左指针
        int right = end;//右指针
        while (left < right) {
            //从右向左找，比base大，right--
            while (left< right && nums[right] >= base) {
                right--;
            }
            //比base小，替换left所在位置的数字
            nums[left] = nums[right];
            //从左向右找，比base小，left++
            while (left < right && nums[left] <= base){
                left++;
            }
            //比base大，替换right所在位置的数字
            nums[right] = nums[left];
        }
        nums[left] = base;//此时left=right，用base替换这个位置的数字
        //排列比base小的数字的数组
        quickSort(nums, start, left - 1);
        //排列比base大的数字的数组
        quickSort(nums, left + 1, end);
    }
}

6. 计数排序

过程不会 （太抽象了）

时间复杂度 O(n+k)，其中 k 是值域

排序稳定

NO code……

7. 基数排序

将所有数统一为同样的数位长度，数位短的前面补零，从最低位开始，依次进行一次排序，这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列

时间复杂度 O(nk)，k 是数位大小

排序稳定

int maxbit(int data[], int n) //辅助函数，求数据的最大位数
{
    int maxData = data[0];              ///< 最大数
    /// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。
    for (int i = 1; i < n; ++i)
    {
        if (maxData < data[i])
            maxData = data[i];
    }
    int d = 1;
    int p = 10;
    while (maxData >= p)
    {
        //p *= 10; // Maybe overflow
        maxData /= 10;
        ++d;
    }
    return d;
/*    int d = 1; //保存最大的位数
    int p = 10;
    for(int i = 0; i < n; ++i)
    {
        while(data[i] >= p)
        {
            p *= 10;
            ++d;
        }
    }
    return d;*/
}
void radixsort(int data[], int n) //基数排序
{
    int d = maxbit(data, n);
    int *tmp = new int[n];
    int *count = new int[10]; //计数器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //进行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for(j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
        for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j < n; j++) //将临时数组的内容复制到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
    delete []tmp;
    delete []count;
}

8. 归并排序

还是分治思想，先把原序列分成 n 个长度为 1 的数，然后两两合并成有序的序列，最后合并完了就是整体有序的序列了

因为不管分还是合都是 log 的，所以时间复杂度是 O(nlogn)

排序稳定

void Merge(int a[], int left, int mid, int right){
    int temp[right - left + 1];                   //临时数组用于存储排序时的数
    int i = left;                                 //分成两块 i指向左边的数字 j指向右边的数字 
    int j = mid + 1;
    int k = 0;                                    //k用于存储数字到临时数组

    while( i <= mid && j <= right ){
        if(a[i] < a[j])                       //永远都是 i 和 j 指向的数进行比较
            temp[k++] = a[i++];                   //谁小，谁就先放到临时数组中
        else
            temp[k++] = a[j++];
    }

    while( i <= mid )                             //如果左边还有数没放上去，就依次放上去
        temp[k++] = a[i++];
    while( j <= right )                           //如果是右边还有同上
        temp[k++] = a[j++];

    for(int m = left, n = 0; m <= right; m++, n++)//读取临时数组中的数
        a[m] = temp[n];
}

void Merge_Sort(int a[], int left, int right){
    if( left == right )
        return;

    int mid = (left + right)/2;
    //递归拆分成较小规模子序列排序 
    Merge_Sort(a, left, mid);            
    Merge_Sort(a, mid + 1, right);
    Merge(a, left, mid, right);      //合并较小规模问题解
}

（五）其他

1. mod

举例：

2. 哈希

将一段数据转化为一个数值，通常采用转进制和取模的方式进行，便于比较

字符串哈希：把出现的字符每个赋不同的值，然后将整个字符串看成一个 b 进制数，这个数 mod 模数 k 就是它的哈希值、

如果想得到字符串 s 从位置 x+1 开始的长度为 n 的子串 s'=s_x,...,s_{x+n-1} 的哈希值，可以预处理出从 1 到 x+n 的哈希值以及 b^n，这样答案就是 H(s')=H(s,x+n)-H(s,x)*b^n

哈希冲突：有小概率情况哈希值会重复，那么这时可以采用“双哈希”，即取不同的模数，如果几个模数得到的哈希值都一样才能判定匹配，例如取 10^9+7 和 10^9+9

数字哈希：把一个序列的数都模上 m 得到的新数列，按照新数列的值作为下标（地址）存储

显然会有哈希冲突，模数会一样，此时可以考虑以下三种方法：

①平方探测法：如果出现重复的模数 i，把 i 变成 (i+1)^2 mod m，继续此步骤直到不冲突

②再哈希法：构造多个不同的哈希函数，发生冲突时用其他的哈希函数计算，问题在于计算时间长

③链地址法：把所有哈希地址相同的值都记录在同一个链表中，例如 m=7 时，1,8 在一个链表里存储

3. 染色

把图的所有节点都用两种颜色染色，若能保证相邻点颜色不同，则说明该图具有可染色行

一定可以染色的图：树、二分图、菊花图

（六）亿些板子

KMP：

int KMP(string S, string T) {
    int ans = -1;
    // i用于遍历主串S
    int i = 0;
    // j用于遍历匹配串T
    int j = 0;
    int next[255]; // 这里初始长度为255,需自行调整
    // 对T做分析，得到next数组
    get_next(T, next);
    while (i < S.size()) {
        // 匹配成功则继续向下一个字符进行匹配
        if (j == -1 || S[i] == T[j]) {
            ++i;
            ++j;
        }
        // 匹配失败进行回溯
        else {
            // j回溯到合适的位置
            j = next[j];
        }
        if (j == T.size()) {
            ans = i - T.size();
            break;
        }
    }
    return ans;
}

exgcd：

int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y), x0 = x, y0 = y;
    x = y0;
    y = x0 - (a / b) * y0;
    return d;
}

int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x); //这里交换了x和y
    y -= (a / b) * x;
    return d;
}

缩点：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#define ll long long
#define MAXN 500005
using namespace std ;

vector <int> G[MAXN] ;//初始图 
vector <int> g[MAXN] ;//缩点后的图 
stack <int> S ; 
int m , n , ans ;
int sta ;
int w[MAXN] , d[MAXN] ;//w点权，d表示该点所属分量 
bool inS[MAXN] ;//inS是否在栈中 ,vis在SPFA ,inQ是否在队列 
int DFN[MAXN] , low[MAXN] ;//Tarjan用 
int cnt , W[MAXN] , num , be , fsum , f[MAXN] ;//缩点信息 

struct node{
    int from , to ;
}way[MAXN];

void Tarjan( int x ) {//求强连通分量，缩点 
    num ++ ;
    DFN[x] = low[x] = num ;
    S.push(x);
    inS[x] = 1 ;
    for(int i = 0 ; i < G[x].size() ; ++ i ) {
        int s = G[x][i] ;
        if( !DFN[s] ) {
            Tarjan( s );
            low[x] = min( low[x] , low[s] );
        }
        else if( inS[s] )
            low[x] = min( low[x] , DFN[s] );
    }
    if( low[x] == DFN[x] ) {
        cnt ++ ;
        int now ;
        do{
            now = S.top() ;
            S.pop();
            d[now] = cnt ;
            inS[now] = 0 ;
            if( now == sta )
                be = cnt ;
            W[cnt] += w[now] ;
        }while( now != x );
    }
}

int main() {
    scanf("%d%d", &n , &m );//基本输入 
    for( int i = 1 ; i <= m ; ++ i ) {
        int a , b ;
        scanf("%d%d", &a , &b );
        G[a].push_back(b);
        way[i].from = a , way[i].to = b ;
    }
    for( int i = 1 ; i <= n ; ++ i )
        scanf("%d", &w[i] );
    scanf("%d%d", &sta );
    for( int i = 1 ; i <= n ; ++ i ) {//缩点 
        num = 0 ;
        if( !DFN[i] )
            Tarjan( i );
    }
    for( int i = 1 ; i <= m ; ++ i ) {//连接缩点后的图 
        int a = d[way[i].from] ;
        int b = d[way[i].to] ;
        if( a != b )
            g[a].push_back(b); 
    }
}

Nim：

#include <iostream>
#include <cstdio>
using namespace std;
int main(){
    int a[1005]={0};
    int ans=0;
    int n; cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        ans^=a[i];
    }
    if(ans)  puts("A");
    else  puts("B");
    return 0;
}

单调队列优化DP：P2034

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    ios::sync_with_stdio(false);
    ll n, m, sum = 0;
    cin >> n >> m;
    vector<ll> A(n + 1), dp(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> A[i], sum += A[i];
    deque<int> Q;
    for (int i = 1; i <= n; ++i)
    {
        if (i > m + 1)
            dp[i] = dp[Q.front()] + A[i];
        else
            dp[i] = A[i];
        if (!Q.empty() && i - Q.front() >= m + 1)
            Q.pop_front();
        while (!Q.empty() && dp[Q.back()] > dp[i])
            Q.pop_back();
        Q.push_back(i);
    }
    cout << sum - *min_element(dp.end() - m - 1, dp.end()) << endl;
    return 0;
}