2020-2021:teams:alchemist:weekly_digest_2
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:weekly_digest_2 [2020/05/15 11:52] maxdumbledore [陈铭煊 Max.D.] |
2020-2021:teams:alchemist:weekly_digest_2 [2020/05/19 16:24] (当前版本) mountvoom [肖思炀 MountVoom] |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| 本周是比较摸的一周，主要学习了一下广义后缀自动机（不敢说自己已经会了），稍微写了下FWT的知识库。 | 本周是比较摸的一周，主要学习了一下广义后缀自动机（不敢说自己已经会了），稍微写了下FWT的知识库。 | ||
| ===== 龙鹏宇 Hardict ===== | ===== 龙鹏宇 Hardict ===== | ||
| + | |||
| + | 摸鱼ing | ||
| + | |||
| + | 学习了递推容斥系数计算,学习了三次剩余(非BSGS) | ||
| ===== 肖思炀 MountVoom ===== | ===== 肖思炀 MountVoom ===== | ||
| + | 这周是特别摸的一周，补了补题，没学啥新东西。 | ||
| + | |||
| + | 摸了一套[[https://codeforces.com/contest/1352|div.4]]和一套[[https://codeforces.com/contest/1353|div.3]]，等明天再摸一套[[http://codeforces.com/contest/1354|div.2]]。 | ||
| + | |||
| + | 爬去写作业了。 | ||
| ====== 本周推荐 ====== | ====== 本周推荐 ====== | ||
| ===== 陈铭煊 Max.D. ===== | ===== 陈铭煊 Max.D. ===== | ||
| 行 14: | 行 23: | ||
| rope对于序列的插入、删除、替换、拼接、切片等操作快速到了$\log n$级别。这是vector或者string所不具备的，因为后者的这些操作，基本上都要对元素进行整体移位。可想而知，其内部是使用了某种BST的结构。BST的每一个结点，代表了一个序列区间，而子节点则进一步划分成了两个子区间——我们自己手写像Splay、Treap这样的BST，也能比较轻松地达到rope的要求。 | rope对于序列的插入、删除、替换、拼接、切片等操作快速到了$\log n$级别。这是vector或者string所不具备的，因为后者的这些操作，基本上都要对元素进行整体移位。可想而知，其内部是使用了某种BST的结构。BST的每一个结点，代表了一个序列区间，而子节点则进一步划分成了两个子区间——我们自己手写像Splay、Treap这样的BST，也能比较轻松地达到rope的要求。 | ||
| - | rope的另外一大能力，是进行可持久化，或者说“写时复制”——在rope进行复制或者部分复制时，BST会尽量利用原序列已有的部分，在对新串进行修改时，才新建部分节点。这种可持久化，能够帮助我们实现一些手写比较困难的数据结构，例如洛谷3369 可持久化平衡树，代码详见个人主页。 | + | rope的另外一大能力，是进行**可持久化**，或者说“写时复制”——在rope进行复制或者部分复制时，BST会尽量利用原序列已有的部分，在对新串进行修改时，才新建部分节点。这种可持久化，能够帮助我们实现一些手写比较困难的数据结构，例如**洛谷3369 可持久化平衡树**，代码详见个人主页。 |
| 但rope的缺点也是显而易见的——没有办法对区间添加额外的域进行维护（比如没有办法快速求区间和，没有办法进行快速区间翻转，这里快速是指的$\log n$级别），另外常数也是比手写的平衡树大了不少。这些场合还是建议手写（当然，pb_ds中的BST可以弥补这一点，但是额外的代码不必手写简单多少）。 | 但rope的缺点也是显而易见的——没有办法对区间添加额外的域进行维护（比如没有办法快速求区间和，没有办法进行快速区间翻转，这里快速是指的$\log n$级别），另外常数也是比手写的平衡树大了不少。这些场合还是建议手写（当然，pb_ds中的BST可以弥补这一点，但是额外的代码不必手写简单多少）。 | ||
| 行 30: | 行 39: | ||
| ===== 龙鹏宇 Hardict ===== | ===== 龙鹏宇 Hardict ===== | ||
| + | |||
| + | $平面图边数至多为3|V|-6(V+F-E=2,F至多2|V|-4)$ | ||
| + | |||
| + | **含递推关系的期望问题** | ||
| + | |||
| + | $对递推\sum_{i=0}^{n} a_{i}f_{m-i}=0,(a_{0}一般为0以求解f_{m})\\ | ||
| + | 递推的特征多项式为\sum_{i=0}^{n}a_{i}x^{n-i}=0,联接多项式为\sum_{i=0}^{n}a_{i}x^{i}=0$ | ||
| + | |||
| + | $P(x)=\sum_{i=0}^{\infty} p_{i}x^{i},p_{i}为概率i,p_{i}具有线性递推关系,那么期望即P^{'}(1)$ | ||
| + | |||
| + | $考虑H(x)=P(x)G(x),G(x)为递推的联接多项式,后|G(x)|项都应为0$ | ||
| + | |||
| + | $P^{'}(1)=\frac{H^{'}(1)G(1)-H(1)G^{'}(1)}{G(1)^{2}}$ | ||
| + | |||
| + | $实际计算时,若P(x)截取2n项,G(x)由BM算法不超过n项,H(x)也应该只截取前2n项$ | ||
| + | |||
| + | [[http://codeforces.com/gym/102268/problem/E|例题]] | ||
| ===== 肖思炀 MountVoom ===== | ===== 肖思炀 MountVoom ===== | ||
| + | |||
| + | 不知道推荐什么好，就推荐一道[[https://ac.nowcoder.com/acm/contest/5477/H|数据结构题]]吧。 | ||
| + | |||
| + | [[http://112.74.186.118/doku.php?id=2020-2021:teams:alchemist:mountvoom:training1|题解]] | ||
2020-2021/teams/alchemist/weekly_digest_2.1589514775.txt.gz · 最后更改: 2020/05/15 11:52 由 maxdumbledore
