[学习笔记] 集训总结

oi
  1. 1. 集训总结
    1. 1.1. 2018/2/3
    2. 1.2. 半夜了,2018/2/4
    3. 1.3. 2018-2-5 边学变总结
    4. 1.4. 2018/2/5 睡前总结
    5. 1.5. 2018/2/6 计划
    6. 1.6. 2018/2/6学习总结

集训总结

这里是第一轮集训的总结


2018/2/3

oi日记
嘛,今天学习的东西还真的蛮多的qwq
为了防止忘记,这里就记一下今天学习了啥东西qwq
就从早上说起吧qwq

  1. 离散化
    离散化的基本思想是将数列排序后对应到一个数组里去
    离散化之前是采用数字本身映射,离散化后采用数字的下标映射
    当然我现在只用过一个离散化的思想,正好也是今天的。树状数组求逆序对,然而我还没写完。
  2. 那个骚dp
    那个贼骚的dp应该是我做过的第一个状压dp了,没做起是废话
    不过提供了两个东西
  • 素数筛,采用bool数组计算某一个数字内的所有素数,效率是比较高的。
    对了,这是我第一次见状压的题qwq所以自然很不熟悉qwq…
    所以就把所有新东西都当成骚操作了…和草十郎新到城市里的感觉一样吧qwq…
    骚操作记录如下
    状态压缩通常是把一个数压缩成二进制来表示
    就说今天的素数题吧
    有一个性质需要记录一下
    1000以内的数字最大的质因数是小于等于33的。所以只用压缩33以内的数字,33以外的再单独讨论。单独讨论的方法以后可能会用到很多次。
    状态压缩的转移通常是”|” 就是求并集,在某种特定条件下,求一个并集,就转移到了下一个状态了。
    类似题cf895c // TODO
  1. 我刚刚想说啥来着…对了,就是求末尾有多少个0的问题
    今天遇到的 cf837d,虽然wa了…但是我还是有话说qwq…
    837大概是一个求末尾有多少个0的…只要记住需要2,5就对啦!记住就对了qwq总不会没用
  2. 逆序对有两种求法…我个人比较喜欢树状数组….因为优雅嘛…具体的在learning/template/逆序对.cpp里,需要看的话就自己看qwq…
  3. 以后考试不要紧张,随时引用之前的知识…不要学专题学傻了,雪耻。现在自己做的题目还是太少了,作为经验主义者,这怎么行!所以要加紧做题的速度,抓紧这剩下四天的时间,争取每天都总结很多东西,

// TODO 离散化并查集
cf895d
学长给的第二道 /contest/20180203里 暂时没复制标程
lyd之后的几页辣!加油啊!!!


半夜了,2018/2/4

今天的总结
其实现在是2/5,看了一会儿Qizy学长的文件…深深的…膜拜…太恐怖了…
先不说这个
今天学了啥
说实话今天的效率挺低的..因为遇上了一个史诗级码力题…开车旅行。
倍增才学不到五分钟,就来这道题,也太变态了点..作为初学者表示强力谴责,到了现在都没做出来…算了也罢
先不说这个,先看看今天学长给的资料
苦逼了,之前没学过lca,只能现场无力yy。
看看第一个题
$ 10^7 $的数据量,RMQ问题
之前听说了这种问题。蓝书上有个备注
// ——-以上全是废话——–

  1. 并查集的骚操作
    之前总结过,这次大概是深刻了一点。
    并查集能做的远远不止是这点。
    对于跳跳的功能,并查集还是很完善的。
    比如说这个
    我们定义位置i, 它的father是father[i]
    f[i]表示[i, father[i]]的最小值/最大值
    然后在走动的时候路径压缩
    今天和LR纠结了半天这道题…
    在shadypi的帮助下解决了qwq…
    先把区间排序,只能离线了,
    不过要保证O(n)的复杂度…只能基数排序了。带个大常数至少保证了复杂度对不对qwq
    第二点,拿第一次查询举例子
    [2, 4]的值是2 3 1
    那么我们把father[2] = 4;
    father[3] = 4;
    father[4] = 4;
    定义$ c_i $为i位置到father[i]的最小值
    所以在在走的时候动态维护
    其实自己在写这篇日记的时候也没有写过代码,到时候只能现场yy
  2. 倍增lca,完全没懂,跳过(
  3. st表的意义(举例子
    st表相对于开车来说才是我今天最重要的意义之一…
    因为开车本身没有涉及到很多倍增的东西。
    倍增的本质,就是利用任何整数都可以由二进制合成
    的性质。和昨天前天总结的妙妙的快速幂由类似的意义。
    倍增是$ O(n^2) $枚举的最好方法
    优化到$ O(n\log{n}) $
    并查集是“信息复用”的优化方法
    优化到$ O(\alpha(n)) $
    动态规划是指数级复杂度的优化方法
    优化到以上的三种
    #####
    这道题还没做完,倍增这个的总结留到明天
    明天的效率一定要高起来,这里留一个list

2018-2-5 边学变总结

  1. 说到排序动态加多个点

其实还可以并归排序
这可以算是信息复用?
并归排序的合并是把两个原本有序的数列合并起来
如果是两个完全无关的数列,其实也是可以合并的说
蛮好的方法哎嘿嘿
其实平衡树也可以

  1. 对了,倍增的用处不仅仅是这里的那一点

也不仅仅是st表那样递推的倍增
还有一点点二分的性质
如果满足的话,当前状态拓宽一倍
如果不满足的话,当前状态缩小至1/2
until -> 0
今天的那个context adxxxxxx就可以解了
具体实现还没想好…

  1. 关于k步最短路我有个脑洞

前天做了一个恰好k个的背包问题
定义的状态是f[k][j]
是选k个,j个2的最大值
同样的,可以转化一下SPFA的dist的状态
转化为dist[k][i],选k个点到达i的最小值是
那么 转移的时候
$$ dist[k][to] = min(dist[k - 1][to] + val, dist[k][to]); $$
当已经选择了k个的时候,就不选了,状态无法转移…dist[k][to] = ….
哎貌似可以做哎…
我忽略了一点很重要的
通常来说,需要用到倍增的时候不是枚举。而是可以信息复用的东西。
信息复用也可以用并查集来做,时间复杂度一个nlogn一个n
但是并查集的要求要高一些,很多情况不能用

2018/2/5 睡前总结

嘛,今天并没有完成昨天的计划,回家之后就写作业和搞博客le…
不过,还是学了一会lyd的。

  1. 贪心的骚操作远远不止LR之前给我看的那一个,具体来说,就是线段覆盖和。。和各种骚操作。
    今天做了一个演示文档,有意的人可以看一看qwq…
  2. 说起来今天真的没什么可以总结的,毕竟前面都写过了,说起来还有一个,我放在上一篇博客里的,不过仅仅是脑洞题,我还是看了题解写出来的…说到底没啥意义。
    嘛,晚安,明天加油。

2018/2/6 计划


早上日常的。如果有考试的话就考试,考试的时候随时想这道题离线还是在线,是不是骚操作?是哪一种类型的。呜啊我不想爆零。

还有各种的,Qizy学长总结了一套,慢慢学着用。

如果没有考试的话,八成又要学习新东西,认真听讲,听不懂就问呜呜呜啊啊啊。不然一个下午都要泡在问题上。

如果搞懂了,下午继续lyd,把第一章的习题刷完。

晚安qwq…

失败不可怕,可怕的是失败之后还一无所有。

2018/2/6学习总结


今天主要是学习新知识上面,而且注重的是理解…所以知识点偏少。

  1. 拓展欧几里得。gcd的拓展,同模方程组的证明见github上的课件。一般遇到拓欧的题目是想办法化为$ax + by = \mathrm{gcd}(a, b)$, 然后用exgcd求出方程的解。公式需要记住,模板必须被着。

    1
    2
    3
    4
    template<typename T>
    inline void exgcd(T a, T b, T &g, T &x, T &y) {
    !b ? (x = 1, y = 0, g = a) : (exgcd(b, a % b, g, y, x),y -= (a / b) * x);
    }
  2. 要说今天主要的时间还真的就在exgcd上了…啊啊啊学习的东西好少,明天要好好做才行…希望能够把现在没学习到什么东西的罪恶感拖到明天早上qwq,数学的一天啊…是第一次接触数论呢。

  3. 2018/2/7的预告

    • 学习lyd的第二章,顺便把第一章的后面POJ的TO THE MAX给A了,挺有意思的一道题。
    • 巩固第一章的各种姿势。
    • 看一套模拟题,需要熟悉到自己能够做出每一道题。
  4. 最后需要给自己一点提醒。我自己虽然是做题型的,但是全部看了题解之后再做还是不好的,而且随时要注意以前的知识的巩固,不然考试会死的很惨。理解知识的速度需要加快,有问题就问什么的,不能因为面子就保留下来自己的问题,和Qizy学长说的一样,那样会很耽误时间。