2020-2021:teams:no_morning_training:week2
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:no_morning_training:week2 [2020/05/15 21:04] shaco [常程] |
2020-2021:teams:no_morning_training:week2 [2020/05/17 00:20] (当前版本) nomansland [王瑞琦] |
||
|---|---|---|---|
| 行 10: | 行 10: | ||
| ---- | ---- | ||
| + | ===比赛=== | ||
| + | 暂无 | ||
| + | ===专题=== | ||
| + | 因为课程刚好讲到图论，所以就顺带学习了一下[[深度优先搜索及其优化]] | ||
| ===== 冯宇扬 ===== | ===== 冯宇扬 ===== | ||
| ===比赛=== | ===比赛=== | ||
| 行 30: | 行 33: | ||
| ==== 王瑞琦 ==== | ==== 王瑞琦 ==== | ||
| + | 比较基础，[[图的多种存储方法]] | ||
| ==== 冯宇扬 ==== | ==== 冯宇扬 ==== | ||
| + | |||
| + | [[2020-2021:teams:no_morning_training:fayuanyu:pou|树链剖分]] | ||
| ==== 常程 ==== | ==== 常程 ==== | ||
| 学了一点数学的东西。（几乎是从头学起，不过我觉得值得推荐，以后做点厉害的） | 学了一点数学的东西。（几乎是从头学起，不过我觉得值得推荐，以后做点厉害的） | ||
| + | [[2020-2021:teams:no_morning_training:shaco:知识点:数论:筛法|筛法]] | ||
| - | ===== 筛法 ===== | ||
| - | ==== 埃氏筛 ==== | ||
| - | === 思想 === | ||
| - | 从每个素数出发，将其倍数都筛掉。 | ||
| - | === 性能 === | ||
| - | 每一个合数会被访问多次；复杂度$O(nloglogn)$。 | ||
| - | === 代码 === | ||
| - | <code cpp> | ||
| - | for(int i=2;i<=maxn;i++) | ||
| - | { | ||
| - | if(!vist[i]) | ||
| - | for(int j=i*i;j<=maxn;j+=i) | ||
| - | vist[j]=1; | ||
| - | } | ||
| - | </code> | ||
| - | ==== 线性筛（欧拉筛）==== | ||
| - | === 思想 === | ||
| - | 对于每一个i，寻找素数使得与i的乘积中该素数为最小因子。由于每一个数的最小因子一定，该数就被唯一地访问。 | ||
| - | === 性能 === | ||
| - | 避免了重复访问；复杂度$O(n)$（？）。 | ||
| - | === 代码 === | ||
| - | <code cpp> | ||
| - | for(int i=2;i<=maxn;i++) | ||
| - | { | ||
| - | if(!vist[i]) | ||
| - | prime[++t]=i; | ||
| - | for(int j=1;j<=t&&i*prime[j]<=maxn;j++) | ||
| - | { | ||
| - | vist[i*prime[j]]=1; | ||
| - | if(!(i%prime[j])) | ||
| - | break; | ||
| - | } | ||
| - | } | ||
| - | </code> | ||
| - | 杜教筛、min_25筛、洲阁筛学到积性函数再补。 | ||
2020-2021/teams/no_morning_training/week2.1589547887.txt.gz · 最后更改: 2020/05/15 21:04 由 shaco
