这个入是娃，啥也不想留下
追踪最近的用户名外显变动记录。
最近的文章、讨论、云剪贴板与社区记录
在文章《题解：P14361 [CSP-S 2025] 社团招新 / club（暂无数据）》发表评论：
s2324年的第一题不都是黄题吗今年这个一上场心态就没了
先说一下字典树。 我们可以把每个字符串理解成链。 而树就是由一条条链组成的。 所以我们就可以把字符串造成树： 比如两个字符串： $abcdef$ 和 $abcdfe$ 。  这样这两个字符串共同…
## P3501 [POI 2010] ANT-Antisymmetry [题目](https://www.luogu.com.cn/problem/P3501) ### 判断回文 首先我们要知道如何判断一个字符串是回文的。 比如一个字符串： $ABCDCBA$ 首先可以用 $reverse$ ，但是时间是 $O(n)…
## U432142 ૮(˶ᵔ ᵕ ᵔ˶)ა祖孙询问 [题目](https://www.luogu.com.cn/problem/U432142) 原理很简单：当 $LCA(x,y)=x$ 时，两点的祖先为 $x$ ，反之就是 $y$ 。 如果 $LCA$ 又不是 $x$ 又不是 $y$ ，那就没有祖先关系。 来说**…
## U556200 破坏的距离 [题目](https://www.luogu.com.cn/problem/U556200) 这题其实跟最短路没关系，因为这题的图是树，树中两点之间的路径是唯一的。 写 $Floyd$ 照陈老师出的那个数据可以拿 $30$ 分，洛谷上可以拿 $60$ 。 但是树上求距离用的还是最近公共…
芝士先放这里了。 我们知道，在c++中，比较字符串用的是字典序。 也就是它们要一位一位的比。 那判断两个字符串的大小的时间复杂度就是 $O(min(len1,len2))$ ，其中 $len1$ 和 $len2$ 为两个字符串的长度。 这个其实非常的慢，如果要比很多个，直接和 $O(n^2)$ 一样了。 但是我们可以把…
## P6225 [eJOI 2019] 异或橙子 [题目](https://www.luogu.com.cn/problem/P6225) 首先最暴力的暴力很好写吧，直接枚举区间长度，然后枚举每个区间，直接算就行，能拿 $12$ 分。 优化一点，就用异或前缀和来算每个区间的异或和，能拿 $18$ 分。 再优化，把异或…
## U432142 ૮(˶ᵔ ᵕ ᵔ˶)ა祖孙询问 [题目](https://www.luogu.com.cn/problem/U432142) 这题虽然做对了，但还是说一下吧。 就很简单，如果两个点有祖孙的关系，那这两个点的 $LCA$ 就是那个两个点中的祖先。 所以祖孙关系就用 $LCA$ 来判。 如果这两个点的…
## P3174 [HAOI2009] 毛毛虫 [题目](https://www.luogu.com.cn/problem/P3174) 这题其实跟重心还没关系，是一道直径的题。 ### 简化题意 在一棵树中选取一条链，将这条链上的点以及他们的儿子节点全部取出，求取出的最少儿子数量。 ### 做法 这个我们就可以直接想…
## P3379 【模板】最近公共祖先（LCA） [题目](https://www.luogu.com.cn/problem/P3379) 暴力还是很好写的。给两个点，先从一个点往上走，把走过的都标记一下，另一个点也往上走，发现标记的第一个点就是 $LCA$ 。 但是这个很容易被卡：  首先树的中心有特性： 1. 树的中心一定在直径上。 因为所有的树都可以画成这样。  **四步法**： ①状态：`siz[u]` 表示将以 $u$ 为根的子树剪成一个特别二叉树，能保留的最多的点数。 ②答案：这题需要以每个点为根跑一遍 $dfs$ ，以 $i$ 为根的答案…
## P3372 【模板】线段树 1 多了一个区间修改。 这样想：修改是为查询服务的，那我们其实可以每次修改只打上一个标记，等要查的时候再去加上，这样就没有占用单独额外的时间。 那就分两个解决：修改和查询。 ### 修改 假如我们是让区间 $[L,R]$ 集体加上 $v$ 。 还是用 $[l,r,k]$ 来表示一个线段…
~~终于熬过dp了不用写四步法了~~ ## U53204 【数据加强版】选课 [题目](https://www.luogu.com.cn/problem/U53204) 这个跟线段树没关系，是上节课树上背包dp的。 [原题](https://www.luogu.com.cn/problem/P2014) 这题加强了数据…
## P2015 二叉苹果树 [题目](https://www.luogu.com.cn/problem/P2015) 引入树上背包。 **思路**：实际上还是选和不选的问题。因为是二叉树，我们可以直接枚举要保留几个，再枚举要在其中一边选几个，那样另一边选几个也就直接出来了。 还是用dp **四步法**： **①状态*…
~~怎么又来图论呀~~ 树上子树问题（选和不选）：子树大小 首先，复习一下树的特征： ``` 有n个点，n-1条边 是无向联通图 ```  比如上面这是一棵树。 有些树有根（比如上面那张图的根可…
只总结错的三四题 ## U562085 修理 [题目](https://www.luogu.com.cn/problem/U562085) 考试的时候对着这题瞪了一个小时才瞪出来，包没时间的 这题其实就是修电线杆的顺序不同，花的时间也不同。 那个修电线杆的时间其实不用管，也为修的时间永远都是**电线杆的数量乘 $t$*…
dp状态压缩，解决二维的选和不选 ## P1879 [USACO06NOV] Corn Fields G [题目](https://www.luogu.com.cn/problem/P1879) 数据比较小，所以暴力也能拿 $80$ 分 先读一遍题，找到种草的三个条件： 1. 有些贫瘠的土地不能种草 2. 不能在两块相…
这次这个是全排列问题优化，hamilton通路回路问题的**状压dp** ## 状压dp前置芝士 二进制的位运算 1. 位与 符号：`&` ``` 1 & 1 = 1 1 & 0 = 0 0 & 1 = 0 0 & 0 = 0 ``` 性质： 都是 $1$ 才等于 $1$ 只要有一个为 $0$ 就等于 $0$ 那就说明…
双端扩展型区间dp ## P1115 最大子段和 [题目](https://www.luogu.com.cn/problem/P1115) 又是这道熟悉的题呀 还是引入 这个就直接写四步法吧 ①状态： `dp[l][r]` $= \sum^{r}_{i=l} a_i$ ②答案： `max({dp[l][r]})` ③状…
这个主要是拆分型（合并石子类） ## P1115 最大子段和 [题目](https://www.luogu.com.cn/problem/P1115) 之前写过，这个主要是引入一下dp 把考虑过程也写上吧（当然考场上肯定是直接用结论） 一开始考虑暴力枚举 枚举子段的长度 就是这么两种写法： ```cpp for(int…
好吧这次考试听陈老师说是综合，以为是这一阶段的综合，在那敲了两个小时最短路的板子，结果考了个数据结构 还是只总结错题 ## U584958 快速幂 [题目](https://www.luogu.com.cn/problem/U584958?contestId=260844) 这题其实是最怕的 因为没有理解的很透彻，所以…
前两天学这个算法，今天考试考了这道题，写个题解吧。 [题目](https://www.luogu.com.cn/problem/P7629) 先把题目的那个英文的代码翻译一下： ```cpp 给定一个 需要排序的数组a while(a不是一个排序好的序列) { 将a划分成多个连续的下降区间; 将所有这些将所有这些区间翻…
前两天学这个算法，今天考试考了这道题，写个题解吧。 本蒟蒻的第一篇题解 [题目传送门](https://www.luogu.com.cn/problem/P8165) 树状数组要会呦。 其实就是把一个很难很难的公式推出来，然后直接套公式就行了。 题解区的公式推的漫天飞，都能看。 我这个写的是我们老师讲的。 操作1没啥好…
这里就只总结错题吧 ## U438285 ١١(❛ᴗ❛)【树状数组】-数星星 Stars [题目](https://www.luogu.com.cn/problem/U438285) 这个题树状数组进阶的总结里面讲过 当时提了重点：modify的时候x不能为0，因为c[0]的长度为0，会一直卡在那里 但是考试的时候不知…
# 值域树状数组 这个上面的不是题目，只是先把一些东西放到前面 陈老师说本来要出个例题，但是没出 **题目：给定n个数字，请输出每个位置i的在i左侧小于a[i]的数字个数** 可以发现这题对于一个j，需要满足`a[j] >a[i]; modify(a[i],1); } ``` 这里有一个重点 a[i]千万不能等于0 因…
## U438237 ١١(❛ᴗ❛)【树状数组+线段树】-模板（单点修改+区间查询） [题目](https://www.luogu.com.cn/problem/U438237) 先把之前画的st表的图放出来 这题有环，所以第一步：******断环成链****** 也就是开3n的空间 这里的题一定要读清楚 陈老师上课都差点翻车了 ![](https://cdn…