之前虽然已经把博客放到 $\tt github$ 上了，但是更新的时候废话还是很多，这次直接就把这些东西全部都放到一个 $\tt bat$ 上。 首先我们需要遍历一个文件夹，直接使用最弱智的方法，就是直接进入文件夹，然后开始遍历。 这里 $\tt cmd$ 和 $\tt bat$ 是有区别的，对于 cmd，for 的参数是 %i，如果是 bat 的话就是 %%i。 1for %%i in (*.md) do copy %%i E:\JHB_legendgod\Blog\source\_posts\%%i 之后需要用到 $\tt gitbash$，我们添加 $\tt gitbash$ 里面的 $\tt cmd$ 文件夹到环境路径上就行了。

[NOI Online 2022 普及组] 数学游戏（民间数据） - 洛谷 简化题意： 给定 $x, z$ 求是否存在满足条件 $z = x \times y \times \gcd(x, y)$ 的 $y$，如果存在请输出，如果不存在输出 $-1$。 输麻了，md 普及比提高还难。 考虑设 $d = \gcd(x, y)$ 那么 $x = k_x d, y = k_yd, z = k_xk_yd^3$。 考虑我们最终要求的东西就是 $k_yd$ 考虑用根据三元方程组肯定是可以表示出的，考虑用已知量来表示未知，$k_yd = \frac{z}{xd}$，那么本质上我们只要求出 $d$ 就行了 ，考虑到我们可以通过 $\gcd$ 的条件进行迭代，因为 $\gcd(k_x, k_y) = 1$ 考虑通过这个性质构造出与 $d$ 有关的式子。 发现 $\gcd(x, y) = \gcd(k_xd, k_yd)$，将 $k_yd = \frac{z}{xd}$ 带入可以得到 $\gcd(x, \fr ...

[NOI Online 2022 普及组] 字符串（暂无数据） - 洛谷 看到题目发现一个明显的问题，就是如果删除了一个前缀我们就去世了，但是我们最后的答案总是字符串 $\tt T$，那么我们会考虑倒着做。 考虑怎么样才是可能合法的，也就是 $|S| - |T| - \text{减号的数量} \times 2$。 我们在这种情况下考虑 $\tt Dp$，设 $f(i, j)$ 表示 $T$ 的后缀 $j \sim m$ 匹配了 $S$ 中 $i \sim n$ 的一个合法子序列的方案数，之后考虑删除一个字符，我们发现如果选择删除后缀那么删除的肯定是下一个第一个不是减号的字符，我们需要记录这个删除的次数，再设一个 $\tt K$。 因为可能有很多个减号连在一起。 $s_i = -$： 删除后缀 $f(i, j, k) \to f(i - 1, j, k + 1)$。 删除前缀 $f(i, j, k) \to f(i - 1, j, k)$，这里为什么不用操作，事实上我们考虑了所有的后缀删除然后如果 $T$ 已经是合法的，根据我们上述的条件剩下的删除操作都是在删前缀， ...

考虑求 $\tt K = 4$ 的情况，本质就是考虑每个数的贡献，发现其贡献次数就是： $$\begin{aligned}a_{1, i} - a_{1, j} &\ge a_{2, j} - a_{2, i} \\a_{1, i} - a_{1, j} &\ge a_{3, j} - a_{3, i} \\a_{1, i} - a_{1, j} &\ge a_{4, j} - a_{4, i} \\\end{aligned}$$ 同时满足这些条件的方案数，这个东西可以直接使用三维偏序做。 但是我们可以不这样，考虑我们求 $f(i, j)$ 本质上就是四个位置的最大值最小值相加。 我们考虑对于最小值进行 $\tt min-max$ 容斥： $$\begin{aligned}&\max(A, B, C, D) + \min(A, B, C, D) =\\ &A + B + C + D \\&- \max(A, B) - \max(A, C) - \max(A, D) - \max(B, C) - \max(B, D) - ...

Serval and Bonus Problem - 洛谷 最近有 $\tt ARC\ F$ 题竟然是相似题，好吧其实也没有那么相似，但是第一步转换是经典的。 首先根据期望线性，求一条线段的期望就是求区间内所有点的期望的和。 之后考虑既然是点那问题就简单了，直接考虑每条线段的相对位置就行了，也就是考虑 $(2n + 1)$ 个点，随机排列被钦定的点 $X$ 被 $\tt K$ 条线段覆盖的期望。 直接考虑进行 $\tt Dp$，考虑去对点进行匹配，设考虑到第 $i$ 个点，还有 $j$ 个点没有右端点，当前位置有没有被选择的方案数。 $$\begin{aligned}f(i, j, k) &\to f(i + 1, j + 1, k) \\f(i, j, k) \times j &\to f(i + 1, j - 1, k) \\f(i, j, 0) &\to f(i + 1, j, 1), j \ge K\end{aligned}$$ 当然我们最后的时候还要考虑线段的顺序，点的顺序，两个端点的顺序，还要把之前是考虑长度为 $1$ 现在变成 $l$ 了。 ...

Problem - 1383E - Codeforces 发现删除后得到的子串肯定是原串的一个子序列，考虑我们怎么样才能改变这个串。 考虑如何删除一个 $0$，也就是要么直接删掉要么前面为 $1$。那么本质上就是随意删除。 如果删除一个 $1$，我们需要保证前后存在一个是 $1$ 的位置 我们继续考虑最终的序列也就是在连续的一段 $1$ 中是可以任意删除的，如果是连续的一段 $0$ 我们是不能被 $1$ 影响的，也就是在区间内不存在任意的 $0$。 那么我们事实上只需要考虑限制，也就是我们把每个 $1$ 都拿出来考虑 $0$ 的限制。 考虑将 $S$ 变成一个数组 $\text{ {pre(i)} }$ 表示位置 $i - 1 \sim i$ 的 $0$ 的个数，可以发现 $\tt T$ 合法 当且仅当 $\tt T$ 的前缀和后缀的 $0$ 小于新的数组的第一个或者最后一个值，对于 $\tt T$ 是可以和 $S$ 进行匹配，也就是意味着对于 $\tt pre$ 存在一个子序列对应的元素大于等于 $\tt T$。 考虑我们做法是用来填 $1$ 的所以需要注意全部是 $0$ 的情况。 ...

Walls 防壁 - 题目 - 黑暗爆炸OJ 一下子想不到什么数据结构来维护一车东西，因为考虑对于每个线段对于每一个点都是需要考虑贡献的，所以状态数就已经是 $O(n ^ 2)$ 了，所以要考虑减少状态。 考虑对于一个点 $x$，在区间 $[l, r]$ 是合法的当且仅当 $l \le x \le r$，发现没有什么特别的性质。考虑点 $r = l + len$，那么发现对于上述式子可以变成 $x - len \le l \le x$，诶，线段和点相互转换了。 我们考虑当前用点去匹配线段的情况，我们尝试缩减状态，很明显三条同向的线段是可以变成开头和结尾两条的，那么我们的线段就变成了左右横跳的情况。 但是我们 $\tt len$ 是会变的，我们考虑对于一个点 $l$ 在其左边的线段肯定是横跳到原来的 $x$，对于右边的线段就是 $x - len$，当长度变得足够大的时候我们会发现两条线段有重合部分了，对于这种情况我们其实只要跳到上线段右端点就已经是最优的。 所以我们考虑可以对于距离最近的线段进行删除，因为上述就已经不是反复横跳的情况了。 我们不妨将两条连续线段的编号记成下面线段 ...

[省选联考 2020 A/B 卷] 冰火战士 - 洛谷 奇怪的题面可以看成求 $\tt 2\max(\min(vl, vr))$，其中 $vl, vr$ 表示左右两边的能量和。 这个东西显然可以考虑二分，之后考虑假设我们二分出来一个答案我们需要通过二分找到每边符合条件的战士之和。 但是其实不需要这样，很明显发现我们是尽量让战士越多越好，当然这个条件肯定是有一个临界值，可以发现我们只需要考虑冰战士比火战士能量多和少的情况。而且对于这个情况我们还能发现温度肯定是某个战士的温度进行 $\pm 1$ 的偏移。 考虑直接对于这个温度进行二分，使用树状数组进行二分，这个东西本质就和倍增是一样的。 之后就是考虑无解是怎么判的，考虑无解就是取任意温度双方都有一方是不能参赛的，也就是冰战士的最低温度比火战士的最高温度要高，不然一定存在解。 细节： 冰系战士是不低于，火系战士是不高于。我们考虑什么时候一个战士是不能参赛的，对于冰系来说就是温度严格低于，火系是严格高于。如果考虑让冰系贡献减去火系贡献的时候，加入冰系就是在其温度的时候，减去火系就是在其温度 $+ 1$ 的时刻。 1234567891 ...