首师大附中集训
关注
分享
扫一扫
记录与总结
Deep_Kevin
这个作者很懒，什么都没留下…
展开
-
专题总结：数据结构
正题 今天讲的是数据结构 树状数组 树状数组在竞赛中是一种主要用来实现以下操作的数据结构。 维护一个长度为 n 的数组，要求支持 2 种操作。 1. 更改一个位置的权值 2. 询问前缀和 两种操作的时间复杂度均为 O(log n) 原理就不多说了 树状数组支持的操作确实被线段树完全包...原创 2019-08-04 21:06:05 · 361 阅读 · 0 评论 -
首师大附中集训第十一天：OI炼金术
正题 今天给我们上课的老师很有趣。 交给我们不只是一些题，还有一些题的入手方法，如何把题面转化为题解才是最重要的。 OI选手经常遇到的痛点 看了题解之后：啊，好简单，我咋没想到呢？ 这题我想出来了，但是那个***我不会写啊？！！！ 咦？好像有bug……（an hour later）怎么还调不对啊！zbl ...原创 2019-08-01 20:11:32 · 446 阅读 · 0 评论 -
首师大附中集训第十天：数论积性函数
正题 今天对于我来说相当于啥都没讲。。。 因为这些东西在我之前的blog已经写过了。 想要学习可以去看我的学习笔记：基本数论函数和杜教筛 原谅我水了一篇blog。...原创 2019-08-01 13:17:18 · 262 阅读 · 0 评论 -
首师大附中集训第九天：快速沃尔什变换和生成函数
正题 FWT 说的是生成函数，其实今天讲了很多很多多项式的内容。 FWT我就不讲了，前面的学习笔记有题到，在这里只放几道简单的例题。 例题1：51nod 1773 A 国是一个神奇的国家。这个国家有 2 个城市，每个城市都有一 个独一无二的编号，编号范围为 0 − −2 n − 1。 A 国的神奇体现在，他们有着神奇的贸易规则。...原创 2019-07-30 21:22:34 · 369 阅读 · 0 评论 -
首师大附中集训第八天：动态Dp和数位Dp
正题 动态动态规划 指出对DP的输入进行修改，在每次修改后快速求出DP值 最经典的动态dp： 单点修改，最大子段和（区间和） 某些子结构的dp值：区间的最大子段和 基本思路：分治 序列上和树上都能做 WC2018 猫 圆方树讲课中提到，NOIP2018 某道题可以用 经典问题：询问一个区间的最...原创 2019-07-29 20:12:29 · 249 阅读 · 0 评论 -
首师大附中集训第七天：最小生成树
正题 “诶，今天讲最小生成树哎。不听了，我刷我自己的题。。”------来自某位神犇。 太难了。 求解最小生成树有两种方法Kruskal和Prim算法，图较为稀疏的情况下，我们一般选择前者。图较为稠密的情况下，我们一般选择后者。 只讲一些我原先不懂得例题。（即使我懂的也就那几道。。。 例题1：动态图连通性 给定一个...原创 2019-07-28 21:35:47 · 302 阅读 · 0 评论 -
首师大附中集训第六天：动态规划 Plus（插头Dp
正题 一开始傻傻的我没搞懂第三题，所以就一直在找第三题的题解，恍然大悟发现自己错过了两道题。 树形动态规划 基本思想： 设计状态：和子树相关的状态。 转移：先考虑子树的所有状态，再考虑该节点的状态。 边界条件：叶节点的情况最简单。 放两道错过的例题：IOI 2015河流，NOI 2002 ...原创 2019-07-27 19:49:04 · 178 阅读 · 0 评论 -
首师大附中集训第五天：动态规划
正题 默认已经会的内容： 1.记忆化搜索的基本方法 2.常见的动态规划模型 3.背包 4.区间（石子合并） 5.LIS LCS 回文 6.基本的树dp 7.基本的数位dp 8.基本的状态压缩dp 9.简单的动态规划优化 将多重背包转化成01背包...原创 2019-07-26 20:09:52 · 333 阅读 · 0 评论 -
首师大附中集训第四天：杂
正题 今天讲的是一些杂题 一开始的是一些搜索。 1.长度为N的数列，已知N个前缀和以及N个后缀和共2N个数打乱后的结果，已知数列中每个数的范围是不超过500的整数，求原数列，存在多组时间求字典序最小的。1<=N <= 1000 我们考虑将整个序列从小到大排序，然后第一个元素一定是F[1]或者G[1]。就这样按顺序得向下选，就可以...原创 2019-07-25 20:18:51 · 256 阅读 · 0 评论 -
首师大附中集训第三天：分治Plus & 分块
正题 将一个集合划分成若干个规模较小的子集合，一般来说，我们倾向于把性质接近的元素分到同一个子集里面，并把每个子集的元素按照一定结构组织起来，形式主要有两种： 1.线形序列的分块化 2.树形结构的分块化 先讲讲现行序列的分块化。 线形序列预处理：在分好块之后，尝试对线性序列进行预处理。当查询任意区间的时候，对于预处理的部分直接返...原创 2019-07-24 20:52:47 · 374 阅读 · 0 评论 -
首师大附中集训第二天：分治与二分
正题 分治 分治分治，分而治之，分治算法就是将一个大问题划分为几个更小规模的形式相同的子问题并加以解决，通过解决子问题最后解决总问题。 分治算法在OI中的运用主要在两个方面 1.二分查找、三分查找、二分答案 2.直接考察分治 基本运用：归并排序，快速幂 例题：Luogu P1228，SP22343 NOR...原创 2019-07-23 19:41:09 · 372 阅读 · 0 评论 -
首师大附中集训第一天：搜索
正题 搜索要明确状态，操作，性质，事先思考怎么搜合适，即怎么搜会更快，不要碰到题就开始搜，剪枝也最好在写题前写好想好，剪枝放在一起放在最前面。 搜索的本质：一棵树或图。 特征：1.树或图较大，无法存储。（存的下就可以Dp，递推，也就是记忆化搜索 2.限制条件比较充分。 在做题的时候考虑三个方面： 1.当前搜的状态，...原创 2019-07-22 19:20:34 · 228 阅读 · 0 评论