CF383E Vowels CF383E Vowels。 emmm 可以自己想出来的简单题。 就是考虑容斥，也就是 $A \cup B = A + B - A \cap B$。三个数的情况也是同理。发现每个字符串的长度 $= 3$ 所以我们可以直接对于集合大小是 $3$ 的进行暴力容斥计算。 之后我们考虑集合的合并，直接进行状压 $\tt Dp$，我们考虑删除最前面和最后面的那一位的贡献之和减去同时删除的贡献即可。 或者说我们可以考虑更好写的情况。我们发现合法的集合肯定是至少包含其中一个位置的。 对于至少可以通过取补集转换成全部不包含。 对于一个不合法的集合肯定是所有位置都在这里的，那么后者完全可以使用高位前缀和进行维护，我们对于每一个补集进行计算即可。 显然所有的集合都被计算过了。因为两个交集为空，并集为全集的集合会互相计算。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#i ...

$$\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 ...