日记

xiaolilsq

2020-03-05 21:59:46

Personal

以后这篇博客会和考试总结同时更新。

有一些特殊的感受会写在这篇博客里面,考试总结在另一篇博客里写。

2020.4.19

下午讲题,感觉还好。

晚上继续改题目。

2020.4.15

做数论题目。。。。。

晚上和其他人一起打了场cf的镜像赛,结果全是贪心和构造。。。

\color{white}\text{cf的比赛在打之前好像也不能知道题目质量?(雾}

2020.4.14

考试的三道题改出来了两道,T1理解了,T2还是没有弄懂为什么,T3题解看不懂,然后在网上好像也没有找到类似的题目?

看了下计算几何,感觉还好。

亚瑟王那题换了一下dp的状态,貌似一直过不了;最后不得已看了题解发现我这种设dp的状态貌似走不通?换了题解设的状态然后就推出式子了。

然后考试的T1和T2都被卡精度了,改了蛮久。

2020.4.13

常规\~\~\~。

晚上做了道树剖的题,又做了做[HNOI2015]亚瑟王,没写出来。

2020.4.12

学会了DLX,然后随便在网上找了题做。

2020.4.9

今天试了试莫比乌斯反演的题目,感觉还可以接受,然后学习了杜教筛,但是好像被卡了没过,但是杜教筛我是理解了。

2020.4.8

看了莫比乌斯反演并完成了两道习题,代码还是出现了犯低级错误的情况,打算明天调整一下状态,如果有时间再看看杜教筛。

2020.4.7

今天学习了扩展卢卡斯,看了看莫比乌斯反演,代码又莫名打错?又调了一段时间,感觉还好。

2020.4.6

今天学习了bsgs算法,感觉还好,就是hash莫名有点打错,结果调了一段时间。明天?扩展卢卡斯+莫比乌斯反演。

\color{white}\text{我居然把FFT看成了TTF?危}

2020.4.5

考试

这次的考试总体还是不算满意吧,所有题目都只是打了暴力。

三道题目,一道dp,两道组合数学,果然我数学还是没学好。

考试过程也没啥好说的,想数学想不出来就是想不出来,推式子之前也没做过这类的题目。至于dp?没想出来自我感觉还是不应该。

学到了什么?推组合式子算是学到了,dp的一种新思路?

2020.4.4

写了考试总结,看了看之前没写的数论题目。

2020.4.2

今天就是看了看FFT,然后写了个小结。

2020.4.1

今天主要是看了老师的直播课,数学有点没听懂,打算明天看看博客,再写点板子吧。(今天搞常规的时间有点多)

2020.3.31

今天主要是把组合数的题目全部写完,回顾了之前组合数的题目,了解了斯特林数,差不多就没了。

2020.3.30

今天写了一道题目:大胖的超级数字(毒瘤出题人不给模数,结果改了好久)。。。

晚上上课发现自己没学过数学。感觉数学好多都不知道,什么生成函数都不知道,明天再在网上看看吧。

2020.3.29

考试总结

2020.3.28

考试总结

2020.3.27

今天可能找回了一点状态吧,反正感觉做题目还好,但还是不太顺手,省选题目还没刷,明天希望可以考好点吧。

2020.3.26

今天继续刷题,省选题目还是没写,感觉常规有点写不完了,可能是今天比较急促的缘故吧,学起来有点力不从心了,总感觉学不进什么东西。

2020.3.25

今天还是在做老师给的数论题目,感觉有些知识点有点生疏了,然后历年省选题目还没写,数论方面还是要加强啊,做题没做出多少。

2020.3.24

今天主要是看了看下发的资料,突然发现readme里面说不用全看。。。然后就是写老师给的题目,发现自己之前学的没有学好,打算明天看一下不清楚的知识,然后看了看历年湖南省选题目,感觉压力有点大啊。。。

2020.3.23

今天主要是写了篇网络流总结,对之前的知识进行了回顾。总结地址。

PS:没写题目就不发做题记录了。

2020.3.22

今天的考试成绩仍然不理想,T1没见过果断打过暴力就放弃,T2斜率优化去重写挂,T3方案如何构造想不出来,结果就凉凉。

分析原因,T1平面几何没见过直接放弃太不明智了,其实dp不难想,T2总觉得是斜率优化的锅,结果是去重的锅,T3则思考还不够深,没有根据数据范围推算算法。

然后今天就是改题,还用了一点时间看了下二次剩余,感觉数论好难啊~

2020.3.21

今天主要是考试和改题,T1最终还是没有改出来,今天考的分数还是不理想吧,T2看错了题目,明天还是继续努力吧。

今天还和liuzhenxi讨论了下题目,基本就没做其它的了。

2020.3.20

今天(算是?)写了两道题目,把dij版的MCMF看了一遍,看懂了,但是还是没有看懂zkw费用流,把之前没A的两道题A了,感觉还算不错吧,希望明天可以考好点。

常规仍是按部就班。

2020.3.19

今天写了两道互测赛里的题目,第一题因为一点细节爆了int,调了一会,第二题T了一个点,感觉建图没问题,可能是spfa或者是网络流写法的问题?然后玄学了一下spfa,还是没过,打算明天还是看看dij的写法和zkw网络流吧。

常规还是按部就班。

2020.3.18

不知道为啥,越来越不想写互测赛里的题目了,于是今天便在洛谷上搜了搜网络流的题目,口糊了几道题,想了一下它们的建图方法,但是没有写,所以看起来今天没有写题,但还是动了脑筋,明天还是把互测赛里的题目写写吧。

常规还是按部就班。

PS:互测赛里的题目没有放进做题记录,所以我就没有提交。

2020.3.17

今天竞赛主要是继续刷网络流互测赛里面的题目,感觉题目都是看得出来的原题,怎么说呢,貌似写起来没有挑战性?(除了zzt的题目,虽然是原题,但我没做过),不管那么多了,先写完再说吧,今天写的题还算多了(都是复习之前的建图套路)。

常规总是按部就班。

2020.3.16

今天主要是做了做网络流互测赛的题目。。。

好多都是做过的,所以直接Ctrl+C Ctrl+V了。

自己想出了洛谷P4003无限之环(即本次考试B题)的建图方法,感觉还算不错吧。

今天整体良好。

2020.3.11

今天算是回到了之前的学习状态,学到了许多新东西。

首先是看懂了志愿者招募的题解,让我对最长k可重区间集问题的理解更加深刻,还有就是总算是找到了有上下界限制的最大(小)流的问题并解决了,对之前只是看看的知识有了实践。

总体来说,今天还算不错。

2020.3.10

今天主要是看了看网络流推荐题单中的一个内容,并完成了里面的一些题目(但还是比较少)。

感觉自己这些天都是在刷做过的题目,似乎没有什么提升,之前没有弄懂的也暂时是放在那里,没有再去看,打算明天还是要突破一下自己,尽力去弄懂自己看不懂的东西,毕竟看懂看不懂的才叫提升,否则是不会有进步的。

网络流博大精深,建图的方式只熟悉套路肯定是不够的,要多思考,指不定考试的一道题目就是从未有过的建图方式,虽说几年后可能题目又会变成经典题,但还是有许多新奇的建图方式等着我们去探索。

{\color{white} \texttt{Keep trying,never stop.}}

2020.3.9

放假一天?学习一天常规。

2020.3.8

今天主要是出了一道题目。

原本以为今天就是最后一天,结果发现又延长了好几天,正好我有一些地方还没搞懂,所以打算后几天继续做网络流费用流相关的题目,既然打算今天出题,于是便今天把题目出好了。

明天放假,打算搞一天常规,后天接着搞,还需要练习的:一类将点拆分成取值范围个点的网络流模型,有上下界的网络费用流模型,还有其它模型等。

突然想起马上就要分科了,可能自己选什么科目还是没有想好吧,可是我除了选物理化学生物还能选什么呢,常规任务是越来越重,都推迟那么久了,还是没有开学,为什么总觉得自己天天都在颓废呢?

## 2020.3.7 今天上午的考试考得并不好,一道题也不会做,打的都是暴力。。。 晚上主要是做题,还是之前网络流的题目,但是并没有做很多题目,因为题目还没有出好,明天是最后一天,还是没有思路,所以晚上在想该出什么样的题目。 出题难,出好题更难,我打算明天大部分时间用来出题,不要给自己太大压力。 网络流的学习就要结束了,总体我还是比较满意的,就是有些看不懂的恐怕只能等到以后再看了。 *** ~~我裂开了。~~ 我肯定不适合考$\text{NOI}$。 > 预估分数:$0+0+0=0

实际分数:0+0+0=0

我s了

2020.3.6

今天写的题目比较少。

今天原本打算继续把之前的题目补一补,补了蛮久题目,卡在一道题上了,看题解感觉有点迷,便先去看了一波有上下界的网络流,但是题解还是看不懂,便一直停在那里了。最后还是选择了放弃,去看后面的资料,结果也没看懂,感觉整个人都很烦躁,什么也没有学进去,一天就过去了。

今天状态确实不太好,出题也没有想好怎么出,整个人都很烦,明天尽量调整一下吧。

网络流真的要多思考。

以上为假的日记。

明天就是\text{NOI Online}测试了,祝自己好运(最好不要赖床)。

这几天真的有点迷,感觉自己天天在颓,没有一心一意铺在学习上,常规越抓越紧,也感觉是一团糟,之前看了好几篇退役记,自己马上也要退役了?(为啥我会有这样的想法?)

感觉强基计划出来后自己搞\text{OI}一直都很悬,自己常规几乎整个学期都在退步,貌似退役才是我当前最好的选择?(高考真善美,退役保平安。),可是我明明才搞了一个学期啊,我还是想搞\text{OI}的啊!!!

算了,可能是我自己给我自己这么大的压力吧,看一步走一步吧。(可这真的有用吗?)

2020.3.5

今天继续巩固了之前看的网络流相关的知识。

今天的刷题量是达到的(毕竟今天就是专门用来刷题的),把\text{3.}网络流建模中的题目写了一下,但是还是感觉写的题目好少,那份\text{ppt}中讲东西太多了,打算明天也用来消化。

还是那句话:网络流最重要的是建图,建好图后都是裸题,多练,多总结,多思考。

2020.3.4

今天写的题目还是很少。。。

原本打算一天看完\text{3.}网络流建模\text{.ppt}的,结果发现内容太多了,里面介绍的建模方式太多了(感觉这\text{ppt}写得太好了),然后一天大部分时间都在看\text{ppt},没有用很多时间刷题。

今天学到了蛮多知识,还算可以接受吧,网络流就是一个及其神奇的东西,算法貌似没有考很多,一般题目\text{Dinic}就行了,主要考的是思维(建图能力),既要多练,也要多做总结。

明天打算看完\text{3}吧,然后把\text{3}中的一些有代表性的题目写一下。

2020.3.3

做题做得好慢啊。。。

今天主要是学习了老师下发的资料\text{1-2},收获还算挺大的,感觉里面的一些东西不看自己是真的想不出来,看完后又惊叹于建图的精妙,自己应该也要在里面有所思考吧。

总的来说,一天没有刷多少题,但还是算总结出了一点东西,就是一类类似\text{2-SAT}问题的网络流模型的建模方式,还是希望明天可以多做点题吧。

2020.3.2

今天主要是学习(复习)了网络流和费用流的基本算法,并做了相关习题。

因为网络流相关问题最难的就是建图,所以今天我并没有看很多资料便去刷题了,感觉一开始还好,一些简单的题目想出来如何建图后感觉蛮有成就感,但是后来一些问题让我卡了好久,就是想不出来,让我有点沮丧,最后并没有写多少题目。

明天多看点资料吧,毕竟跟着资料走应该不会很难。

2020.2.29

本次图论学习到这里就告一段落了(就一天),这次学习的总结如下:

一、学习内容

在这次学习中,我复习了最短路、最小生成树、欧拉路径、拓 扑排序算法,学习了最小乘积生成树、次小生成树等一系列生成树算法,最小树形图,\text{A*}\text{K}短路,差分约束;还复习了\text{tarjan}求强联通分量,学习了\text{tarjan}求割点、桥、双连通分量,以及圆方树,\text{2-SAT}问题;学习了二分图匹配的匈牙利算法,带权二分图匹配的\text{KM}算法以及一般图匹配的带花树,\text{01}分数规划。

二、学习小结

本次图论学习学到了大量的新知识,这些知识需要刷题以及 思考来巩固,刷题量上我算是达到了,但是有一些问题,就是刷题质量还不算高,存在刷水题的情况,下次要着重提高刷题的质量;另外,刷题的过程中也会出现问题,比如细节的问题,这些都是要注意的。

在自学的过程中,他人博客以及老师提供的资料我大部分可以看懂,算法的原理基本可以搞清楚,其中的证明大致可以看懂,结论大部分可以记住(以后要多背背结论),就是有些的算法时间复杂度没有给出严谨证明。

三、备忘录(暂时没有看懂或感觉需要复习的知识)

## 2020.2.28 今天主要是做考试题。 今天的考试题不算很难,前面几题都是基础题,后面添加的几道题也还算简单。今天考试的内容涉及到了之前的东西,不止图论,还有$\text{LCA}$以及并查集,也是结合了之前的东西的一场考试吧。 后面看了下老师提供的$\text{pdf}$,里面讲的也可以接受,如果思考一会儿也是可以想出正解的。 今天总体状态不错,明天保持。 ## 2020.2.27 今天的考试题,不算太难。 先看$\text{T1}$,$\text{01}$分数规划?可惜我没仔细看,估计刚不出来,跳$\text{T2}$,一看,状压显然?然后就打了个状压,提交不上去,感觉没问题,然后直接跳$\text{T3}$,感觉可以枚举最小值二分找最大值,然后打了个类似暴力的程序,仍交不上,看$\text{T4}$,想了半天没思路,$\text{T3}$可以交了,一交,$\text{WA+TLE}$一片,不过大部分都$\text{A}$了,后来发现不用二分,直接尺取还快些,再交,$\text{TLE}$一个点(心想这数据也太水了吧),卡了下常数,然后就$\text{A}$了?跳$\text{T2}$,交上去$\text{RE}$一片,一脸懵,查了半天发现数组开错了($\text{dp[maxs<<1][maxs]->dp[1<<maxs][maxs]}$),改了就$\text{A}$了,看排行榜上大部分人都切了$\text{T1}$,选择放弃$\text{T4}$刚$\text{T1}$,$\text{01}$分数规划真想不出,便打了个$\text{tarjan}$求强联通判无解,然后$\text{15}$分光荣收场。 总体来说这次考试还是反映了许多问题,比如数组开错,还有之前就该看到的知识点没看都是问题,第一个问题是细节问题,需要每次考试时都集中注意力,毕竟要尽量避免调试,一次就打对比调试花的时间要少得多;第二个问题是学习方法上的问题,为什么之前总觉得自己收获少,就是因为时间用去刷水题而不是学新知识上了,刷题巩固必然重要,但额外的刷题只会导致效率的低下,省选马上要到了,已经没有多余的时间了! 望明天得到一个满意的成绩。 ## 2020.2.26 怎么感觉今天还是在刷水题? 感觉关于二分图匹配的题目大部分都差不多,自己找的题貌似都是板子题。。。 今天主要是复习了匈牙利算法,$\text{KM}$算法以及带花树,并刷了相关题目。竞赛差不多就是这些了。 关于常规,今天就是看了语文老师和英语老师发的视频,并完成了语文的一些课后作业。 ## 2020.2.25 今天主要是巩固之前的内容,加深了对带花树的理解,又刷了(带权)二分图匹配的一些题,其实收获还算蛮大,因为这些题中有许多细节要注意。 这两天主要刷的还是模板题,明天要刷点带思维难度的题目,来增加自己的分析问题以及建图的能力。 ## 2020.2.24 今天学习了匈牙利算法(增广路算法)、$\text{KM}$算法、带花树,并掌握了和二分图最大匹配相关的一些东西(最小点覆盖、最大独立集、最小边覆盖、$\text{DAG}$的最少路径覆盖等)。其中带花树有点没看懂,思路理解了,但是具体实现还是没有想明白,对着题解打了一遍代码,明天还要再看几遍。考虑到$\text{HK}$算法的本质是$\text{Dinic}$,决定学网络流的时候在看一下。 今天做题还算可以,数量上达到了要求。 今天总体状态良好,明天继续保持。 $\text{PS}$:$\text{U}$盘坏掉了,之前的程序和东西都丢了,望谅解。 ## 2020.2.23 $\text{U}$盘炸了,没心情写。 ## 2020.2.22 今天把$\text{tarjan}$算法全部看完了,有些没有记住,明天再补补。 今天主要是学习(复习)了无向图割顶、桥、点双连通分量、边双连通分量、有向图强连通分量以及完成了相关习题。 自我感觉图的连通性算法实践有很多要注意的细节,要多加练习。今天题目完成情况良好,状态不错,明天继续保持。 ## 2020.2.20 今天总体来说还是不太满意。 今天做题时又栽在简单的地方了,做最小树状图时在找环的地方纠结了好久,结果浪费?了大量时间,最后还是没有完成老师布置的任务。 今天学习了最小树形图、次小生成树,并进入了生成树/最短路计数,做了相关的一些习题(感觉做的都是板子,但是又很难),图论对我来说学习起来还是有点困难。 全天状态还算是正常,就是有时调程序有点烦躁。 ## 2020.2.19 今天学习效率还行,看了老师给的资料,复习了最短路和最小生成树、拓扑排序,以及复习(学习?)了欧拉图相关性质,先已进入任务要求$\text{2}$的学习,自学了差分约束、$\text{k}$短路$\text{A*}$算法、最小瓶颈生成树。 今天做的题目较少,有些细节让我调了蛮久,$\text{20}$题感觉完不成?尽量吧。 图论方面感觉之前学的还是太少了,要勤奋一点才行。 ## 2020.2.18 今天果真是试水赛。。。 先开$\text{T1}$,求割点?打了下,结果没过,自闭了。跳$\text{T2}$,基环树?于是迅速水了过去。$\text{T3}$?二进制分组?结果$\text{90pts}$,莫名$\text{WA}$(后面发现有种情况没考虑)。$\text{T4}$,最短路板子?(最短路径生成树),水了。$\text{T5}$,考过,数据范围小,直接枚举,水了。$\text{T1}$感觉没戏,刚$\text{T3}$,就是$\text{90}$分,最后收场。 这次考试,还是不尽人意吧,后来知道T1怎么写,感觉自己考场上没写出来真是遗憾,感觉考试时心态也不咋的,下次加油吧。 ## 2020.2.17 然而,今天的考试并不良心? 上来看$\text{T1}$,以为是用左偏树,没有仔细分析空间复杂度,结果让我调了一整个考试,获得了倒数第三的好成绩。。。 该怎么说呢,反正考试的时候还是不服输的,别人都切了$\text{T1}$,自己却没切,让我很着急,加上之前没考过左偏树,让我直接判断,还是有蛮大失误的,下次要仔细分析题目数据范围,不要先入为主。 ## 2020.2.16 今天的考试,然而,还是很良心?(貌似我已经说了好多遍了。) 先看$\text{T1}$,点分治的模板,$\text{T2}$也是,$\text{T3}$也是,$\text{T4}$网络太卡,打不开,先做了下$\text{T1}$,$\text{T2}$和$\text{T3}$,没有交,但是应该十拿九稳了,看$\text{T4}$,贪心思路显然?$\text{splay}$调了一下,然后就切了。交题,除了$\text{T2}$其它一遍过,再看$\text{T2}$,$\text{70pts}$,发现没判无解,$\text{80pts}$,发现路径至少包含两个点,$\text{90pts}$,发现手贱,一个点打错了,$\text{100pts}$,似乎细节出了点问题,但是还是过了。 今天状态没有昨天好,有细节没注意到,下次一定要注意。 PS:好像难度要加大?不知道还可不可做(黑题?灰题?) ## 2020.2.15 今天考的,然而,还是很良心。。。 $\text{T1}$之前的原题,$\text{30min}$切了,$\text{T2}$动态开点线段树的板子,因为之前没打过,打了比较久,$\text{1h}$切了,$\text{T3}$一开始看没思路,有点晕,在仔细看了下题,感觉就是用最长上升子序列的求法,于是打了个暴力,$\text{60}$分到手,后来仔细分析,发现这个暴力很简单就可以转为$\text{LCA}$,于是改了一下,然后就一遍切了?然后就$\text{AK}$了? 总的来说,这次考试没有出锅,大都能一遍过,体现了我的代码实现能力还算可以的,然后想到的都能实现,状态还算不错。(貌似明天就有点困难了。。。) ## 2020.2.14 今天的题目仍然很良心。。。 $\text{T1}$,一看上去不知道如何写,看数据范围,颜色数小于等于$\text{30}$,果断状压,线段树半小时切了(又是模板题?),跳$\text{T2}$,只要链修改最后查询,这不裸的树上差分吗?半小时切了(又是模板题?),看$\text{T3}$,一开始没思路,脑子里一直想着莫队,但由于没想到容斥,所以莫队复杂度还是太高,后面突然想到可以转化成求包含某区间的区间个数,然后打算用$\text{cdq}$分治求二维偏序,结果问题还没仔细考虑清楚就下手,加上$\text{cdq}$我又不熟,所以打得挺慢的,后来停下来想清楚了,半小时打完了,一提交,全$\text{WA}$加$\text{TLE}$,让我有点慌,以为是算法错了,但是总发现不了问题,后来找到了些小问题,改完后提交还是错。突然想起可以对拍,于是对拍了许久,发现了错误的一组数据,此时离考试结束还有$\text{5min}$,没时间留给我了,于是交了个暴力就放弃了。考完后找了一会,便发现排序时有个小问题,改完就切了(太可恶了,原本可以$\text{AK}$的(如果忽略数据错误))。 总结考试失败原因,大概有三个,第一个是$\text{cdq}$不熟,以后要及时复习之前学的知识点;第二个是没考虑清楚就下笔,这是老毛病,一定要改;第三个是不习惯对拍,这次比赛可以看到评测记录,但是比赛中不可以,所以一定要对拍,一定要对拍,一定要对拍!!!对拍可以发现并及时改正许多错误,下次考试坚决要对拍。 //最后再说一句,为啥大部分还是板子题啊? ## 2020.2.12 今天考试还是很基础吧。。。 $\text{T1}$数据结构题先跳,看$\text{T2}$,博弈论,再跳,$\text{T3}$,线段树板子,半小时切了,过来看$\text{T1}$,发现$\text{T1}$倍增,树剖,$\text{LCT}$均可做,调试也不难,一个半小时切了,跳$\text{T2}$,分析有点难?想了一下,大概有个思路,求必胜必败的状态转移还算简单,结果没有考虑到一些地方,导致思维有点混乱,我也有点烦,结果推出来是错的,只有$\text{30pts}$。 今天的题目主要是没有仔细考虑清楚答案的求解,导致白白丢了分。 ## 2020.2.11 今天的考试还算好吧。。。 考试一开始,我首先看了$\text{T1}$,结果题目看错,$\text{+i}$没有看到,以为是道$\text{hash}$找规律的题目,写了半个小时,才发现题目看错了,然后想了想,没思路便放弃了,跳$\text{T2}$,我好像想过这类型的题,可以用笛卡尔树做,于是打了半小时切了,$\text{T3}$,原题,半小时用并查集切了,$\text{T4}$,没思路,跳,$\text{T5}$,还是没思路,便先把$\text{T1}$暴力写了(后来才知道模拟就是正解,结果$\text{hash}$没$\text{hash}$好,便$\text{T}$了),看$\text{T4}$,以为要求矩形边必须平行与$\text{xy}$轴,便打了,结果发现样例都过不了,跳$\text{T5}$,还是没思路,然后就又用$\text{map}$打了$\text{T4}$的暴力(后来竟然可以过),$\text{T5}$还是没思路,打了暴力边去检查了。 考完感觉没考什么恶心的数据结构题?今天试题还算容易吧。 ## 2020.2.10 今天看了下点分治,点分树没有看懂,打算开学后在问同学问懂,今天主要是写了篇总结,并对以前学的数据结构进行了回忆。[总结链接](https://www.luogu.com.cn/blog/LSQ147/shuo-ju-jie-gou-zong-jie) ## 2020.2.9 今天主要复习了$\text{LCT}$和树剖,学习了点分治。 由于时间问题,点分治只打了板子,树剖也没有仔细看,只有$\text{LCT}$花了很长时间写题,主要是我感觉所有东西都包含很多知识,几天时间根本搞不透,结果想搞透$\text{LCT}$,所以花了大量时间。至于点分治,以后再补吧。 今天状态还算可以,代码上没出很大的锅(主要是因为之前打$\text{Splay}$打的?),明天继续加油。 ## 2020.2.8 今天主要是学习了树链剖分和$\text{LCT}$,树链剖分仅仅是打了模板,$\text{LCT}$则深究了一点,看了下别人的博客并刷了些题。 树剖感觉和$\text{LCT}$的联系也是很大的,感觉$\text{LCT}$就像是动态的树剖,并且支持更多的操作,$\text{LCT}$中的$\text{Splay}$操作又和之前的知识联系起来,然后有$\text{Splay}$就又有了线段树。 今天状态还算不错,学到了蛮多新东西,主要是在看别人的博客,所以没刷多少题,一天学两个新东西着实有点困难,也不容易都学透,以后注意避免这种情况。 明天再打下树剖,$\text{LCT}$和点分。 ## 2020.2.7 今天主要复习了平衡树(主要是伸展树$\text{Splay}$)的拓展,并做了有关习题。 $\text{Splay}$和线段树的结合使得$\text{Splay}$可以出出很多有关序列操作的题目,这类题目较相似,但较难调试,这就需要一些经验来避免一些错误,所以这方面的题要注重实战。今天写了6道题目,状态还算比较好。 打算明天学$\text{LCT}$和树剖,后天学点分治。 ## 2020.2.6 今天学习了$\text{RMQ}$和$\text{LCA}$的一些算法和技巧,新学的知识有$\text{Tarjan}$离线求$\text{LCA}$以及笛卡尔树,$\text{RMQ}$转$\text{LCA}$,复习了$\text{LCA}$的倍增求法和转$\text{LCA}$求法,并做了一些关于RMQ的题目。 $\text{RMQ}$和$\text{LCA}$问题在我前几天刷题时就有碰到,自我感觉这类问题的可变性还是很强,可以和许多东西结合,需要比较强的问题分析能力。 我后来看了一下文件夹外的《高级数据结构》和《数据结构》,似乎讲了一些其他的数据结构,感觉收获也蛮大的。 今天一天状态都挺不错的,明天要保持。 ## 2020.2.5 今天主要是刷了关于线段树的一些题目,收获还是比较多的,主要是在做题经验方面和题目套路上面,既考验了代码实现能力,也有思考能力,唯一的遗憾就是写的题有点少。 ## 2020.2.4 今天学习了树状数组以及线段树的一些操作。 今天主要看了一下线段树,感觉之前了解得太少了,今天学习了懒标记的特殊下传以及标记永久化等关于标记方面的特殊操作,一些看似暴力实则可过的方法,学习了线段树的另外的写法(非递归等),还有线段树维护的信息的选取,以及和其它数据结构的联系。 自我感觉线段树的变式还蛮多的,有的题看上去真不那么能想到用线段树做,确实蛮难的(或者是我刷题不够???)。 不管怎么说,今天还是学了蛮多东西的,感觉今天状态不太好?明天必须调整一下。 打算明天再看一下树状数组和线段树,后天再学$\text{RMQ}$和$\text{LCA}$这种和倍增有关的东西,树状数组和线段树应该差不多吧。 ## 2020.2.3 今天主要学习(复习)了$\text{Trie}$以及$\text{AC}$自动机的相关内容,主要是做题,通过一天的刷题我对$\text{AC}$自动机掌握得更加熟练了,学会了如何利用$\text{AC}$自动机其中$\text{fail}$数组的树形结构,学会了如何在$\text{AC}$自动机中$\text{dp}$和其中的套路(如矩阵快速幂),同时也了解了$\text{AC}$自动机的拓展等(自动机)。 今天学习效率算高,总体还算不错(自己$\text{A}$了道黑题)。 ## 2020.2.2 今天主要学习了(复习)$\text{hash}$与$\text{kmp}$,掌握了拓展$\text{KMP}$算法和$\text{manacher}$算法,做了一部分习题,整体状态还算不错,没有在细节上出很大毛病。 ## 2020.2.1 今天主要学习了并查集的相关操作以及与其相关的复杂题目的思考方式,还有掌握了二叉堆、左偏树,了解了二项堆,斐波那契堆等可并堆,并做了与其相关的练习题,有一点就是没来得及做的是相关可并堆的习题以及可反悔的贪心的习题,时间主要浪费在对细节的一些调试上,下一次要着重抓细节,防止出现代码的一些低级失误。 总体来说,第一天还算是不错的。