P1775典。code#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=3e2+5;intn,a[N],sum[N],dp[N][N];signedmain(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n; memset(dp,0x3f,sizeofdp); for(inti=1;i<=n;

常用dp状态：\(dp_i\)表示以\(i\)结尾的XXX/前\(i\)个元素的XXX。涉及的类型（由易到难）：线性dp，背包，区间dp，树形dp（换根dp），状压dp，dp的各类优化（数据结构优化、斜率优化、四边形不等式优化......）。背包问题：01背包、完全背包、分组背包、多重背包、树上背包。P1455并查

拖更了一个暑假。P6492很妙的线段树阿。对于修改，我们无需用lazytag，只要每次跑到叶子节点去直接修改即可。对于询问，答案即为树根的信息，因为它每次询问的都是整个区间。最难的是pushup部分：我们需要维护三个东西，ans,lx,rx，分别表示当前节点的整个串的最长合法串/左端点开

UVA1328简单题。我们有结论：对于一个周期串S的子串T，它的最小循环节即为T-nxt_{\left|T\right|}。（具体请查阅往期笔记）于是，我们枚举所有前缀，检验上式是否能被当前前缀的长度整除并且不止一个循环节即可。code#include<bits/stdc++.h>usingnamespacestd;constintN=

CF126B朴素解法：求出原字符串的最长border，并kmp匹配出出现在中间的最长border，若没有则不断缩短border的长度，直到中间存在。若border长度减到了\(0\)，则无解。我们通过画图来探索优化方式。如图，蓝色部分为原串的最长border，红色部分为蓝色部分的最长border。容易发现，

Kobe-Morris-Pratt算法定义一些基本定义：border：是一个字符串的子串（不与其本身相同）且满足既是其前缀又是其后缀的字符串，我们称之为该字符串的一个border。Kobe-Morris-Pratt算法（以下简称KMP算法），是解决字符串匹配问题的一种算法，实际做题中常偏思维，通常用到的只有其中的bo

众所周知，换根dp是非常套路的。换根真好玩（换根dp：当不同节点作为根时，dp结果不一致，若枚举每个节点作为根，则时间复杂度过高，在此种情形下，可使用换根dp处理相邻两节点间的贡献，从而达到快速换根的效果。使用场景：对于一棵树，寻找以某节点\(u\)为根时取得的最大值/最小值

登神长阶！P1272&P1273请查阅往期笔记，此处不再赘述。其中P1273我们学到了定义更好求解的状态（一般是转化为价值，如本题），再通过枚举求解最终答案。P8625容易发现你选出的\(S\)一定是一个子树。然后这题就变成最大子树和了。关于最大子树和那题，请查阅往期笔记，此处不再赘述。

复习树形dp。树形dp定义状态一般套路：令\(dp_i\)表示以\(i\)为子树的xxx（要维护的信息），可以有多维，但一定会有这一维。P2016&P2014请查阅往期笔记，此处不再赘述。P2585以前是分讨每个节点有几个儿子，然后分别转移。其实不用分讨，直接将所有节点视作有两个儿子，初始时将它

树上倍增：维护\(dp_{i,j}\)表示节点\(i\)向上移动\(2^j\)步所到达的节点编号、区间最值、区间和等信息。倍增求LCA：预处理：令\(dp_{i,j}\)表示\(i\)向上走\(2^j\)步所到达的节点。转移：\(dp_{i,j}=dp_{dp_{i,j-1},j-1}\)。初始：\(dp_{i,0}=fa_i\)。查询

RMQ问题/ST表：静态区间求最值。实现（以最大值为例）：倍增dp,预处理\(st_{i,j}\)表示区间\([i,i+2^j-1]\)内的最大值，我们有转移方程：\[st_{i,j}=\max(st_{i,j-1},st_{i+2^{j-1},j-1})\]相当于是把\([i,i+2^{j-1}-1]\)与\([i+2^{j-1},i+2^j-1]\)这两段区间的最大值拼了

HDU6567首先我们发现每棵树内部的距离已经固定，只有经过新边的路径才会产生贡献。又因为重心到树上所有节点的距离和最小，所以我们连接两树重心。然后我们想到一个经典套路：计算距离可以不枚举点，只枚举边。于是我们枚举每条边，计算出它们各自被经过的次数，再求和即为答案。维护\(

树的重心当\(u\)作为根时，其节点数最大的子树最小，则称\(u\)为树的重心。性质一：节点数最大的子树的节点数不超过\(\frac{节点总数}{2}\)。（反证法，若某重心\(u\)的节点数最大的子树的节点数超过\(\frac{节点总数}{2}\)，则将其一个子节点提起来会更优）性质二：至多两个且一

树的中心当选取树上节点\(u\)为根时，最长链最短，则称\(u\)为树的中心。性质一：至多\(2\)个且一定相邻。性质二：一定位于树的直径上。性质三：若一棵树有多条直径，则它们必定交于树的中心。性质四：树的中心为根时，根到直径两端点分别为最长/次长链。U392706板子。

树的直径：定义：树上两个距离最远的点形成的简单路径（不重复走一条边/点）性质：不唯一。树的直径的端点一定是度数为\(1\)的点。证明：显然。树的直径若有多条，则必交汇于一点，即中心。证明：首先每条直径只能交于端点（因为是一棵树，一个节点不能有两个父节点），然后此交点必定

退役选手复活后的第一篇。https://www.luogu.com.cn/problem/SP4033其实只要一个insert.就是插入时没新建节点\(\to\)自己是别人前缀，插入时途经了别人的结束节点\(\to\)别人是自己前缀。code#include<bits/stdc++.h>usingnamespacestd;constintN=3e5+5,M=31;i

必考题四选一 Home&Accommodation选择高频考点的7个问题1.Whatkindofhouseorflatdoyouwanttoliveinthefuture?Well,currentlyIhavebeensharingaflatwithyoungcouple,andIhatethattheynevercleanupthekitchenafterusingit.Sointhef

\(\mathcal{TRIE}\)：用于存储和查询字符串的树形结构，相同前缀的字符串共用节点，每个节点存储一个字符。操作：insert：单次\(O(len)\)search：单次\(O(len)\)性质\(1\)：若一个字符串\(T\)作为前缀，则包含\(T\)的所有字符串的“终止节点”一定在以\(T\)的“终止节点”为根

    Today,morethan30yearslater,itgraduallydawnsonmethatpeoplelikeme,whowereborninthe1960sinChina,areprobablytheluckiestpeopleinhumanhistory,becausenogenerationislikeus,whohavebeenabletowitnesssuchtremendo

T1这是一道manacher模板，但是我们使用二分+hash\(O(n\logn)\)的做法。显然地，若长为\(len\)的回文串存在，则长为\(len-2,len-4,...\)的回文串也一定存在（在两端各删去若干相同字符即可）。至此，我们发现回文串分两类：奇回文串、偶回文串，在每一类当中分别具有单调性。于是

Mrs.Smith’slivingroom史密斯太太的客厅词汇Vocabularylivingroom客厅都成：living=liveing生活room屋子搭配：inthelivingroom在客厅文化：西方人一般都在起居室活动，所以客厅很大，一般可以一起聊天，看球，下棋什么的。near在……附近【不直接挨着】例

题目：有一个巧妙的解法：考虑这个问题,从一个没有限制的从1开始的递增序列找出第k个数,显然就是十进制的k。而这里则可以定义新的进制为"012356789"9进制,那么k对应的就是这个特殊的九进制数,我们只需要把它转换为十进制就行。代码：#define_CRT_SECURE_NO_WARNINGS#inclu

T1第一问开桶统计即可。第二问我们采用双指针，不断地移动\(r\)直到包下含有最多单词数的区间，再移动\(l\)使答案更优并不断更新答案即可。具体有一些细节见代码。时间复杂度\(O(n\logn)\)。可以把代码中的两个map换成数组存hashvalue，时间可以降至\(O(n)\)，但是我懒了

hashfunction（哈希函数）将一个规模很大的字符串用特定规则转化为特定数值，这种特定规则，我们称之为hashfunction。hashvalue（哈希值）字符串由哈希函数生成的数值。hashcollision（哈希冲突）多个字符串得到了相同的hashvalue。算法竞赛中的hashfunction通常将字符

状压dp空间优化技巧：滚动数组提前预处理出有效状态T1典题限时返场。上次讲的时候的代码用到了滚动数组，这次讲第二种优化。其实很简单，就是在dp前将所有状态枚举一遍，将同行冲突的判掉，合法的用\(st_i\)存储即可。方法很bf，但经试验可以发现一千多状态中仅有几十个