$$\textbf{Funtion}\ \text{的使用}$$ 关于 function属实是一种有趣的语法。 我们常常会碰到的问题，就是我们在一个函数内部想使用其局部变量来进行一些操作。 我们常用的写法是直接定义一个函数： 123auto F = [&, i] () -> void{ ..... }; 但是如果说我们需要使用一些递归的调用，auto不能判断出其类型，我们就必须使用 function函数。 换言之 function本质上是一种类型，表示一个递归函数的指针。 1function<A(B)> dfs; 其中 A表示返回值的类型，B表示要填的参数。 举一个列子，我们需要遍历以当前节点 $x$ 为根的树。 123456for(int i = 1; i <= n; ++ i) { function<void(const int& p,int pre)> dfs; dfs = [&] (const int &p,int pre) { for(au ...

CF1562E Rescue Niwen! CF1562E Rescue Niwen! 应该是经典 $\tt Dp$ 题目的变种。 字符串 $\tt Lis$ 直接做复杂度是 $O(n^3)$ 的。我们来找寻一下这个的性质。也就是考虑对于一个字符串如果选择了他，肯定可以选择其之后的所有后缀，答案肯定会更优的。 那么我们的 $\tt Lis$ 可以枚举每个位置的起点，如果能加就肯定是直接加了。 $s_i > s_j$ 肯定是直接加入了，别忘记加上 $j$ 后缀的贡献。 $s_i = s_j, s_{i + lcp(i, j)} > s_{j + lcp(i, j)}$ 同样加入贡献，但是为了保证合法我们的 $i$ 肯定需要选之后的 $lcp(i, j)$ 个字符来保证可以接到 $j$ 上。 但是我们第二种方法不一定更优，我们钦定一下转移的顺序从小到大进行转移，可以发现后缀是变少的，那么选了 $j$ 的后缀肯定不会比选了 $i$ 的后缀更劣。 123456789101112131415161718192021222324252627282930 ...

CF1550F Jumping Around CF1550F Jumping Around 经典的转化，可能有点正难则反的意味。 $\textbf{我的思路：}$可以看出因为 $d$ 是不变的，所以对于一个逐渐增大的 $k$ 可以到达的点是逐渐变多的，换言之就是具有单调性。 有一个比较显然的想法，就是离线一下 $k$ 考虑从小到大进行计算。考虑暴力，就是对于每一个 $k$ 建图跑一遍 $\textbf{Dijstra}$。 复杂度是 $O(n^2 + q\ n\log n)$ 的，用一下线段树优化建图复杂度就是 $O(q\ n \log n)$ 了。 尝试考虑能否继承，但是没有结果。那么我们对于一个 $k$ 进行判断，不妨我们判断对于一条路径其合法需要的最小的 $k$。 $\textbf{题解：}$我们思考对于一条路径其最小的 $k$ 就是其路径上的最大值，也就是说我们对于任意一条路径我们要让其最大值最小。这就可以使用最小生成树维护了 $(\text{也就是最小生成树的定义})$。 但是发现边数是 $O(n^2)$ 级别的，直接会想到那个奇妙的 $\textb ...

HDU6580 Milk HDU 6580 Milk 校内考试题目，感觉考试的时候没看这题，之后还被恶心了一下 $\dots$。 考试的经过： 搞 $\tt T3$ 嗯，很好简单二项式反演。好最后转换错了，没了。 之后 $\tt 30 \ minutes$ 诶呀这个不是网络流题吗？高分暴力呀！！ 之后没写出来，显然网络流不能处理这个东西，及时说每次修改终点那一段的权值。仅仅是样例就能说明费用流显然是直接流最好。这个真的要搞清楚定义，哎呀。 感觉建图的时候还要稍微改一下不能很随便就直接距离连边之类的。 题解：我们考虑只有中间的一条线可以走，我们不妨对于每一个终止行进行计算。那么其他的位置肯定是 进入行的内部再回到中间 。 不妨对于每一行进行 $\tt Dp$ 保存向左终止和向右终止，向左返回和向右返回的情况。 之后合并的时候使用背包。 每次 $\tt Dp$ 的时候对于每个位置都计算一次贡献，从距离起始点从近到远进行计算即可。 之后每次枚举行，然后记录一下之前的 $\tt Dp$ 。 不要忘了离散化。 123456789101112131415161718192 ...

切比雪夫距离和曼哈顿距离 众所周知两个点 $(x_1, y_1), (x_2, y_2)$ 的曼哈顿距离是 $|x_1 - x_2| + |y_1 - y_2|$。 显然我们可以通过不等式去掉绝对值 $\max(|x_1 + y_1 + x_2 + y_2|, |x_1 + y_1 - (x_2 + y_2)|)$。 切比雪夫距离就是 $\max(|x_1 - x_2|, |y_1 - y_2|)$。 然后我们发现这两个格式很像，事实上确实是可以转换的： 曼哈顿距离 到 切比雪夫距离 ： $(x, y) \to (x + y, x -y )$。 切比雪夫距离 到 曼哈顿距离 ： $(x, y) \to (\frac{x + y}{2}, \frac{x - y}{2})$。 注意： 可能 $\frac{x + y}{2}$ 不一定是整数，那么我们不妨考虑在四周枚举一下。 P3964 [TJOI2013]松鼠聚会 P3439 [POI2006]MAG-Warehouse 这题就是经典的不一定是整数，我们要在周围的点分类讨论一下。 123456789101112131 ...

P7444 「EZEC-7」猜排列 这个是 $\textbf{2021.9.10}$ 未完成的最后一题。 就是先找找性质，发现 $f(0)$ 的时候本质上就是不包含 $0$ 的区间个数，不妨设 $0$ 在位置 $i$ 那么显然 $(i - 1) \times (n - i) = f(0)$。最多有两个这样的位置。 而且是对称的。 之后我们考虑进行 $\tt Dp$ 每次记录极大的区间也就是设 $f(i, l, r)$ 表示考虑了 $1 \sim i$ 的位置，极大区间是 $[l, r]$ 的方案数。 然后对于一个位置 $x$ 放在 $l$ 的左边的时候，可以满足 $c_i = (l - x + 1) \times (n - r + 1)$。 为了找到 $x$ 的位置显然 $n - r + 1 | c_i$。 如果出现 $c_i = 0$ 的情况，那么这个位置肯定只能放在 $[l, r]$ 中间，那么我们看一下是否能放即可。 直接讲一下优化，就是将之前的东西打表发现每一个 $dp$ 只有一个 $l$ 是有用的。我们不妨每次记录之前有用的 $l$ 然后用 ...

[USACO08NOV]Toys G首先可以网络流建图，但是因为 $n$ 的范围很大，所以我们考虑换一种方法。 首先考虑网络流建图的时候我们是考虑拆点之后进行跑流量，对于所有满流的情况我们计算一个最小费用。 我们对于这种情况不妨进行二分答案之后进行判断，显然我们二分的不能直接是答案。我们考虑那个条件我们知道了之后可以进行贪心或者 $\tt Dp$。总共就那么几个条件，只有购买了多少个是不知道的。那么我们就二分买了几个玩具。 简单思考可以发现对于买的玩具数量和花费是一个二次函数，下凸，进行三分。 具体贪心： 首先如果一个方案时间又短又优秀显然只用这个方案，不然两种方案肯定是一个时间短花费多，另一个反之。我们考虑用队列维护又多少没有消毒的，然后每次优先通过时间长的进行消毒，不然我们就使用时间短的进行消毒。 这里有一个问题如果放到了时间短的里面但是没有被使用，之后又可以放到时间长的里面了。 对于这个疑问，我们可以每次将时间短的来更新一下时间长的，之后每次将贡献放到被使用的时候计算即可。 1234567891011121314151617181920212223242526272829 ...

CF150E Freezing with Style 经典的更优复杂度不会，大众分都懂。 就是对于中位数的话进行树上路径合并很难处理，那么我们不妨二分中位数，之后将 $\ge$ 的数作为 $1$，否则就是 $-1$。那么合法的一条路径肯定是权值和 $\ge 0$。 前面取等号是题目的要求。 那么对于一条路径如果其长度是 $\tt len$ 那么我们合法的配对路径的取值范围就是 $\tt[L - len, R - len]$。 因为要使其合法所以我们只要使用这个区间的最大值就好了。如果我们将路径长度从大到小排序，那么这个区间就是逐渐向右移动，本质上就是一个滑动窗口问题。 那么我们合并就可以处理了，具体来说就是将之前子树的信息记录，之后枚举当前子树的中路径的长度（这里相同长度的路径显然只要考虑权值最大的一个）。每次更新一下滑动窗口的区间即可。 最后我们再将当前子树和之前合并就好了。 一些代码中使用的数组： $i$ 的最大权值的节点编号。12345678910111213141516171819202122232425262728293031323334353637383940414 ...