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

userId_undefined

133****3286

倔强青铜

2023-08-20 14:45:03

发布于：浙江

30阅读
0回复
0点赞

Day1 上午 第一课 算法入门

Part 1 算法的定义


Part 2 时间复杂度

Part 3 空间复杂度


Part 4 素数问题

1） 埃筛

原理：将所有不大于 n\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;
}

Part 3 前后中缀表达式

长度不够喽，第二部分在这里

  1. 实验性代码指通过代码可视化等手段来更好的发现问题，完成纠错等环节，在后面的笔记中还会有很多 ↩︎

userId_undefined
去预览
0/2000

全部评论 1

  • userId_undefined

    133****3286

    倔强青铜

    下半部分也更完了哈，按链接跳转

    2023-08-20 来自 浙江

    0

热门讨论