八月份杭州X02笔记整理~（1/3）

133****3286

2023-08-20 14:45:03

发布于：浙江

29阅读

0回复

0点赞

Day1 上午第一课算法入门

Part 1 算法的定义

Part 2 时间复杂度

Part 3 空间复杂度

Part 4 素数问题

1）埃筛

原理：将所有不大于 $\sqrt{n}$ 的所有质数的倍数剔除，剩下的自然数就是质数；
模板：

const int N = 100000010;
bool vis[N]; // true 非素数   false 素数
void sieve(int n){
    vis[0] = true;
    vis[1] = true;
    for(int i = 2; i <= n / i; i ++){
        if(vis[i] == false){
            for(int j = i * i; j <= n; j += i){
                vis[j] = true; 
           }
        }
    }
}

2）线性筛

原理：每个非质数只被其最小的质因子对应的最大整数因子剔除唯一分解定理历史唯一分解定理数学解释
模板：

const int n = 1000;
int prime[n+10], pi = 0;
bool vis[n+10] = {0};
void primeInit(int n) {
    for (int i=2; i<=n; i++) {
        if (vis[i]==false) {
            prime[++pi] = i; // 未被标记则是质数
        }
	for (int j=1; j<=pi; j++) {
	    if (prime[j]*i>n)  break;
	    vis[prime[j]*i ] = true; // 用当前数 i 进行筛
 	    if (i%prime[j]==0) break; // i*prime[j+1] 可以被之后的数筛
 	}
    }
}

Day1 下午第二课 STL模板

Part 1 vector

常用成员函数：

函数名	作用	时间复杂度
val.push_back(data)	对val向后插入data	O(1)
val.pop_back(data)	删除尾数据	O(1)
val.size()	val内元素个数	O(1)
val.clear()	清空val	O(N)
val.begin()	起始迭代器	/
val.end()	末尾迭代器	/
val.empty()	判空	/

Part 2 set

常用成员函数：

函数名	作用	时间复杂度
val.insert(data)	对val插入data	O(log(N))
val.erase(it)	1.删除一个it迭代器所指的位置	O(1)
val.erase(it)	2.删除值为it的数据	O(log(N))
val.erase(first,last)	3.删除迭代器于{last,first}的数据	O(last-first)
val.size()	val内元素个数	O(1)
val.clear()	清空val	O(N)
val.begin()	起始迭代器	/
val.end()	末尾迭代器	/
val.find(data)	在val中寻找data	O(log(N))

模板

Part 3 map

常用成员函数：

函数名	作用	时间复杂度
mp.erase(it)	1.删除一个it迭代器所指的位置	O(1)
mp.erase(it)	2.删除键为it的数据	O(log(N))
mp.erase(first,last)	3.删除迭代器于{last,first}的数据	O(last-first)
mp.size()	键的个数	O(1)
mp.clear()	清空	O(N)
mp.begin()	起始迭代器	/
mp.end()	末尾迭代器	/

Day2 上午第三课课前缀和与差分

Part 1 前缀和与区间和

Part 2 差分与区间修改

Day2 下午第四课递归与递推

Part 1 递归

Part 2 递推

Part 3 例题

（1）平行线分割平面

（2）错排问题

Day3 上午第五课贪心算法

Part 1 概念

Part 2 例题

活动排序

const int N = 1010;
struct Act{ int s, t; };
bool cmp(Act a, Act b) { return a.t < b.t; }
Act act[N];
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> act[i].s >> act[i].t;
sort (act + 1, act + 1 + n, cmp);
int cnt = 1;
int endTime = act[1].t;
for (int i = 2; i <= n; i++) {
    if (act[i].s >= endTime) {
        cnt++ ;
        endTime = act[i].t;
    }
}
cout << cnt << endl;

Day3 下午第六课二分

Part 1 二分搜索

查找x

int findx(int a[], int left, int right, int x) {
    int mid, ans;
    while (left <= right) {
        mid = (left + right) / 2;
        if (x <= a[mid]) {
            ans = mid;
            right = mid - 1;
        } 
        else {
            left = mid + 1;
        }
    }
    return a[ans] == x ? ans : -1;
}

Part 2 lower_bound and upper_bound

sort 样例代码

// 根据 check 函数对二分值的判定，选择收缩的空间。
bool check(double sq, int x) {
    if (sq * sq - x < 0) return true;
    else return false;
}
const double eps = 1e-6;
double msqrt(int x) {
    double l = 0, r = x;
     double mid;
    while (abs(r - l) > eps) {
        mid = (l + r) / 2;
        if ( check(mid, x) ) {
            l = mid;
        } 
        else {
            r = mid;
        }
    }
    return r;
}

Day4 归并，快排和高精度

Part 1 归并排序

样例代码

void merge_sort(int a[], int l, int r) {
    int mid = l + (r - l) / 2;
    if (l < mid) merge_sort(a, l, mid);
    if (mid + 1 < r) merge_sort(a, mid + 1, r);
    int t[N];
    int i, j, k;
    for (i = l, j = mid + 1, k=1; i <= mid || j <= r; k++) {
        if (i <= mid && j <= r) {
            if (a[i] < a[j]) t[k] = a[i++];
            else t[k] = a[j++];
        }
        else if (i > mid) { t[k] = a[j++]; }
        else { t[k] = a[i++]; }
    }
    for (i = l, j = 1; i <= r; i++, j++) { a[i] = t[j]; }
}

Part 2 快速排序

Part 3 高精度算法

背景

加法

减法

乘法

####除法

Day5 上午第九课栈和队列

Part 1 栈

实验性代码^[1]

#include <iostream>
using namespace std;
int st[100];int tot = 0;
 /*
操作数 1，插入 x
操作数 2，退栈
操作数 3，输出栈数据 
*/
int main() {
    for (; ;) {
        int opr, x;
        cin >> opr;
        switch(opr) {
            case 1:
                 cin >> x;
                st[++ tot] = x;
                break;
            case 2:
                if (tot > 0) tot --;
                else cout << "empty" << endl;
                break;
            case 3:
                cout << "Stack: ";
                for (int i = 1; i <= tot; i ++) {
                    cout << st[i] << ' ';
                }
                cout << endl;
                break;
        }
    }		
    return 0;
}

Part 2 队列

实验性代码

#include <iostream>
using namespace std;
int que[100];
int f, r;
/*
操作数 1，入队 x
操作数 2，退队
操作数 3，输出队列 
*/
int main() {
    for (; ;) {
        int opr, x;
        cin >> opr;
        switch(opr) {
            case 1:
                cin >> x;
                que[r ++] = x;
                break;
            case 2:
                if (f < r) f ++;
                else cout << "empty" << endl;
                break;
            case 3:
                cout << "Queue: ";
                for (int i = f; i < r; i ++) {
                    cout << que[i] << ' ';
                } 
                cout << endl;
                break;
        }
    }
    return 0;
}