好句
那些富有诗意的或引人深思的佳句
如果一个人在他年轻的时候居然是保守派，那他没良心；可如果他六十岁了还是个开明派，那他没脑子。
在任何时候，我们总希望世界对我们只有一条标准。因为这对我们来说很简单。
人从来不靠标准指导，而是人发现自己想要什么之后，再把它归纳成标准。标准是一种后验的东西。
或许世人道你轻狂，可你本就年少啊。
时间就是金钱，我现在可以回答拿金钱来买些什么了；效率就是生命，生命之外刻意追求生活了。
我们现在最大的悲哀是我们经过四十年的忙碌之后忘掉了失去了闲暇的能力和盼望。我们视闲暇为罪恶，视闲暇为迷茫。
如果社会观念不先改变，如果高考的指挥棒不先改变，如果分配体制不改变，你有什么资格让他别内卷，你有什么能力让他先走。谁敢呐。坦白说，资源集中的地方，内卷必然存在。我们躺在时代的红利上，现在该还债了。
既然这个社会都在告诉我们人不轻狂枉少年，那没有人应该天然地觉得轻狂是一个贬义词。
这夜熬着，找着自己，有时候，付出一些代价又如何呢。谁不知道这夜熬着的青春有些时间在往后走，但给我们最后的一线天，一些机会去碰触自己吧。
人和人本来就不在一条跑道 ...
4 月 7 号模拟赛题解
4.7 模拟赛祭第二次 AK 这次是首 AKer。CF126B PasswordDescription给定一个字符串 $s$，求 $s$ 的一个最大 $\text{border}$ 使得它除了在收尾，在中间也出现过。
Solution显然，中间存在过一个 $\text{border}$，也就是对于末尾的 $\text{border}_n$，存在一个中间值 $j$ 使得 $\text{border}_j=\text{border}_n$。而且，注意到所有的 $\text{border}_i\le n$，因此开一个桶 flag 来记录中途出现的 $\text{border}$，最后结尾不断跳 $\text{border}$ 判断之前有没有出现过。
1234int j=border[n-1];while(j&&!flag[j]) j=border[j-1];for(int i=0;i<j;++j) cout<<c[i];cout<<endl;
P3879 [TJOI2010] 阅读理解Description给出一些句子，包含一 ...
树上分治
树上分治点分治基本思想类似于链表中的二分，链表作为树的一种特殊形式，那么我们是否可以把链表中的二分扩展到树上，完成树上一些关于路径的问题呢？于是我们就引入了 点分治 这个算法。具体地，点分治是通过有一定技巧地枚举路径的必经点，然后不重不漏地计算出所有路径的贡献。
那么如果我们普通枚举，不仅时间复杂度会变成 $O(n^2)$，连正确性都很难保证，这是因为普通枚举很难保证不重不漏。但是点分治给出了一种方法，使得复杂度在 $O(n\log n)$ 的情况下能够正确的处理问题。
类比链表，链表是通过枚举中点来把需要枚举的区间分成等大的两份，再通过该点是否符合题意，结合整个决策的单调性来判断临界点，在严格 $O(\log n)$ 内解决问题。那么我们在点分治的时候能不能也找到一个方案使得每次至少将问题规模缩小一半呢？这不禁让我们联想到一个概念：树的重心。
树的重心对于一棵树，若树上的一个点 $x$ 满足：对于 $\forall y$，都有 $mx_x\le mx_y$，则称点 $x$ 是该树的一个重心。
其中 $mx_u=\max\limits_{edge=(u,v)} s ...
Hello World
Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.
Quick StartCreate a new post1$ hexo new "My New Post"
More info: Writing
Run server1$ hexo server
More info: Server
Generate static files1$ hexo generate
More info: Generating
Deploy to remote sites1$ hexo deploy
More info: Deployment
At_dp选讲
At_dp 选讲前言这一次做 Atcoder 上的 dp 题目，将26道题都刷了一遍，各个方面都有涉及，但每个都只涉及一到两题，总体来说掌握的不是很扎实，但现将这些东西写成blog巩固一下。
背包问题背包问题分为很多种，常见的有01背包、多重背包、完全背包、分组背包等等，问题都是关于给定 $n$ 个限制 $w_i$ 和价值 $v_i$，求在 $\sum w_i\le W$ 的情况下最大化 $\sum v_i$。在这里，Atcoder 上只给出了01背包和它的状态设计优化。
01背包 (Atcoder_dp_d Knapsack1)对于 $n$ 个物品，每个物品只能取1次，问 $\sum w_i\le W$ 的情况下最大化的 $\sum v_i$。
考虑我们要用到什么状态，首先需要选到了第几个物品，然后需要知道现在的重量是多少，以免超过 $W$。那么不妨设 $f_{i,j}$ 表示选到第 $i$ 个物品还剩 $j$ 的容量的最大价值，于是显然：
$$f_{i,j}=\max{f_{i-1,j},f_{i-1,j-w_i}+v_i}$$
同时注意到 $i$ 只与 $i-1$ 有关 ...
杜教筛
杜教筛前置芝士线性筛保证每个数只被它的最小质因子筛到。为了达到这个目的，我们在枚举 $i$ 时只枚举比 $i$ 的最小质因子小或相等的质数。即：if(i%p[j]==0) break;。因此保证了该筛法的线性。
积性函数若函数 $f(x)$ 满足 $f(pq)=f(p)f(q)$，其中 $\gcd(p,q)=1$，则称函数 $f(x)$ 为积性函数。
大部分数论函数为积性函数。
狄利克雷卷积定义对于两个函数 $f(x),g(x)$ 的运算 $(f*g)(x)=\sum\limits_{d\mid x}f(d)g(\frac{x}{d})$ 或 $\sum\limits_{d\mid x}f(\frac{x}{d})g(d)$，这个运算叫做 $f$ 与 $g$ 的狄利克雷卷积。
莫比乌斯反演设函数 $g(x)=\sum\limits_{d\mid x}f(d)$，则 $f(x)=\sum\limits_{d\mid x}g(d)\mu(\frac{x}{d})$。这过程叫做莫比乌斯反演。
简单证明：给定条件 $g(n)=\su ...
换根DP
一般情况对于树上 DP，要求求以每一个节点为根的树内的 $dp$ 值，这类问题我们可以用换根 DP 完成。一般地，我们总是用 $f_{fa}$ 来更新 $f_u$，可以写成
$$f_u=f_{fa}+val(u,fa)$$
的形式。
其中，最重要的是找到由父亲转移到儿子会产生那些贡献和算重的贡献，将贡献加上，多余的减掉，一般就可以在 $O(n)$ 内求出所有的贡献。流程一般包括两遍 dfs，第一遍统计以 $u$ 为根节点的子树内的答案，第二遍由 $1$ 号节点开始进行换根。
典例分析P3047 [USACO12FEB] Nearby Cows GDescription给定一棵树，没给点有权值 $a_i$，对于每个点 $u$，求：
$$\sum\limits_{\operatorname{dis}(u,v)\le k}a_k$$
Solution观察 $n$ 的数据范围是 $10^5$，考虑换根DP。
首先设状态，因为注意到 $k$ 仅有20，我们可以设 $f_{i,j}$ 表示以 $i$ 为根节点的子树内与它距离为 $j$ 的点的权值和。
首先第一遍 dfs 求出来再子树内的 ...
斜率优化
前情回顾如果对于一个 1D/1D 动态规划，即状态一维且递推公式可以化简为 $f_i=\max{f_j+w(i,j)}$ 的形式的动态规划，这样的动态规划在 $w(i,j)$ 不含同时与 $i,j$ 相关的函数时可以使用单调队列优化，即可以写成
$$f_i=\max{f_j+h_i+g_j}=\max{f_j+g_j}+h_i$$
时可以使用单调队列优化。
但是，如果 $w(i,j)$ 中包含同时与 $i$ 和 $j$ 相关的项，在 $j$ 项一次的情况下，可以使用斜率优化来 $O(n)$ 或 $O(\log n)$ 地完成题目。
一般情况对于一般式：
$$f_i=\max{f_j+h_i+g_j-k_ix_j}$$
我们首先去掉 $\max$：
$$f_i=f_j+h_i+g_j-k_ix_j$$
将只含有 $j$ 的移到等式左边，其它的移到等式右边：
$$f_j+g_j=k_ix_j-h_i+f_i$$
在转移 $i$ 项时，我们可以将只含 $i$ 的函数看成常常数，于是计 $b_i=-h_i+f_i$ ...
李超线段树
李超线段树—— 维护多个一次函数单点最值的数据结构
基本算法李超线段树本质上是一个标记永久化的线段树，对于插入的一条线段 $(x_0,y_0),(x_1,y_1)$，我们在区间 $[x_0,x_1]$ 上进行修改：
如果线段树上该点还没有线段，直接赋值。
如果原线段树上储存线段的中点值比该线段小，那么交换两条线段，这是保证两端只会有一段使得加入的线段比原线段更优。
判断哪边插入线段更优，递归继续讨论哪边。
于是，我们就插入完了一条线段。关于时间复杂度，我们首先会把一条线段分成 $\log$ 份往下递归，然后每次递归最深能够达到 $\log$ 次，因此一次插入线段是 $\log^2$ 的。但是对于直线，我们不需要分成 $\log$ 份的操作，因此复杂度为单 $\log$。
对于一次查询操作，我们能够一路递归下去，然后取所有线段在 $x$ 的值的 $\max$。之所以要一路取 $\max$，是因为我们在存的根节点的线段只是中点最大的线段，但是对于所有的它不一定最大，因此一路往上取 $\max$ 即可。
对于大部分题目，我们只需要掌握直线的李超线段树即可，因为在优化动态规划的时候基本都是 ...