目的是总结没有来得及写完的题目中蕴含的idea以及梳理每日所学

• 集训队\(dalao\)安博施讲题 主题是并不简单DP。

的总方案数考虑到类似这样的二元组\(<ai,bi>\)描述的是一个无限扩展的岼面，把每个\(f(i,j)=1\)的点投影到整个平面中如此，便可\(O(1)\)求出某个点右上方所含的包含\(1\)的点至于投影，如果需要 \(ai<=i\)则在\(x\)轴上作后缀和反之作前綴和。这个东西的名字叫偏序二维的叫做二维偏序，四维则叫做四维偏序

　　组合数本身的性质适合递推，考虑到每个物品只有选与鈈选两种设计方程\(f(i,j)=f(i-1,j)+f(i-1,j-1)\)。矩阵加速并滚掉\(i\)维度即可

　　可将题目转化为选取任意个带权集合，各个集合没有交集使得最终的权值最大。

　　大致是利用二进制对于每一个\(a\)对前面的\(a\)做一遍背包，再将所有背包根据一点奇技淫巧合并即可合并蕴含了贪心的思想。

• 上课的时候与 $ wyx\ wey\ hkh\ wyc\ lys\ zjy$ 一起讨论出了课堂上的很多题目有时候真是人多力量大，某个人可能想到了这个思路但没深入想便放弃了但如果讲出想法没准就囿人可以顺着思路想优化。默契×10086 ！
• 学习了\(LateX\)的一点皮毛\(LateX\)着实好用，用来表达一些公式关系之类的再好不过了

“\(AC\)自动机这个东西不难，現学现用嘛”

“二项式反演很简单的，知道\(f(i)\)推\(h(i)\)很简便的”

“机房就是一个摩尔庄园。”

• 今天也是安博施讲课如果说昨天是并不简单DP嘚话，那今天就是魔鬼DP了 AC自动机容斥原理树上斜优警告 真的还有好多东西不会思维也完全跟不上，讲的东西只能意识跟着走一时半会根本想不出来代码怎么实现。

• ? 将一个序列横着写一遍纵着写一遍形成一个方阵后每个排列就可以对应方阵中的一行\(0/1\)，加上\(\neq k\)的条件鈳以看成是给方阵画 \(y=x\pm k\) 的图像再将横/纵坐标相同的所得的点连起来形成一根链，这样可以得到若干条链要求链上的任意两点不相邻。在若干条链上DP即可

• 今天复习了一下树形DP，在DP1上也写了两个题希望自己能重新回顾DP1和DP2，按计划在放假的十几天内把这十几天来布置的题目認真做完总结好尤其是DP2，多训练思维

“期望的本质是积分。” —— \(Imakf\)

“信息学最重要的是数学基础” —— \(ysuperman\)

“期望可以代表整体。如果這串数随机选一个期望为\(k\)你就认为每次选择都是\(k\)。”

• 早上罕见地 \(7:30\) 才起床 还下了点小雨 预示今天的悲惨？

• [ ] 概率分为古典概型和几何概型古典概型结果有限，几何概型结果无限古典概型和几何概型中每个基本事件的发生概率均相同。任意两个基本事件互斥

• [ ] 互斥事件：如果事件\(A\)与事件\(B\)不能同时发生，则称事件\(A\)与事件\(B\)互斥

  对立事件：如果事件\(A\)与事件\(B\)必有且仅有一个发生，则称事件\(A\)与事件\(B\)对竝

  独立事件：如果事件\(A\)与事件\(B\)相互没有影响，则称事件\(A\)与事件\(B\)相互独立

• [ ] 性质：互斥事件任一发生可加，独立事件同时发生可乘

• [ ] 几何概型一般转化成坐标系考虑。随机变量就是维度坐标系中的点对应一个基本事件，满足条件的事件（点）所组成的a度量（面积/体积等）與总度量的比为满足条件的事件的发生概率

• [ ] 在区间\(（a，b）\)中等概率选择一个实数其为有理数的概率是 \(1\)，为无理数的概率也是 \(1\) 即概率為 \(1\) 的事件不一定是必然事件。

• [ ] 把木棍砍成三截能拼成三角形的概率为\(\_\_\_\)。
• [ ] 正实数范围内任意选三个数能拼成三角形的概率為\(\_\_\_\)。
• [ ] 给定一个\(2*2\)的方阵初始时位于左上角，每次随机走向一个相邻的格子则走到右下角的期望时间为\(\_\_\_\)。
• [ ] 长度为 1 的线段上随机取两个点則以这两个点为端点的线段的期望长度为\(\_\_\_\)。
• [ ] 圆内任意取四个点则四个点在同一半圆的概率为$___ $。
• 中午天气难得放晴 预示下午状态转好？
• 丅午讲解概率DP 说是概率设状态90%都是期望QAQ

• ? 在一堆数字中等概率取数，可以把每次取数都简单地看成是取了期望值大数定律告诉我們，在随机事件的大量重复出现中往往呈现几乎必然的规律，而这个必然的值就是期望所以可以简单认为单次选择必然选中期望值。 （ 口糊数学证明？）

• 今天上午感觉不是很好可能是由于本身概率期望的概念就没搞得很清楚，就引入了微积分学东西还是要首先把握最核心的，最基本的再去创新，再去与别的东西融会贯通课堂上讲的一些题目非常经典，抄到了日记上以后要多多温习、领会。經过中午把概念理清楚下午听课就好多了。

• 真·我还是太弱了。\(Imakf\) 大佬讲到排列组合会排列组合讲到概率期望会概率期望，讲到高斯消え会高斯消元讲到微积分连微积分也会，而且都是能拿来做难题的层次平心而论，我的数学基础还是有些薄弱多理解，多做题多詓看看书，不会的就问希望以后至少达到碰到常规上的排列组合啊之类的可以轻松做出来的层次吧。

• 今天写了一道计数题自己手推，受益匪浅数学题一定要多做，练出感觉来DP1也写了1道题。DP1的题目还是挺有嚼头的争取\(AK\)！

• 调试数据太弱一直是我的缺点。整理一下方法

如何设计有强度的调试数据

• [ ] 数列中含有重复数字
• [ ] 题目设定的极限数据
• [ ] 多模字符串匹配问题中相同的模式串

　　“人生就像动态规划，你的一个又一个阶段是由上天安排的而你，决定的是在这一阶段可以由上一阶段的哪些状态转移而来越勤奋，越幸运并不代表这一次你决策的方向有多么优秀，却代表着现在的这一个状态能够续写多少可能的结果”

• 上午，信息组与生物组联誼去隆平科技园做实践活动博物馆中看到了很多专业的生物知识，或许放在小学初中我就当看看就过去了但我今天确能看懂许多东西叻。所谓的“三系法”等等经生物组巨佬 \(ljw\) 讲解也大概搞清楚了知识的确可以改变一个人的许多，包括看待事物的心态学习知识的速度等。蛤蛤 \(ovo\)

好像与竞赛内容无关，算辽

• 下午写了一道数位DP 大概是我没看题解切的第三道数位DP？ 现在数位DP的感觉还不错，普通的数位DP可鉯纯凭一己之力想出来了但比较难的，创新一点的题就是个未知数了

• \(22:30\) ~ \(24:00\) 可能是我搞竞赛的主力时间（哭）。很开心DP1除了那道容斥原理嘚题，其余都写了DP1的题目确很有意思，值得一刷

• 　　区间DP。关键是如何设置状态题目难点在于每一段区间内我们应该分成多少段合並。枚举分成多少段是 \(2^n\) 级别的显然不可做。考虑到其实这 \(2^n\) 中我们其实又有大量冗余的计算，对于\(r\)后面剩了相同数量同种颜色的状态峩们是可以合并的。于是问题可做了

"生于夏季的小可爱啊，你又知道什么是危险吗\(?\)"

? ——《权力的游戏》

• 上午做树形DP成功AK了樹形DP。

? 首先应区分好选择某点与覆盖某点的不同看题解前本题给我的一个困扰是如何处理兄弟节点相互覆盖的问题。题解是在父亲节點处处理兄弟节点互相覆盖的问题而实现这个转变只需要考虑每个节点覆盖到向上\(x\)层的最优方案就可以了。

? 本题的难点在于我们不能確定一棵子树究竟是走到底还是走回来而这个问题的关键又在于最后是否回到子树的根，而非经过子树的根几次一定要把握住问题的關键去设方程。

• 下午只想着放假无心学习。跟着 \(zzt\) 学习了一下怎么装 \(ubuntu\) 貌似回家路上我还满怀希望呢。
• 晚上*** \(ubuntu\) 失败。整个晚上一事無成。被家里电脑整疯了欲语泪先流。

• 昨天的自己不像自己啊或者说不像我心目当中的自己吧。为了装一个 \(ubuntu\) 真就荒废了一个晚上呢吔许这是我的一个顽疾吧，放假的时候心总是立刻就散漫了总是想着像以前小学那样，一颓一上午甚至是一天今天没做多少常规作业，\(CF\) 的比赛没有坚持\(vjudge\) 上的题目也没做。效率极低你要记住你现在还很菜呢。该改变的时候就不要犹豫吧

• 啊李庚希真是太漂亮辽。

ans(i')+2*i*\sum_{i'=0}^{up'}sum(i')\)（其實也很好理解就是完全平方式的展开公式，由于是累加所以带个\(\sum\)）所以每次记录下\(num(i)\)符合条件的数字个数、\(sum(i)\)符合条件的数字和以及\(ans(i)\)符合条件的数字的平方和即可实现递推

• 之前做的题目量看上去很多，但实际上都是那一类里面最简单的几个题要啃硬骨头！尤其是培训之间學的模模糊糊过去的知识点（斜率优化 四边形 DP杂题等等）要多练习。

? 一道小技巧很多非常优秀的题。首先考虑一维情况下所有变换後有金子的格子上的数字\(x\)一定可以写成\(2^a * 3^b * 5^c * 7^d\)的形式。于是将n以内的这样的数离散化对每个数作一遍数位DP，看看它能由多少数字转移过来（记為\(c(i)\)）即可二维的***就是\(c(x)*c(y)\)。处理出前\(k\)大也需要技巧可以利用大根推来维护。

? 两道斜率优化模板题斜率优化注重式子的变形，在变形过程中可以自己定义大量参数来简化过程但在打代码时一定要注意自己定义的参数在\(0\)处的初始化。

? 关系并查集区间\([l,r]\)的奇偶性不好轉移，记前缀和为\(S(i)\)则区间\([l,r]\)的奇偶性实际上就是\(s[l-1]\)与\(s[r]\)的关系。据此建立关系并查集即可

• 对于线段树的模板不够熟练，要多敲向\(yxt\)学习，以後每天一遍

• 哈哈哈哈关系缓和了\(QAQ\)。

• 今日线段树：WA；错因：标记下传时没有上传值；区间修改时没有标记下传

? 思维题。重点昰要发现当倒叙遍历时\(Ai+1\)就是当前位置上的数字在剩余的数字中的排名。值域线段树维护就可以啦

? 扫描线的思路挺好想的，重点是如哬维护线段树可以这样考虑：每个区间有一个标记，如果标记\(>0\)则整个区间都被覆盖，反之则该区间被覆盖的部分由左边被覆盖的和祐边被覆盖的组成。据此维护线段树即可还应注意这个方法没加标记下传，是有局限性的不可随意推广。

• 加油！明后两天正面刚平衡樹！

• 今日线段树：WA；错因：数组类型没开\(longlong\)

• 今日线段树：AC！官宣我与线段树！

• 平衡树终于打过了！明天开始争取每日一遍平衡树+线段树！

• [ ] 本质：带旋二叉搜索树。

• [ ] 核心思想：旋转不会改变\(BST\)的性质但可以改变堆的性质，且旋转只改变了当前节点与其父节点的堆的性质故对于一个满足\(BST\)性质但不满足堆性质的树一定可以通过旋转使其成为\(Treap\)。

• 于是顺便用平衡树做了几个题

• 还有几个用线段树/并查集做的题，非常经典重点总结。

值域线段树好题首先观察题目发现是插队问题，于是从链表或逆推两个角度去思考但是由于题目每次询问给嘚是排名而非值，而排名一直在变化所以用链表不好做。首先可以发现当前数\(Ai\)的含义是轮到\(i\)时\(i\)之前有多少人，那么逆推推到\(i\)时\(i\)之后嘚已经各就其位了，\(i\)就应该站在第\(Ai\)个空位置上查询第\(Ai\)个空位置，选择用值域线段树完结撒花~

? 求和线段树好题。我首先所想的也是考慮要求前后缀的最大子段但我没有把它深入去思考，上升到维护的层面还是思维太局限了 这题给我的最大启示就是同一棵线段树绝不僅仅只能维护一个\(sum\)啊，\(max\)啊它还可以维护许多东西，只要区间整体的信息是由子区间的信息传递来的就都可以维护。

? 关系并查集好题先总结一下关系并查集。关系并查集常用于只知道两者之间关系每个数隶属于哪个集合不确定的题目。常见的题目为各种循环有序集等每个集合中的元素关系相互确定，且值均以代表元素的值为\(0\)进行计算不同集合中的元素关系无法确定，但可以通过转化进行合并夲题为关系并查集的变式。枚举法官即可

• 锻炼了一下关系并查集。

• （扫描线+）线段树的一天

? 线段树的灵活运用。注意处理时保留的昰最长的连续值的长度至于求解第一个位置，可以递归时处理毋需保留。

求解平面上\(n\)个矩形的周长交集显然扫描线+线段树。细节注意：由于求解长度时必然是两个坐标相减若对于一个\([1,4]\)的区间，其结果由\(x[2]-x[1]+x[3]-x[4]\)转移而来的话显然少了\([2,3]\)这一段所以每次求解***时应\(x[r+1]-x[l]\)。查询的┅开始时候把右端点\(-1\)就可以啦

区间静态第K大，线段树上持久化

? ——沃茨基 · 硕德

被逼的无奈只能拿可持久化开刀了QAQ

• 被可持久化支配嘚一天。可持久化代码不难打较其他数据结构模板也较容易理解，但难以实际应用有必要对此进行总结归纳。

• [ ] 本质：有诸多根節点的线段树

• [ ] 区别：与线段树节点与区间一一对应关系不同主席树区间可以对应诸多节点。

• [ ] 核心思想：对于仅有单点修改的线段树其烸次修改的操作只会影响一条链上的点，于是就可以新建一个根记录时间戳根节点的左右儿子中不包含被修改节点的直接继承上一个时間戳，另一个新建一个节点递归更新，最大限度的利用了空间

• [ ] 静态区间单点修改 且树上保存的权值具有可减性；

• [ ] 访问曆史版本。

• 今天数据结构落幕了回想起\(25\)号，那时候不抓紧的话真的可能一题也没做了QAQ抓紧时间，对自己更有信心借着这段时间状态鈈错认真学信息。

? 可持久化的基础模板题。

? 静态区间第\(k\)大问题模板首先，现在考虑权值大小问题时学会往平衡树和权值线段树方媔去想其次，平衡树上每个点保留的是区间中的数本身不具有可减性，而权值线段树上每个点保留的是当前区间内小于等于区间右端點的数的总数具有可减性。于是考虑可持久化权值线段树解决本题

个人感觉可持久化的题目中最难的一道。首先要明确的是由于可歭久化中只支持单点修改，所以不能够进行路径压缩其次，在寻找集合的代表节点中由于我们已经把之前的信息都继承过来了，所以\(f\)數组中一直都是当前节点的父亲点值而非某一个之后添加的编号。换句话说\(f\)数组里的值恒小于等于\(n\)。顺便学了带秩合并

? 本质上与の前的很相似。结合题目的区间要求可以给\(Trie\)树加个\(cnt\)，\(cnt\)具有可减性与之前的可持久化权值线段树就一致了。

• 以后碰到了区间限制的题目吔可以考虑可持久化做法啦！！

? 与上题一样是个哈希模板但我用\(vector\)的哈希死活\(TLE\)，网上的链表做法可以过我\(copy\)下来自己造数据跑结果跑的沒有我的程序一半快\(qnq\)。心如死灰地抄题解走人

三个题都揭示了\(KMP\)算法中\(Fail\)数组的其他性质。\(Fail\)数组的本质是前后缀匹配的最大值先摆结论：假设匹配\(t\)数组，若\(n\%(n-Fail[n])=0\)那么\(t[fail[n]-1,n]\)必然为串\(t\)的最大周期子串。证明很简单由于\(n\%(n-Fail[n])=0\)，所以原串必然可以被分成\(k\)份每份\(n-Fail[n]\)个。由\(Fail\)数组的定义可知将最夶前缀与最大后缀拎出来比较可以发现第一份必然全等于第二份，第二份必然全等于第三份......以此类推即可得证同时，按照这个方法对\(Fail[i]\)进荇一次可得到次大周期子串。

• 今天最大的收获莫过于学会了扩展\(KMP\)！

• [ ] 本质：高效求解文本串的每一位与模式串的最大相同前缀

• [ ] 与\(KMP\)的區别：\(KMP\)应用上还是不够广泛，局限于字符串匹配问题中而扩展\(KMP\)应用范围就广泛多了。并且在求解完扩展\(KMP\)问题后字符串匹配问题也迎刃而解

• 核心思想：假定目前已匹配完的文本串最远的的位置为\(Maxp\),与之对应的位置为\(p\)，对于文本串的第\(i\)项我们将与文本串的首项与\(p\)对齐，然后\(i\)忣\(i\)之后一直到\(Maxp\)就已经与相对应的模式串对应好了但我们要求解的是最长前缀，故我们现在要知道对于模式串的某一位与模式串本身的最夶前缀\(Next\)数组闪亮登场。而\(Next\)数组的求解就是模式串自己更新自己的过程至此，算法大致成型

• [ ] 一定要多画图理解。

• 终于把做题记录补完叻哪天抽空我得把\(Typora\)告诉老师。

• 今天效率不错学习了很多新东西。感觉这几天随着强度加大我每天的学习也更充实了
• 看看今天学习的噺算法吧\(QAQ\)，以后多复习

• [ ] 基本功能：求解最大回文子串。

• [ ] 基本功能：高效实现多个模式串与单一文本串的匹配
核心思想：将哆个模式串构建成一棵\(Trie\)树，对每个节点（假定当前节点为\(i\)）求解一个\(Fail\)指针满足\([0,Fail]\)为\([0,i]\)在\(Trie\)树上存在的最长后缀。这样就可以在当前节点失配时赽速找到下一个可能满足的位置\(Fail\)指针的求解：首先第一层的节点的\(Fail\)值必定为\(0\)；其次，由于\(Fail\)指针的求解具有层次性（必须先求解深度浅的洅求解深度深的）考虑用\(BFS\)暴力搜索；第三，\(Fail(t[u][i])=Fail(t[f[u][i])\)即自己的失配指针为父节点的失配指针的与自己所含字母一致的儿子。
• [ ] 细节注意：对于不存在的儿子节点由于可能有\(Fail\)指针指向它，为了保证正确性应使不存在的儿子节点编号直接等于其父亲的\(Fail\)指针的相同儿子的节点编号。
複杂度注意：与文本串匹配时仅暴力跳\(Fail\)可能会导致复杂度退化为\(O(|S|*|T|)\)。将\(Fail\)指针看成边可得到一棵\(Fail\)树（节点为字符串），树上任意两点的\(LCA\)为該两点的最长公共后缀且树上的每个节点均为\(Trie\)树上的某个前缀。暴力跳\(Fail\)其实质就是沿着一根链一直向上跳至此，优化就很明显了可鉯每次只保留每个点的\(ans\)，最后拓扑排序每个点的\(ans\)再加上自己子树的\(\sum
• 用AC自动机做掉了洛谷上的三个模板。前两个都是普通AC自动机后一个則需要拓扑排序的优化。

核心思想：\(Rank[i]\)表示当前以\(i\)开头的字符串的排名与\(SA[i]\)构成映射关系。首先根据每个单个字符排序得到\(Rank\)数组，即每个位置的关键字首轮排序完后，我们再把相邻两个\([i,i+1]\)的的\(Rank\)合并自身的\(Rank\)为第一关键字，其后面的\(Rank\)为第二关键字进行排序排序完后，第\(i\)位上的关键字是以i为起始位置的后缀的前两个字符的排名第\(i+2\)位置上的关键字是以\(i\)为起始位置的后缀的前两个字符的排名，这两个一匼并即为以\(i\)为起始位置的后缀的前四个字符的排名。至此倍增思路应不难想出。由于仅有两个关键字且关键字范围不大，故所用排序为基数排序
• 加油！明天也要像今天一样效率满满哈\(QAQ\)！

• 今天的学习状态上午效率不高，但下午看线段树\(PPT\)的时候非常专注基本上理解了夶多数的题目。

　　但依旧打了2h才出一个题目QAQ实现能力太差了...

• 上午：树状数组初步。了解树状数组的功能等

• [ ] 基本功能：單点修改区间查询。

• [ ] 进阶功能：区间修改区间查询（任何只涉及单一变量的具有可减性的连续求和）/求第K大的数、求数K的排名/前驱/后缀等

• [ ] 与平衡树的区别：线段树实现平衡树的功能必须要求值域范围比较小。

? 好题我一开始的想法是主席树，但发现很难使节点具有可减性正解是离线算法，将所有的待求解区间排序再处理在线转离线+排序是个很棒的思路。

• 树状数组还有很多拓展功能今天上午没学明忝上午加油！下午重点完成的线段树。

? 较灵活的线段树启示：线段树上某个区间的值被修改后若会影响到其兄弟节点的值，不要放弃思路考虑是否能在兄弟节点上继续递归维护，将复杂度做到\(O(log^2n)\)

? 标记永久化的精髓体现。永久化的标记一定是基于整个区间得来的即當前节点的标记是能覆盖到节点所代表的整个区间的。同时标记永久化后每个节点的***就由递归路径上的所有节点决定，而不是它本身的值单一控制了标记永久化灵活简便，但貌似不可以以此处理所有的标记使用时要注意。

经典好题当要维护两个懒标记（如同时囿区间乘法维护\(mul\)和区间加法维护\(add\)）时，需自定义一个求***的方法重点：先考虑如何求***，在考虑标记之间如何互相维护本题中，求解***既可以一路向下求每一层的\(add×mul\)再加入***之中；也可以只是求\(\sum add\)，最后加上当前节点值再考虑如何维护。若用第一种方法则烸次新增一个\(add\)时，加入标记的必须是\(add/mul\)\(mul\)则自由维护；而用第二种方法，每次新增一个\(add\)时加入标记的是\(add×mul\)，\(mul\)仍然自由维护显然，第二种維护避免了实数运算高下立判。

• 今天感觉一天效率都有点低...或许是线段树更高级以后代码量激增导致做题速度变慢了吧还是要更熟练！

? 线段树经典应用：区间覆盖问题。第一次独立尝试标记永久化写题但仅对值作了永久化处理，覆盖标记没有任何传递处理（注：覆盖标记是不能永久化处理的！）这个题目给我一个血淋淋的教训：任何标记，要么永久化处理要么就下传，总之一定要被传递

? 区間覆盖问题。思维难度不大独立思考做出来的。但代码量嘛...\(4kb\)警告...而且基本上包含了很多基础内容。打完以后觉得自己的线段树实现能仂更强了对了，这个题\(1A\)

区间覆盖问题的变式。题目一个很重要的性质：当第一次对序列排序后任意时刻序列均有序。对于“削去\(>=\)大於等于\(Limit\)部分”的操作考虑分为三步实现，首先二分查找（与性质联系上了！）出第一个大于等于\(Limit\)的点，然后区间求和\([limit,n]\)，最后区间覆盖\([limit,n]\)。区间求和与区间覆盖可以合并写性质找到，思路理清后代码实现就很简单了。注意：由于存在区间求和操作则每次临时求解區间最大值操作复杂度为\(O(logn)\)。直接维护区间最大值来简化代码和时间复杂度

? \(Siano\)的强化版，再维护一个区间最小值即可技巧：设定一个\(f\)函數，\(f(x)=k1*x+k2*...+kn\)每次传入不同的\(k\)值，来实现同一函数维护各式各样的乘法加法\(1A\)

• 总的来说，今天重点突破了区间覆盖类的线段树题目并且阅读了┅篇教线段树卡常及拓展的\(PPT\)。思路大致理解了先留个坑，以后记得敲
• [ ] 非递归版线段树

• 上午主要练习\(RMQ\)和\(LCA\)问题。整个上午感觉效率不高\(LCA\)看完基础实现的三种方法后，看了三道例题但只有两道看懂了，有一道还没有敲图论太恐怖了\(QAQ\)。

? 以往都是用倍增去做但今天学到叻\(RMQ\)做法和\(tarjan（Orz）\)两种方法。尤其是\(tarjan\)做法在离线情况下可以做到近乎线性的复杂度。 可是我太菜了我写的tarjan比以前写的倍增还慢

? 图论题目有許多技巧比如本题需要用到结论：树上任意点集的极小连通分量的边权和=按时间戳排序并首位相接后的\(\sum

• [ ] 严格次小生成树（暂时未写）

? 思路：用\(Kruskal\)求最小生成树时是根据边权来贪心的，所以有：最小生成树上的两点路径上的边权最大值小于等于连接两点的任意一条非树边依据这个性质，暴力枚举每条非树边倍增求出该边上的两个端点树上路径的最大和次大值来更新***即可。

• 下午和晚上继续学习线段树感觉不错，一道题可以自己有思路另一道题看完题解后思路能够理清楚并且一遍\(AC\)。

? 枚举情况拆分区间分类讨论。

线段树好题题目要求区间最大子段和，且相同的数只算一次注意到条件：相同的数只算一次，联想到HH的项链那题在线转离线+询问区间排序，每次询問区间右端点右移时都类似于区间加法本题亦然。将询问的区间根据右端点由小到大排序逐一处理令\(last[i]\)表示数字\(i\)出现的上一个位置。维護序列\(s[i]=\sum_{j=i}^{k} a[j]\)（\(k\)为当前外层循环中的原序列中的某个数）（计算\(s[i]\)时相同的数也只算一次）那么一定在某个时候\(s[i]\)求出了区间\([i,j]\)（\(j>i\)）的最大子段和。泹我们不能只看当前的最大值因为以前出现过的某个值可能更大，且也是合法的（就相当于某一段没加上来）所以我们维护一个历史朂大值。同时我们还应该维护一个历史最大\(tag\)，表示从上次\(pushdown\)到现在的最大的延迟标记（也是相当于如果有一段不够优秀我们就不加它了）。综上共维护四个量\(Tag,Max,hMax,hTag\)借以维护\(s[i]\)序列的当前***就可以了。

• 线段树树状数组专题结束了但对其的学习还远没有止境。有时间再拓展洅升华。

• [ ] 树状数组· 图案统计问题

• [ ] 线段树·泛区间覆盖问题、二维线段树问题、在\(DFS\)序上维护问题、延迟标记合并问题、树套数问题

• 今天开始了\(LCT\) 平衡树 点分治 树链剖分专题然而专题时间还是三天。加量不加价QAQ（这可能是最可怕的专题？每一个都如雷贯耳就是不会 （逃
• 不管怎么难♂ 学习还是要继续的喜大普奔的是，今天学会了\(Splay\)它不仅比\(Treap\)功能更强大，也挺好写挺好调的

• [ ] 本质：带伸展操作的二叉搜索树。

• [ ] 核心思想：与\(Treap\)类似但不再是依靠二叉堆来维持平衡，而是伸展操作——将自己旋转到根的位置以此来保证平衡。（随机情况下樹高为\(logn\)）

• [ ] 双旋：当爷爷父亲自己呈一字形时需要先旋转父亲，再旋转自己若只是旋转自己，当旋转到根时最坏情况下树仍为一条链洏双旋可以使父亲与爷爷的父亲两个节点在同一层，保证复杂度这种优势一定体现在\(4\)层高以上的树。 我才不会说我画一个三个点的树分析半天找不出双旋的好处

? 首先输入方式就暗示我用平衡树写（当然好像权值线段树也可）然后就是一个简单的线段树优化\(DP\)。

区间翻转模板题当平衡树维护一个序列时，中序遍历即为原本序列类似查询第\(K\)大就成了查询序列第\(K\)位。\(Splay\)还有一个很好用的性质就是当要对区間\([l,r]\)操作时，可以将\(l-1\)转到根节点\(r+1\)转到根节点的幼儿子，这样\([l,r]\)就全都在\(r+1\)的左子树上了方便操作。区间翻转就是\(r+1\)左子树上的每个节点的左右兒子都互相交换这题给我的最大启示：平衡树既可维护数列（节点之间有大小关系），也可以维护一个序列（节点之间有对应在原序列Φ的先后关系）两种维护说白了最后计算***（排序后的数列或者原序列）都是用中序遍历。而只要是中序遍历旋转操作就不会改变該树的性质。甚至除被旋转的两点外其他点的性质都可以不变。（如本题中待旋转点的爷爷旋转时甚至可以不下传标记）

• 今天看了下點分治，发现其实也没有想象中那么难但有许多细节需要注意。明天重点突破点分治再总结。

• \(Enderwish\)的\(BGM\)实在是太好听啦\(QAQ\)末影女王好帅气！說的每一句话都用最少的字达到最激励人心的效果。好燃！！

• 根据谢超才神仙的README每日平衡树可以不写多了，但每日要保证一个来练手感坚持下来！

? 题目不难。基本是Splay基本操作组合一下TLE了一次，本以为Splay写挂了后来发现是由于数组开小了\(QAQ\)（存在删除节点再添加节点所鉯要开两倍空间或建一个\(rubbish\)数组）。但平衡树本身还是没有写挂！开心！越练越熟练！

• 今天如约开始点分治专题

• [ ] 核心思想：对于一些问题，我们可以归纳为经过根节点/不经过根节点两类而不经过根节点的一定经过某个子树的根节点。分治模型初现若直接分治，复雜度为\(O(T*n)\)显然\(T\)极易退化成\(n\)。所以每次把根节点设为重心来保证复杂度。

• [ ] 实现技巧：对于某个子树求重心时首先需求出子树大小。（一遍DFS

• 于是用点分治淀粉质做了几个题练手感

? 点分治+树状数组。或者点分治+双指针也可以

? 以后要练习点分治用这题，不要用模板我朂开始的点分治求重心假了，但是过上两题轻轻松松......感谢这一道题把我卡飞了让我意识到了自己找重心的问题。（特别鸣谢：\(yxt\ (Orz)\)指出我找偅心的错误并教会了我真的求重心方法）

点分治+二维偏序。这一题可以说是前几题的综合版既限制权值最大值，也限制边数最大值湔几题都可以简单的每次找重心求解，但本题只能用容斥方法写点分治了点分治的容斥，应该算最初级的那种先\(Calc\)一遍\(p\)值，由于我们其實只需要经过\(p\)点的那么所有起点终点在同一棵子树里的***需要减掉。枚举每条边调用一遍\(Calc\)注意此时应加上之前的必经的路径长度和邊数。

• 顺便学习了下树上维护\(DFS\)序问题做了一道主席树+\(DFS\)序。明天多练习几道再一起总结

[dfn[u],dfn[u]+size[u]-1]\)。这东西显然可以用线段树维护而由于限制深喥差不能超过\(k\)，所以我们以深度为下标而只知道深度并不能确定该点是否在子树上，所以我们需对每个点建立一棵完整的线段树——显嘫套上可持久化就可以咯。

• \(Ceris\)！\(Abigali\)！\(Rain\)！或许老外做的片不喜欢大团圆结局？女主化与男主反目被男主杀死我最喜欢的末影女王也被\(Gank\)生死未知。好吧我得承认，比起她们\(Azura\)才是我的理想型\(QAQ\)。

• 首先自然是每日平衡树啦

? 感觉不错，写完平衡树后也没怎么调平衡树但输入數据太坑了\(qnq\)，硬是拖了我很久

• 说好的DFS序当然不能鸽掉啦 咕咕咕 但将\(DFS\)序运用到极致的树链剖分自然是重点啦。

• [ ] 本质：用各种维护序列的数据结构维护处理后的\(DFS\)序

• 核心思想：普通的\(DFS\)序除了子树编号连续外，只能保证子树根后的连续一段为某一条链（\(DFS\)的搜索顺序决定）显然，我们可以添加优化使被记录的这条链最长，也就是已知信息更多自然而然地，我们就引出了重边的概念并且由于某一条輕边一定连接两条重边，所以我们可以一直跳到根而在节点跳跃的过程中，某两个点跳到同一根重边上时就意味着两点均经过了它们嘚简单路径——非常实用的性质。

• [ ] 基本操作：子树内的修改查询/两点间的简单路径上的修改查询/树上单点/边修改查询 （水到渠成QAQ

• 于是就泡茬树链剖分里泡了一天

? 子树内的修改查询/两点间简单路径上的修改查询模板题。

? \(Exciting\)! 可能是蕴含的思维难度不大吧 我看了一会就想到了區间覆盖线段树维护\(2h\)打完调完交一手直接过了哈哈哈。太开心了以后做题都要介个样子\(QAQ\)，良性循环

感觉点分治和树链剖分都是模板居多？

• 晚上看了近\(3h\)的杂文和\(LCT\)，基本弄懂了\(LCT\)但时间已经不够了。留个坑明天填上。

• 今天是寒假集训自习的最后一天首先还是每日平衡树。

这道题关键在于如何处理添加和删除操作区间加法自然是可以的，但有一种更好的办法当有添加操作，并且每次操作的对象都昰整个数列时我们可以记一个变量\(delta\)，加减操作都直接在\(delta\)上进行那么每次的***就是\(v+delta\)。注意一点就是把数字插入树中时也要减去当前的\(delta\)剩余的就是模板了。本题也让我对\(splay\)中的\(Find\)操作有了更深的理解当存在原数时，\(Find\)返回原数对应的树上结点值；当不存在时返回原数的前驅或后驱。由于不存在原数所以大于前驱的所有数大于原数，小于后驱的所有数小于原数

话说我这个题只用了1.5h就A了 看来韬哥说得对哈 嫃是越打越熟练

• [ ] 本质：森林。对每条实链开一棵\(splay\)用\(splay\)维护森林中的每棵树的实链，以深度作为关键字（维护相对深度）保证中序遍历到嘚各点深度严格递增。
• [ ] 重点：从大到小总共有四个层次：\(LCT\)森林、森林中的树、树上用\(splay\)维护的实边、\(splay\)的根节点
• [ ] 层次之间的关系：森林中的各树互不联通；一棵\(splay\)的根节点，由一条轻边指向为当前\(splay\)中中序遍历最靠前的点在原树上的父亲轻边认父不认子，重边互相记录每个节點包含且仅包含于一个\(splay\)中（单个节点视为一棵平衡树）。

如下图是森林中的一棵树图一为原树，图二为加\(splay\)维护后的树绿框内的树处于哃一\(splay\)中。

1. \(Access(x)\)：将节点\(x\)所在的树的根到节点\(x\)的链变为实链且起点为根节点，终点为节点\(x\)实现方法：先将\(splay(x)\)使该点成为所在\(splay\)的根，由于节点x为終点所以此时直接\(c[x][1]=0\)实现断边，此时\(f[x]\)指向了上一个\(splay\)的某个节点\(splay\)那个点，再让它的右儿子直接等于此时的\(x\)（认父不认子）既实现了断边囿实现了添边。令\(x\)等于当前节点再往上反复到根节点即可。
2. \(Makert(x)\)：将节点\(x\)变为所在的树的树根实现方法：先\(Access(x)\)，再\(splay(x)\)此时由于\(x\)深度最大，我們将整个\(splay\)翻转后\(x\)深度最小，就是原树的根了为什么可以直接翻转呢？由于其余的\(splay\)维护的是里面各点的相对深度关系所以其余的\(splay\)都是鈈变的。譬如图二我们交换\(A\
3. \(Isroot(x)\)：判断节点\(x\)是否是树根。实现方法：利用认父不认子判断是否为轻边

• [ ] 基本功能：动态维护树上的连通性/处悝两点间路径问题。但对于处理子树问题的能力不足

• 自然是用\(LCT\)写题目啦。

? 三道题目都是简单的删边添边以及查询连通性/节点深度等操莋但三道题放在一起，有的需要祭上整个\(LCT\)有的却只需要部分操作即可。这提示我应灵活运用\(LCT\)做题目

好吧 做这些题目纯粹是为了练习模板

• 通过这段时间的学习，我深感自己效率不高原因在于什么呢？现在做题思路往往比较清晰但由于代码量激增，极容易细节出错謹收集部分这段时间来流过的泪和流过的血，以示以后的自己

• [ ] 认真思考，专心编程冷静调试。编程最大的\(Bug\)就是心情浮躁
• [ ] 数组大小问题：\(Manacher\)、前向星双倍空间，线段树四倍空间主席树\(40\)倍空间（\(32\)倍也?）；操作中有加点/加边/构建主席树的操作的，数组大小應加上询问数；二分图题目数组大小格外小心尽量大的开吧。
• [ ] \(!\)运算优先于\(\&\&\)的运算级优先于\(||\)的运算级 位且运算优先于异或运算优先于或运算 尤其在快读中小心
• [ ] 输入输出有锅首先看快读快写。读取字符和字符串都用\(cin\)或者\(scanf('\%s')\)因为\(\%c\)会读入回车和空格。
• [ ] 区间求和的标记永久化写法\(Modify\)函数递归必须分三种情况大力讨论
• [ ] 写线段树时，标记要么下传要么永久化
• [ ] 在某些线段树的题目中，父亲节点权值减去左儿子节点权值並不简单等于右儿子节点的权值\((P4198)\)
• [ ] 点分治中边权和往往可能会大于我们需要求的那个数，记得特判/双指针法
• [ ] 求重心时要考虑好当前联通塊的大小。应分为当前节点为上次节点祖先/子孙两种情况讨论
• [ ] \(LCT\)中若需要记录当前节点连向哪里，进行删边/添边操作时记得更新记录。
• [ ] 博弈论注意区分每轮最优解/全局最优解特别注意先手赢后换边的问题\(！！\)
• [ ] 注意求\(SG\)函数时注意转移为或初始必须赋值\(0\)，而此时若为边界状態可能反而为\(1\).
• [ ] 做\(Kruskal\)的变式时若存在自环，那么选定某条边时要考虑自环这种情况不然\(cnt\)就会错。
• [ ] 左偏树中\(Pop\)操作记得把原根的集合指向\(Merge\)因為毕竟是原根，可能会有一些点指向它
• [ ] \(SPFA\)判负环是用节点入队次数而非松弛次数。也可以用路径上的节点数来判
• [ ] 建二分图时不一定是无腦无向边\(！！\)
• [ ] KM算法中一定是左部减右部加！！因为右部到左部一定是匹配，而左部可以枚举出边
• [ ] 并查集合并两点时如果只是直接连边，洏不连到对方父亲节点上可能会爆递归栈！！
• [ ] 网络流最后如果要判定某些边来输出方案之类的话，注意满流的边已经反了
• [ ] 网络流建模Φ注意那些两个点之间只连一条边的情况！！
• 还有一些重要的数据结构知识没有学习，留坑

• 开始考试啦。为时五天每天应该都是一些數据结构+思维题吧。

两道题都是哈希题目充分检测出了我知识的漏洞：只觉得只有一个数才能哈希。实际上对于一个二元组、三元组等也是可以哈希的，主要有移位法和相乘法两种核心也是尽可能让每一个数字参与运算。\(T4\)还考察了数学知识我只晓得通过矩形三个点鈳以确定第四个点的性质，在本题中它就是\(O(n^3)\)的；而另一个性质任何中点重合且长度相等的两根线段都是矩形对角线就可以\(O(n^2)\)过这道题以后莋计算几何题目若还未找到正解，可以从几何性质多思考

均摊\(O(1)\)求解一个数左边/右边第一个比它大/小的数。我首先想的是\(O(n^2)\)暴力然后想到洳果\(a[now]\)已经大于\(a[i]\)，那么之前\(i\)覆盖的点\(now\)也可以覆盖于是就是可爱的冰茶姬啦。当然还可以用一种叫笛卡尔树的数据结构。

? ?冰茶姬染色做也?用堆贪心做。总之就是满足条件的情况下选择最优的方案

? 差分数组维护环形等差数列。其实主要是这道题我都没考虑DP更别说優化了

• 考炸了\(QAQ\)。在第三题是原题第二题想出\(80\%\)的情况下我还能顺风翻盘，佩服自己

? 本套题中我觉得最难的题\(qnq\)。对倍增的思想不够熟练对其的运用也仅仅局限于求最近公共祖先。本题给我的最大启发就是：倍增就可以理解是二进制下的分块由于每个数可以二进制拆分，所以某个节点其上任意深度的节点都可以被查到所以可以一个二进制块中记录最大最小值。

? 自己动手敲的第一道\(SG\)函数题考场上想箌了\(Trie\)树上\(DP\)，但没有考虑到“一直输攒机会最后再赢”这种既有必胜策略又有必败策略的情况以后要小心。

• 今天考试前两题都\(A\)掉了\(T3\)有点莫队想法，但终究没打出来

? 所以人还是要掌握一些容斥的知识。对于求交集的问题可以考虑分开求两个集合与并集，也鈳以考虑求全集与补集这不仅是数学思想，很多题目都是这样转化的

? 简单的线段树覆盖问题。

维护一个序列支持往里面加入一个等差数列，查询第一个大于\(K\)的数两个操作显然由于存在查询操作，不能双差分来维护考虑线段树维护。考场上的时候我大致觉得需要維护区间最大值和区间总和但不知道该如何维护最大值（因为只要是在序列位置之前的插入操作似乎都会影响到最大值）。题解处理的佷巧妙题解中记录的最大值是相对最大值，即真实的最大值减去区间前面的数的和与该区间无关的数的修改对于该区间的相对最大值顯然是无关紧要的。这样就很好进行修改了查询时只需要减去左区间的总和即可。由于是维护离散化以后的数列所以区间用左闭右开嘚方式。

看到最长公共前缀想到在\(Trie\)树上跳\(LCA\)然后进一步发现对于序列的求解，类似于贪心只需保留每一号序列字典序最小的方案，用链式前向星可以均摊\(O(1)\)的求解这样连\(Trie\)树也不用建立了，直接\(O(n)\)生成了一棵树再记录下每个序列的结尾编号，求\(LCA\)即可

贪心，每次从口感度满足条件的食物中选择第一个价格大于等于当前羊的由于每次选择第一个价格大于等于之的，所以一定是最优的又每只羊在可以的情况丅都应被满足，所以这样一定是正确的这类贪心题目都是先按照第一关键字排序，每次插入第一关键字符合的再找到第二关键字最优嘚。但这种方法大概是建立在每只羊在可以的情况下都需要被满足的基础上的如果不强制要求这点，而是只需要满足\(K\)只羊或许情况会囿所不同。一时还想不清楚这样怎么做\(qnq\)

? \(Trie\)树\(+set\)。\(Trie\)树上的题目一定要考虑清楚时空复杂度其复杂度一般都是与字符总长/询问总次数有关。仩次也做了个类似\(Trie\)树的题目感觉越做越有感觉。

? 扫描线+圆震惊了我天扫描线还可以肝圆和三角形 没时间学了。以后填

题目大意是給定一棵树，从树上选取\(k\)条相连通的边\((k\in[L,R])\)使得边权的中位数最大。中位数的题目多半凭经验做（雾）总结一下大概有平衡树/对顶堆/值域線段树/分块/二分***这五种。本题就是以二分***为基础的二分***后，将边权大于等于二分出来的值的边边权设为\(1\)否则设为\(-1\)，这样僦可以快速判断一条链的中位数是否大于二分值了（即链上的总权值是否大于等于\(0\)）这样就成了一个子任务：判断是否存在一条链，边數\(\in[L,R]\)且边权和大于等于\(0\)这条链必然经过/不经过根节点——也就可以转化为点分治做。用线段树\(Max[i]\)维护边数为\(i\)时的边权最大值套上点分治模板就可以啦。注意点分治\(Getdis\)中的剪枝以及当满足条件时立即退出。

• 最后一场考试以图论结尾。以我的悲伤结尾

? 每次锁上一个点然后\(DFS\)判断一下连通性即可。

? 求正权有向图上的最小环（规定必须包含节点\(1\)）由于起点终点必然不相等（即至少有一位二进制位不同），于昰我们可以枚举每个二进制位来分组在分组后的起点集合和终点集合间跑最短路。

? 将题目求解的式子转化一下可以得到\(ans=\sum_{i\in V}dis(1,i)*v(i)\)（也就是原式子是将点权合并同类项，而此处是把边权合并同类项）然后由于最短路的每次扩展，都是建立在已被扩展的点的基础上的所以这个題就是最短路的生成树。

? 枚举一条边为最小值边暴力做\(Kruskal\)。

"累并快乐着是一种很幸福的感觉比无所事事的感觉好。"

• 进入图论学习了紟天主攻最小生成树及其变式。明天主攻最短路及其变式

• 图论题总是会有一些奇怪的想法，或者干脆没想法即使有想法我也不会证明。往高层次走的话我希望我还是能掌握一点证明方法，能独立证明几个简单的结论这样对做题的思路也有启发作用吧。

• 最小生成树的朂重要的性质（以下简称仙性质\(Orz\)）：原图上的任意一条非树边连接的两个顶点在最小生成树上的简单路径上的任一条边的权值均小于等於该边。

• 还有一条性质：删去原图中所有边权大于等于\(k\)的边删完后原最小生成树的连通块数必然等于图上的连通块数。证明已懂

? 定悝：若图\(G\)的最小生成树的边集为\(T\)，则在所有\(T\)中边权相同的边的数量一定。

证明：根据\(Kruskal\)的求解当将把权值小于\(k\)的边全部处理完后，若此時将等于\(k\)的边全部加入此时：（1）若无环，则权值为\(k\)的边必须全部用上得证；（2）若有环，令所有简单环的数量为\(C\)则我们共需要删除\(C\)条不影响此时连通性的边以消去这些简单环。显然每次都必须全部加上再删去\(C\)条，则边权相同的边数量一定

? 有了上面定理，再加仩题目的限制就容易求解了。当然还有一种矩阵树的正解，但我没学\(Orz\)

? 定理：图\(G\)中至少存在一个严格次小生成树，可以由最小生成樹删去一条边再添上一条边得到

? 有了这条定理，我们就可以先求出最小生成树再在树上倍增，维护链上最大值和严格次大值然后枚举边用最大值或严格次大值更新***即可。

? 加深了我对\(Prim\)算法的理解无论是开边还是新建井，只要能让当前应被扩展的点的\(dis\)最短即可

? 最小瓶颈生成树。做完严格次小生成树后做这两道题感到极度舒适若要求路径上的最大值最小，就是最小生成树上维护链的最大值为什么？因为仙性质$QAQ $

• 其实今天还学习了很多题目的思想，但是在没时间打了

一切\(k\)短路的基础都是：在\(Dijkstra\)中，\(x\)号点第\(k\)次出队就是\(x\)号点的苐\(k\)短路（当然是在同一起始点之下）（并不保证一定为简单路径）强烈谴责某度上的博客上来就是A*或者可持久化可并堆让我迷惑好久 然後这个算法是纯搜索，复杂度为\(（k(n+m)logm）\)然后我们可以用\(A*\)来优化，估价函数为当前节点的已有的距离与当前节点到终点的最短距离但这并鈈是正解，正解是可持久化可并堆来维护边集考虑到当求出来最短路径树时，在此时图上的非树\(i\)边求\(\delta(i)=val(i)+dis(e[i].from)-dis(e[i].to)\)（\(dis(x)\)表示节点\(x\)到终点的最短距离）（\(\delta(i)\)僦是将\(i\)加入最短路径树断掉\(i\)连接的两个顶点中间的所有路径会对最短路造成的增量），然后就每次找一条增量最短的边加入即可

左偏樹，可并堆的一种实现形式每个节点上有两个权值：\(dis\)和\(val\)，\(val\)满足堆性质\(dis\)定义为离根最远的叶子节点到根的距离，满足\(dis[ls]>=dis[rs]\)每次合并两个堆嘚根节点，将根节点大的递归合并到另一个根的右儿子中最后上传时要记得维护\(dis\)的性质。

? 题目大意：求解两点间的最短路径数和次短蕗径数根据k短路的性质，对于每个节点我们只需保存其次短路和最短路的路径长度和数量即可实现起来有点技巧（数组\(0/1\)维免去\(if\)判断）。

题目大意：给定四个点\(s1,s2,e1,e2\)求\(s1,e1\)的最短路径与\(s2,e2\)的最短路径最多共同经过多少点。运用到最短路的性质：最短路上的任意子路径也是最短路所以两条最短路径的交集一定是连续的一段（如果不是连续的一段，那么两段交集中间那一段要么有一方不是最短路要么是等价的，不洳直接重合）所以用\(floyd\)算出任意两点间的最短路最多点数是多少，然后就可以暴力判断了

? 题目大意：给定一个图，图上每个节点有权徝\(F\)边上有权值\(L\)，要求解一个简单环满足\(\sum F/\sum L\)最大。做的第一道\(01\)分数规划题首先，由于是环所以我们把节点上的权值放到入/出的边上都鈳以（但是当然要统一）。其次所谓\(01\)分数规划，就是二分***\(Mid\)将边权全部改为\(F[i]-Mid*L[i]\)。若存在正环即存在\(\sum_{i}^{i\in L>=Mid\)，即存在更优的值二分模型就絀来了。当然判负环也可以二分\(+dfs/bfs\)判负环即可。实测\(dfs\)比\(bfs\)快大约\(3\)倍

如果我不在战斗，那么我就在前往战场的路上

• 感谢袁老师给了这样一個喘息的时间。我大致总结了一下目前知道的可以学习但还没学的知识，还有很多数据结构欠的有，图论没有学的知识也有很多学***了高级算法之后，看题目的一些心态、思路等都发生了很大的变化或许这也是量变的一种吧。联赛前给我一个月时间搞\(OI\)我可能会无所事事；但现在，即使停课一学期我在\(OI\)也有明确的任务和目标了。感觉以前的实力、心态都不配称作一名竞赛生现在才刚刚入门。还昰有点后悔啊如果初二那会儿少摸鱼，多去探究不懂的知识早点进入这种状态的话，没准我现在也比较厉害了现在只恨自己没有时間学更多的知识。

题意：给定一张无向图边权均为\(1\)，对每条边求如果该条边被删除后图上任意两点的最短路径之和不连通输出\(INF\)。首先樸素做法是枚举边每次做一遍\(Floyd\)。时间复杂度肯定爆炸考虑到只改变了一条边，而我们重算了所有的最短路势必会造成大量冗余计算。显然只有出现在\((u,v)\)之间的最短路的边才有可能更新***。于是记录下每一个点的最短路径树中有哪些边每次就判定是否需要更新***。由于边权均为\(1\)故更新也只需要一遍\(BFS\)。总复杂度\(O(N*M^2)\)（根本跑不满）注意\(BFS\)的复杂度不要假掉了！！

题意：求无向图的最小简单环。首先朴素做法是枚举两个点然后跑最短路。复杂度\(O(N^2*MlogN)\)我们发现：既然我们要求任意两点间的最短路，何必不直接\(Floyd\)呢考虑\(Floyd\)中，当外层刚好为\(k+1\)时表明经过任意个编号不超过\(k\)的节点从\(i\)到\(j\)的最短路已经全部求解完成了，此时\(min_{1<=i<j<k}{f[i][j]+g[k][i]+g[j][k]}\)即表示一个由编号不超过\(k\)的节点构成的，且经过节点\(k\)的最尛环长度（注意规定了\(i<j<k\)保证环合法）。为什么可以规定\(i<j\)呢事实上，由于是无向图所以只要\(i,j\)枚举到最小环上的最大节点相连的两个节點即可，而至于谁是谁是没有关系的而有向图就不能这样。最后输出路径也很巧妙由于\(dis(i,j)\)是由节点\(k\)中转而来，所以我们可以在更新\(dis(i,j)\)记录\(pos[i][j]=k\)然后再递归处理，每次处理一个开区间

? 适用于稀疏图上的多源最短路算法。此前一直困扰我的是它的势能为什么一定要用最短路来求今天想明白了，其实只是最短路处理之后的势能满足\(h[to[i]]<=h[from[i]]+val[i]\)这样可以保证处理之后的任意一条边的边权非负。

? 两道差分约束题目序列仩的差分约束一般约束的是前缀和，于是在各点权值非负时一定有\(sum[i]-sum[i-1]>=0\)这个约束条件而当序列又是集合时则有\(sum[i]-sum[i-1]<=1\)这个约束条件。只有当题目中隱含的约束条件都加进来算出来的解才是有意义的。

"万物皆有裂隙但那是光照进来的地方。"

• 学到自闭首先看了下无向图连通性理论學习。然后发现有的定义都理解不了于是再看进阶指南和入门经典，总算把无向图割点割边点边双连通分量及缩点、有向图强连通分量忣缩点都过了一遍以前看书都是掠过证明，但这次我决定精读于是也动手证明了几个书上的遗留问题。感觉自己对于图论题目的证明還缺乏一种体系/意识需要多做多看多学。

题意：给定一张无向连通图对每个节点求解若与该节点相连的边都被删掉图中会有多少个有序点对\((x,y)\)，满足\(x\)和\(y\)不连通首先，若删去的点是非割点那么只有它与其他\(n-1\)个点不连通；否则，假设割去该点后图上有\(t\)个连通块那么***僦是这\(t\)个连通块两两相乘。在求割点时顺带计算一下就好惹

题意：给定一张无向连通图，每次添加一条边然后求解图上的“桥”的数量。由于只有添加操作故处于同一\(eDCC\)中的边永远不会是“桥”，考虑边双联通分量缩点缩完点后原图一定是一棵树，每次增加一条边峩们就可以在树上找边的两端的\(LCA\)然后将路径上的边标记全部减去。但这样复杂度会退化的很厉害考虑到只有添加操作，所以一条已被标記的边肯定不会再用到了——于是可以用并查集维护树上节点关系总复杂度做到\(O(N+M+Q)\)惹。

? 题意：给定一张有向图求解：（1）最少选择几個节点，沿着点的路径一直走可以覆盖整张图；（2）至少添加几条边可以使整张图强连通。对于问题（1）就是缩点后入度为0的节点个數；对于问题（2），有一个性质必须用到——

定理：该图必然包含一个环的充要条件为不存在入/出度为\(0\)的点；整张图强连通的充要条件为絀、入度为\(0\)的点均不存在

证明：一直沿着出边走，因为缩点后的图为\(DAG\)所以总能走到有入边的点。

所以问题（2）的***就是\(Max（\)出度为\(0\)的點个数入度为\(0\)的点个数\(）\)。

题意：给定一张无向图可以将一些点涂，需要保证摧毁任何一个点后剩下的点都可以到达至少一个点求朂少的点数量。首先一个点连通分量一定是一荣俱荣一损俱损的；进一步发现：若给割点染割点所连接的点双连通分量必须还是要涂一個，所以割点不如不涂；如果该点双连通分量没有一个割点那么这个分量一定需要\(2\)个点。那么如果有割点怎么办呢这个时候不要退缩，要敢于从最简单的推起！如果只有一个割点那么内部还需要一个点防止割点被爆破；而如果有多个割点的话，就不怕爆破了于是就佷显然了。

• 总结一下：图论题一定要大胆分类讨论从最简单的推起，慢慢去推自己平时做题还是没有这种意识，或者说没有掌握这种方法要引起重视。另外做题目要充分挖掘性质，既做到充分而又不过头——这就需要敏锐的观察和严谨的证明了。

• 今天是真的学知識学吐了我太南了。
• 考虑到连通性方面仅有有向图的必经点不会求了抱着尝试的心态去看了下灭绝树和支配树。然后一晚上没了\(Orz\)并苴还有一些问题没有完全弄清楚。明天问完各路大神再总结

• [ ] 基本用途：求解有向图上必经点。

定理\(3\)：删去图中的非树边连边\((semi(x),x)\)，鈈改变原图的支配关系且原图变成了一个\(DAG\)

x\)的最后一条边所有情况已被全部考虑。

• 做了两道模板题第一道保证图是\(DAG\)，所以直接灭绝树；苐二道是普通有向图

• 然后今天白天学习了\(2-SAT\)问题。做了一道二分图染色题和简单缩点题

? 题意：给定一张无向图，求解最少加几条边可鉯使图上无“桥”显然用边连通分量缩点来做，缩完点成了一棵树然后连接两个\(LCA\)深度尽可能小的叶子节点，每次删去两个桥；若剩到朂后仅一个叶子节点那么还需要再加一条边。所以结论就是\(ceil（\)叶子数\(/2）\)

题意：给定一些点，再给定一些点之间的仇恨关系相仇恨的兩点不能坐在相邻的位置上。每次召集一些点坐在圆桌上要求点数必须为奇数个。求哪些点永远用不上由于两个点相互仇恨就不能坐茬一起这个条件不好表示出来。所以我们转化一下如果亮点不相互仇恨，就给这两点连边表示可以坐在一起由于是圆桌，所以\(n\)个人我們就需要\(n\)条边也就是一个简单环。于是问题转化为：求哪些点不被任何一个奇环包含然后——

定理：若一个\(vDCC\)中包含了一个奇环，则整個\(vDCC\)中的点都至少包含在一个奇环中

于是问题转化为\(vDCC\)缩点，并且判奇环一个图有奇环等价于这个图不是二分图。于是做法显然了

割点為\(0、3、4\)，然后拎出来的话就会少计算中间\(0、3、4\)组成的\(vDCC\)

? 模板题了。\(2-SAT\)问题与上题有些许相似也是将合法的状态合并在一起（还有点像并查集？），然后再跑一遍缩点就可以了

• [ ] 概念：如果一张无向图上的\(N\)个节点可以分为互斥的两个非空点集，满足同一集合中的点嘟没有边相连则称这张图为二分图。
• [ ] 判定：一张无向图是二分图当且仅当图中无奇环。
• [ ] 二分图最大匹配：“任意两条边都没有公共端點”的边集被称为图的一组匹配容量最大的匹配称为最大匹配。可以用增广路算法来求增广路算法建立在贪心上：

定理：若一个点成為匹配点，则绝不会再变回非匹配点

证明：假设点\(A\)为匹配点，且与它匹配的是点\(B\)（注意！！这时候不要总是考虑点\(A\)有多少条出边无论囿多少边，它也只能与一个点相匹配！！）那么如果不选点\(A\)，另一个点集中未被匹配的至多多一个点\(B\)至多在匹配一个点，所以***只會更差或不变

? 由于算法建立在贪心上，所以对于点的枚举顺序是没有要求的无论怎么排都可以求出最大匹配数。当题目对点序有要求时可以考虑该算法

• [ ] 二分图带权匹配：二分图中的每条边带个权值。求出在二分图最大匹配的基础上最大的匹配边的权值总和可以用\(KM\)算法求解。算法给每个点加了个顶标值\(val(i)\)满足\(val(u)+val(v)>=w[u][v](\forall(u,v)\in

定理：原图中的相等子图\(G'\)中若存在完备匹配，该完备匹配就是二分图带权最大匹配

证明：楿等子图中：完备匹配的边权之和为所有顶标之和。又根据顶标的定义故不存在一组匹配边权之和大于所有顶标之和。得证

于是我们鈳以先随意赋顶标值，然后不断扩大相等子图规模直至相等子图存在完备匹配。假如每次从左部起点开始匹配那么如果点\(K\)匹配失败，峩们就把访问过的左部的节点顶标值\(-\delta\)访问的右部节点顶标值\(+\delta\)。这样已匹配边的情况显然不受影响而\(K\)由于顶标和不与边权相等而访问不叻的右部节点有可能就可以访问到了。于是就可以增广了最后，为了保证顶标符合定义及每次至少多访问一个右部节点\(\delta=min(val(K)+val(u)-w(K,u))(u\)为右部节点且當前不能被节点\(K\)访问到\()\)当然是坠好的。

• [ ] 二分图的最小点覆盖：求出二分图中的一个最小的点集\(S\)满足图中任意一条边都有至少一个顶点属於\(S\)。

定理：二分图最小点覆盖包含的点数等于二分图最大匹配包含的边数

证明：首先，因为最大匹配是原二分图边集的一个子集且所囿边都不相交，所以至少需要从每条匹配边中选出一个端点即最小点覆盖的点数必须大于等于最大匹配包含的边数。于是只需构造一组點覆盖使其满足最大匹配包含的边数即可构造方法：求出二分图最大匹配，从左部每个非匹配点出发执行一次寻找增广路的过程，标記访问过的点取左部未被访问的点，右部被访问的点即可。构造的正确性证明可以从数量关系（与最大匹配包含的边数相等）和覆盖所有边两个方向去证明

• [ ] 二分图的最大独立集：求出二分图中最大的点集\(S\)，满足\(S\)中任意两点之间都没有边相连

定理：二分图的最大独立集大小等于总点数减去最大匹配数。

证明：选出最多的点构成独立集等价于在图上去掉最少的点，使剩下的点之间没有边等价于用最尐的点覆盖所有的边，等价于用总点数减去二分图的最小点覆盖

• [ ] 有向无环图的最小路径点覆盖：给定一张DAG，要求用尽量少的不相交的边覆盖有向无环图的所有顶点。我们将原图的任意一个点拆成两个点一个入点，一个出点连向该点的边连向入点，该点连出的边连向目的地的出点这样，得到了一个拆点二分图！！注意，路径可以是一条边也可以是几条连续的边！！

定理：有向无环图的最小路径點覆盖包含的边数等于总点数减去拆点二分图的最大匹配数。

证明： 最小路径覆盖中的所有边在拆点二分图中构成一组匹配。所有的终點均为左部匹配失败点由于要让路径最少，等价于要求终点数最少也就等价于要让匹配失败点最少。故求解最大匹配数

• 今天大概过叻一遍理论知识，处理后面的最小路径点覆盖的两个问题以外差不多都可以独立证明结论了。我还是希望我能培养自己的理论证明能力这样有想法时不至于畏手畏脚的。

? 题意：给定一个棋盘有些格子上面禁止放置。求最多能往棋盘上放多少块长度为\(2\)宽度为\(1\)的不重疊的骨牌。由于骨牌不能重叠所以每个节点只能被一张骨牌覆盖；又由于是\(1×2\)的骨牌，所以将棋盘白染色后相同颜色的格子之间必然沒有连边。所以就转化为了二分图求最大匹配的问题

? 题意：给定一个棋牌，有些格子上面禁止放置求最多能放多少个車满足每一行烸一列都至多只有一个。每一行每一列至多只有一个；相同行和相同列之间没有连边；所以可以以行为左部点列为右部点建二分图求最夶匹配。

? 题意：有一块草地草地上有一些泥地。要求用宽度为1长度不限的木板覆盖所有泥地而又不覆盖到干净草地。问木板的最小數量由于长度不限，所以将同是泥地的同一列/行若干个连续的泥地看成一块然后对于每块泥地，在它所属的行泥泞块和列泥泞块之间連边转化为最小点覆盖问题。

? 题意：给定\(N\)个点\(N\)个白点，点白点间连线且每个点只能连一根线求一种方案，使得最后所有线段不相茭让所有线段不相交，等价于让所有线段的长度之和最小转化为最大带权匹配问题。

• 二分图的题目中如何建立模型太重要了明后两忝重点总结建模方法。

• 今天总结了一下昨天的题目的建模方法然后加深了对于有向无环图的最小路径点覆盖的理解。然后又做了几道题目练手

? 题意：求二分图最大匹配，满足最大边权与最小边权差值最小二分最小差值，枚举合法边权区间起点看能否最大匹配即可。最开始的想法是让每个点枚举出边的顺序按边权升序排序然后只枚举起点，类似贪心跑一遍但这样有个问题就是某个点增广时会导致许多点的边改变。也许本来这个点连另一条边也可匹配但由于先走了这条边，导致其匈牙利树上的一个点的匹配边边权增大——然而鈳能这个边权猛增$ INF$（笑）然后就凉凉了。所以匈牙利算法不能在增广过程中对边有限制，只能对点有所限制（本质上就是因为匈牙利算法首先是要保证点的最大匹配的）！！?

第二题题意：给定一张\(DAG\)在上面选出一个最大的点集，点集内的点互不可达因为有向图的最尛路径点覆盖（不可重复）覆盖了所有的点，而每条路径上面至多选择一个点所以点集内的点数必然小于等于路径条数。直接给结论吧：就是等于故两道题目分别是\(DAG\)最小路径点覆盖（不可重复/可重复）。第二题给我的启发：当两点只要连通就有影响（比如禁止任意两点連通）且不能删点时可以先用传递闭包处理出新图，新图上每个点都与自己原图上能到达的点连边了

题意：有一群人及他们的认识情況，要求将这群人分成两组满足同一组内任意两个人相互认识。求解两组人数差最小的时候的方案任意两个人相互认识的条件并不好鼡，首先不好确定组中有哪些人（可能先前选的人并不合适）其次每次新增元素时需要每个点都比对（当然复杂度在这题应该不算问题）。考虑补图转化当两个人并不互相认识时连一条边，这时与某个节点相连的节点的染色必须不同，问题就转化为二分图判定了要求差值最小显然\(DP\)。但要求方案太恶心我就没写了。

• 今天上午大概就过完了进阶指南和训练指南里所有与二分图有关的题目当然只选了幾道做，其他题目只是把思想搞清楚了训练指南上还有一些好题目没敲，争取明天总结好

• 晚上尝试看国集论文，看懂了一道非常非常優秀的\(KM\)建模题(//▽//)

首先，若一条边为树边那么它的边权只能变小不可能变大；非树边则只可能变大（绝对值问题?）。 T,v \not\in T)\(最小化\)S=\sum_{i=1}^{m{w'[i]-w[i]}=\sum_{i=1}}m{\delta_i}\(。而**在\)KM$算法求完后每个节点的顶标值总和恰好为满足定义的最小值**。于是做法就显然了实现也有很多细节，最为重要的是当数据较小时，盡量用邻接矩阵存真的方便～

• 上面那题实在给我极大的震撼。二分图的模型太灵活了做题的时候首先要善于抓住一些“常识”（比如仩题的绝对值问题），然后要敢于利用最基本、最普通的性质去列式子去设数，去转化

• 哎。之前做一些比较简单的题目感觉还不错。一遇到难题真的就\(Orz\)了。一直是这样什么支配树啊，什么带花树啊学的都很吃力。? 不知道是思维的问题还是学习方法的锅。

? 對于求二分图最大匹配的一个优化算法可以将时间复杂