# P8776 最长不下降子序列 ## 本题的*非*树状数组或线段树做法： ​ 首先回顾一下 LIS 问题，也就是最长（严格）上升子序列，除了朴素的 $O(n^2)$ 算法外，还有维护一个 $ends$ 数组，其中 $ends_i$ 表示 $i + 1$ 长度的 LIS 结尾数字是多少（需要数组下标从0开始的强迫症，如…

# # CF2091D Place of the Olympiad 题解 实际上是个简单的数学题，用到了鸽笼原理。大意是说 $n$ 个物品放入 $k$ 个盒子，则至少有一个盒子放入的物品数至少为 $\lceil \frac{n}{k}\rceil$ 个。 回到这题，显然一行放得越多，可能拼凑出的长度越大，那么数量最多的…

# KMP 板子题 题意不能再简述了，要想让添加上后缀形成的的回文字符串最短，我们要充分利用原字符串自身形成的回文子串。具体来说就是找原字符串的一个最长回文后缀。 将原字符串 $s$ 的反转串 $s2$ 拼接到 $s$ 之前，也就是对 $s2+s$ 做 kmp，得到的 $next$ 数组最后一个数就是匹配的最长回文后缀…

# 因数计数 一道比较（？）好的组合数学题。 使用 $cnt[i]$ 统计 $i$ 的出现频率，$suf[i]$ 表示 $i$ 的倍数的个数（不包括 $i$ 自身），$pre[i]$ 表示 $i$ 的因数的个数（不包括 $i$ 自身）。其中 $suf$ 和 $pre$ 数组可通过 $cnt$ 数组在 $O(N\ln N…

# 因数计数 一道组合数学题。 使用 $cnt[i]$ 统计 $i$ 的出现频率，$suf[i]$ 表示 $i$ 的倍数的个数（不包括 $i$ 自身），$pre[i]$ 表示 $i$ 的因数的个数（不包括 $i$ 自身）。其中 $suf$ 和 $pre$ 数组可通过 $cnt$ 数组在 $O(N\ln N)$ 复杂度内…

在讨论《全WA求调！！！》回复：

你排序了，编号是固定的，不能排序

在讨论《Bellmen-Ford 82分求diao》回复：

无法到达的点输出-1