Problem - 1437F - Codeforces 题目比较弱智，但是我更加弱智。 首先考虑排序之后肯定是没有关系的，从小到大进行插入。 考虑插入了 $i$ 位置之后的结果 $f_i$，我们发现如果需要插入必须找到一个位置 $j$ 使得 $2a_j \le a_i$，当然对于 $\forall k \le j$ 都是可以进行转移的。 我们考虑位置 $j$ 前面满足 $2a_k \le a_j$ 的最大位置 $x_j$，那么经过 $j$ 的插入之后总共有 $x_j + 1$ 个元素。同理对于 $i$ 来说序列的长度是固定的就是 $x_i +1$。 考虑插入到了位置 $j$，也就是通过 $f_j$ 进行转移，对于只受 $i$ 影响的数我们肯定可以在 $i$ 之后任意排列，数的个数总共有 $x_i - x_j - 1$。 $j$ 也是需要算进去的。 对于位置 $i$ 可以考虑还有几个位置可以放置，显然有 $n - 1 - 1 - x_j$。 减去 $i, j, x_j$。 所以方案数就是 $A_{n - 2 - x_j}^{x_i - x_j - 1} = \df ...

整除分块就是一种可以将相同值一起计算，使得带有取上整或者取下整的式子可以在 $O(\sqrt n)$ 内计算。 我们考虑一种比较简单的式子： $$\sum_{i = 1}^ n \lfloor \frac{n}{i}\rfloor$$ 直接进行打表可以发现有一些部分是相同的，我们考虑一起计算。 不妨考虑 $\left \lfloor\dfrac{n}{i} \right\rfloor = k, n = ki + r$。 考虑会带得到 $\dfrac{n - r}{k} = i$，考虑 $r \in (0, i)$，而且我们有 $\left \lfloor\dfrac{n}{i} \right\rfloor = k$。 所以我考虑如果想要让 $i$ 最大，我们必须满足 $r = 0$，所以我们有 $max(i) = \left \lfloor \dfrac{n}{\dfrac{n}{i}} \right\rfloor$。 我们仔细思考复杂度，每次让 $\lfloor\dfrac{n}{i}\rfloor$ 不同的 ...

Codeforces - 830D 考虑这个东西可以做到 $O(k^3)$，要么是一个矩阵的形式，要么是二维状态的 $\tt Dp$。 感觉矩阵一下子想不出来有什么前途，考虑对于每个点，其儿子本质上就是子问题，我们考虑设答案为 $f_n$。 考虑转移的时候要么是直接从儿子中转移，要么是考虑儿子的一条路径经过自己得到的，注意两条路径如果要合并的时候是不能有重复节点的。 如果一个节点的祖先是自己，那么就存在连边，所以任意一条路径总是可以通过根节点的，我们考虑转移的时候需要通过若干条不相交的路径进行计算，所以设状态为 $f(n, k)$ 表示根节点为 $n$ 选择了 $k$ 条不相交路径的方案。 转移的时候考虑根节点自己作为一条路径。 两条路径不算根节点。 根节点和某条链相连接，可以连接头或者，也就是是否通过返租边。 根节点合并两条链，总共有 $K + 1$ 条链，选择两条即可，也就是钦定一条头和尾。 $$\begin{aligned}f(n, K) &= \sum_{i + j = K - 1} f(n - 1, i) \times f(n - 1, ...

$\tt bitset$ 是一个比较神奇的东西，我感觉经常用来卡常数，毕竟这个东西有 $\frac{1}{w}$ 的常数。 事实证明，如果写埃氏筛用 $\tt bitset$ 比欧拉筛要快。 定义：就是一个存了 $0/1$ 串的东西，每个位占用一个 $B$。 可以使用 unsigned long long 或者 string 进行初始化，默认值为全 $0$。 $\color{red}\text{pay attention ! }$string 最右边的那一位是被放在 bitset 的位置 $0$ 的，数字同理。 123bitset<maxn> vis;//000...000bitset<maxn> vis1(5);// 000...00101bitset<maxn> vis2("100101"); // 000...100101 $\tt Bitset$ 函数 flip() 全部取反。 filp(x) 取反下标为 $x$ 的位置。 size() 返回位数（大小）。 count() 返回 $1$ 的个数。 ...

[IOI2015]teams分组 - 题目 - 黑暗爆炸OJ 考虑对于一个点 $i$ 的区间 $[l_i, r_i]$ 不妨假设按照 $l_i$ 从小到大排列，如果一个点 $i$ 是可以取到的情况，我们可以发现对于所有可以取到的肯定是选 $r_i$ 最小的进行取走。 我们考虑对于每个询问从小到大来做，考虑将每个 $[l_i, r_i]$ 对应到二维平面的 $(x, y)$ 上，对于每个询问记录在这次询问之后没有被取走的 $y$ 的最小值，设其为 $h_i$。 那么对于一个 $k_x$ 如果 $h_i < k_x$ 显然是可以直接取的，如果出现 $h_i > k_x$ 我们需要考虑其剩下没有取的元素，这个东西可以通过单调栈来维护。 之后对于平面上二维数点，直接使用可持久化线段树即可。 考虑加入一个元素的情况，直接在线段树二分位置即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656 ...

之前虽然已经把博客放到 $\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$ 已经是合法的，根据我们上述的条件剩下的删除操作都是在删前缀， ...