~~~~今天是来到小码王集训营正式上课的第一天，虽然说前一天晚上宿舍进了两只猴子（帅气的室友）大闹宿舍，没睡好，但早上还是很兴奋，然后就去吃了早饭(非常不错）然后开始魔鬼训练*上午讲了
**Part 1 算法的定义
Part 2 时间复杂度
Part 3 空间复杂度
Part 4 素数问题
1） 埃筛
原理：将所有不大于
𝑛
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; // iprime[j+1] 可以被之后的数筛
}
}
}
然后去吃了超级无敌好吃的中饭*
下午上了
**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() 末尾迭代器 /**
然后吃完巨好吃的晚饭（有学校千年难见的鸡排）额（反正我们学校是千年难遇）
然后就到了现在（此时此刻）
老师发了一本超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超超厚的算法竞赛的书（感觉有一种更魔鬼的感觉………………
等会还有模拟考试（每天都要）
额祝我好运吧
***
