「OI笔记」2021.8.16
Day7 上午 P4074 糖果公园 树上带修莫队,在一期夏令营的时候没有解决,而是直接淦SP10707,就是因为糖果公园这道题带修,而那时刚刚学莫队,不太熟练。今天上午就再次学习树上莫队,然后搞掉这道题。 树上莫队的核心就是将一棵树通过欧拉序变成一条链,从而转…
316 2021-08-16 0 康一康「OI笔记」2021.8.14
Day6 上午 T1一开始题意理解错了,以为被替换成Backspace的字母不会被删,也就是说一次只会删一个字母。后来才发现样例中有一个点本来是NO我输出YES,所以发现了问题。 之后发现规律:如果两个字符串长度的奇偶性不同,就必须先删掉首位,因为首位是一定要被删掉…
523 2021-08-14 1 康一康【OI笔记】2021.8.13
Day5 上午 前一个小时在激烈地讨论跳舞和getID的事情,就当划水吧。大约九点半的时候才开始干事。首先又去回顾了一下树上莫队,搞了下欧拉序。 我现在觉得好像自己的复习计划有些混乱,这里一下那里一下,貌似不太好,应该要调整一下。 上午也没做什么题,就这…
464 2021-08-13 1 康一康【OI笔记】2021.8.12
Day4 上午 今天自习,看看某神仙的言论: (好叭我不是神仙我先GUN了) 上午一直在啃昨天的T1,本来想用dsu on tree的,看到using大V已经实现,就试了试,结果还是败在了昨天的那个地方。所以还是采取了题解的思路:平衡树。。 平衡树这里有几个坑,一是不能…
333 2021-08-12 0 康一康【OI笔记】2021.8.11
Day3 上午 我的MA啊,为什么题目都这么难????首先看T1,看到ans[i]这个东西的时候脑子里边第一时间蹦出dsu on tree,然后就开始尝试。 但是,在最关键的步骤,也就是子树要传什么东西给父亲的时候,我被细节给绕晕了。在徘徊了45分钟之后,毅然决然跳T2。 …
319 2021-08-11 0 康一康【OI笔记】2021.8.9
Day1 上午 今天上午讲了 SA 计数排序 基数排序 总体来讲可还是听懂了,就像HYF所说的 板子会打了,但是不会用。 个人认为SA比SAM要好理解的多(毕竟带上“M“的都不是什么好理解的东西),就好比树状数组和线段树的关系(可能吧),SAM我至…
355 2021-08-09 0 康一康【OI笔记】7.26复习
前言 没得。。。 正文 ST表 适用于维护可区间合并的值,如 max(a,b,c)=max(max(a,b),max(b,c)) 具体操作:用f[i][j]表示从i开始往后2的j次方。 初始化: log[i]=log[i/2]+1; f[i][0]=s[i]; 具体操作:见程序 P3865 【模板】ST 表 https://www.luogu.com.…
334 2021-07-26 0 康一康【OI笔记】Splay
前言 Splay其实并不是一种数据结构,而是给另一种数据结构进行优化的方式。 预备 Splay是建立在二叉查找树(BST)的基础上的,所以要学会Splay,就必须先了解二叉查找树。二叉查找树的形态是一颗形如这样的二叉树: 具体查找操作看OI-Wiki,大致操作就是和当…
394 2021-07-15 0 康一康