CSP考前复习

基础模板 - 排序专题 $sort$

基础模板(一) 快速排序

785. 快速排序 - AcWing题库

给定你一个长度为n的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;//注意数据范围
int n,s[N];//定义类型为int的变量n，以及数组s

void quick_sort(int q[],int l,int r){//传入数组q，以及需要进行排序的左端点和右端点
    if(l >= r) return;//如果左端点与右端点重合或在右端点的右面，则跳出函数
    int x = q[l + r >> 1],i = l - 1,j = r + 1;//x记录q数组的正中间的值
    //i从左面开始扫描，j从右面开始扫描
    //i赋值为l - 1是为了方便do while循环，j赋值为r + 1亦是如此
    while(i < j){
        do i++;while(q[i] < x);//从左边向右边扫描，找到第一个大于等于x的数
        do j--;while(q[j] > x);//从右边向左边扫描，找到第一个小于等于x的数
        if(i < j) swap(q[i],q[j]);//如果i仍在j的左面，说明这两个数仍是无序的，需要排序
    }
    quick_sort(q,l,j);//传入当前排好序的的q数组，对q[l~j]的数进行进一步排序（前半部分）
    quick_sort(q,j+1,r);//传入当前排好序的的q数组，对q[j + 1 ~ r]的数进行进一步排序（后半部分）
}

int main(){
    //输入
    cin >> n;//读入n
    for(int i = 0;i < n;i++) cin >> s[i];//读入数组s
    //将数据进行处理
    quick_sort(s,0,n - 1);//将s数组进行快速排序
    //输出
    for(int i = 0;i < n;i++) cout << s[i] << ' ';//将排好序的数组s输出
    return 0;
}

基础算法(二) 归并排序

787. 归并排序 - AcWing题库

给定你一个长度为n的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;//看准数据范围
int a[N],n,t[N];//a -> 输入数组, t -> 临时数组

void merge_sort(int q[],int l,int r){//传入要排序的数组q，以及左端点和右端点
    if(l >= r) return;//如果左端点与右端点重合或在右端点的右面，则跳出函数
    int mid = l + r >> 1;//找中间点
    merge_sort(q,l,mid);//对数组的前半部分进行排序[l ~ (l + r) / 2]
    merge_sort(q,mid+1,r);//对数组的后半部分进行排序[(l + r) / 2 + 1 ~ r]
    int i = l,j = mid + 1,k = 0;//将临时数组t进行填充
    //i从左端点开始扫描，j从中间点开始扫描
    while(i <= mid && j <= r){//i在l ~ mid,j在mid + 1 ~ r
        if(q[i] <= q[j])t[k++] = q[i++];
        else t[k++] = q[j++];
        //看哪部分大就填入哪部分
    }
    while(i <= mid) t[k++] = q[i++];
    while(j <= r) t[k++] = q[j++];
    //i或j中是否还有没有填完的(只存在一个没有填完)
    for(int i = l,j = 0;i <= r;i++,j++) q[i] = t[j];
    //将临时数组t -> 原始数组q 方便进行下一步排序
}

int main(){
    //输入
    cin >> n;//读入数组长度n
    for(int i = 0;i < n;i++) cin >> a[i];//读入要排序的数组a
    //将数据进行进一步处理
    merge_sort(a,0,n-1);//归并排序
    //输出
    for(int i = 0;i < n;i++) cout << a[i] << ' ';//将排好序的数组a输出
    return 0;
}

基础模板 - 位运算专题 $bitwise$

基础模板(三) 位运算基本符号作用

基础模板(四) 位运算运算顺序(包括其他运算符)

算数、关系、逻辑，按位操作放中间

基础模板(五) 判断2的整数次幂

if(!(n & (n - 1)))
    则n是2的整数次幂

基础模板 - 搜索专题$dfs bfs$

基础模板(六) dfs-全排列

#include<bits/stdc++.h>
using namespace std;

const int N = 10;

int n;
int path[N];
bool st[N];

void dfs(int u){
    if(u == n){//所有位置都已经存满了，可以输出了
        for(int i = 0;i < n;i++) cout << path[i] <<' ';
        cout << endl;
        return;//返回，接着搜索下一种可能
    }
    for(int i = 1;i <= n;i++){
        if(!st[i]){//数字没有被标记过才可以使用
            path[u] = i;//储存路径（选择的数字）
            st[i] = true;//标记已经使用过了
            dfs(u + 1);//深搜下一位
            st[i] = false;//恢复现场
        }
    }
}

int main(){
    cin >> n;//输入
    dfs(0);//开始爆搜

    return 0;
}

基础模板(七) 八（n）皇后问题

#include <bits/stdc++.h>
using namespace std;

int bfs(string start){
    queue<string> q;//存储每次产生的新字符串
    unordered_map<string, int> d;//记录变换到当前形式需要几步

    q.push(start);//放入初始字符串
    d[start] = 0;//初始字符串 -> 初始字符串 需要0步

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//依次枚举x上下左右数字

    string end = "12345678x";//最终结果
    while (q.size()){
        auto t = q.front();//当前队头的字符串
        q.pop();

        if (t == end) return d[t];//出口

        int dis = d[t];//当前 队头字符串 变换所需时间
        int k = t.find('x');//找到 x 的位置
        int x = k / 3, y = k % 3;//转化为 二维 的形式存储
        for (int i = 0; i < 4; i ++ ){//依次枚举
            int a = x + dx[i], b = y + dy[i];//确定x周围选定数字位置
            if (a >= 0 && a < 3 && b >= 0 && b < 3){//边界位置
                swap(t[a * 3 + b], t[k]);//交换二者位置
                if (!d.count(t)){//当前字符串未被记录
                    d[t] = dis + 1;//对应距离加1
                    q.push(t);//将当前字符串进入队列
                }
                swap(t[a * 3 + b], t[k]);//恢复现场
            }
        }
    }

    return -1;
}

int main(){
    string start;
    //输入
    for (int i = 0; i < 9; i ++ ){
        char c;
        cin >> c;
        start += c;//将每次输入的数依次拼接
    }
    //输出
    cout << bfs(start) << endl;

    return 0;
}

基础模板 - 数学问题专题$maths$

基础模板(八) 判断质数问题

常见题型：分解质因数，质数判断等

1. 试除法判断质数

#include<bits/stdc++.h>
using namespace std;

int n,a;

bool prime(int t){
    if(t < 2) return false;
    for(int i = 2;i <= t / i;i++)//循环为了加快速度，可以只到t / i
        if(t % i == 0) return false;
    return true;

int main(){
    cin >> n;
    while(n--){
        bool flag = true;
        cin >> a;
        if(prime(a)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }

    return 0;

2. 分解质因数

#include<bits/stdc++.h>
using namespace std;

int n,a;

void to_prime(int t){
    int cnt = 0;
    for(int i = 2;i <= t/i && t != 0;i++){
        cnt = 0;
        while(t % i == 0 && t != 0){
            t /= i;
            cnt++;
        }
        if(cnt) printf("%d %d\n",i,cnt);
    }
    if(t > 1) printf("%d 1\n",t);
}

int main(){
    cin >> n;
    while(n--){
        cin >> a;
        to_prime(a);
        cout << endl;
    }

    return 0;
}

3. 筛质数(提高速度)

线性筛法

#include<bits/stdc++.h>
using namespace std;

const int N= 1000010;

int primes[N], cnt;
bool st[N];

void get_primes(int n){
    for (int i = 2; i <= n; i ++ ){
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ ){
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main(){
    int n;
    cin >> n;

    get_primes(n);

    cout << cnt << endl;

    return 0;

朴素筛法

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;

int primes[N], cnt;
bool st[N];

void get_primes(int n){
    for (int i = 2; i <= n; i++){
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

int main(){
    int n;
    cin >> n;

    get_primes(n);

    cout << cnt << endl;

    return 0;
}

基础模板(九) 最大公约数

辗转相除法

#include<bits/stdc++.h>
using namespace std;

int n;
int a,b;

int main(){
    cin >> n;
    while(n--){
        cin >> a >> b;
        int tmp = a % b;
        while(tmp){
            a = b;
            b = tmp;
            tmp = a % b;
        }
        cout << b << endl;
    }

    return 0;
}

递归写法

#include<bits/stdc++.h>
using namespace std;


int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}


int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", gcd(a, b));
    }

    return 0;
}

rp++