Problem - 1152F2 - Codeforces 发现 $k, m$ 很小这个东西肯定有问题。 要么是直接通向要么可以使用矩阵快速幂。 感觉任意两个元素都是不同比较难处理，所以我们考虑进行 $\tt Dp$。 设 $f(i ,j, S)$ 表示当前值是 $i$，是序列长度为 $j$。 因为直接按照序列进行放置值域是不好确定的，我们考虑进行插入操作。 对于值域为 $i$ 我们需要权值 $\ge i - m$ 的位置在其前面，所以 $S$ 表示权值 $\ge i - m$ 的权值有哪些在序列中。 当然我们可以放在序列的开头，因为我们考虑值域是从小到大的，所以可以直接进行操作。 $$\begin{aligned}f(i, j, S) \times (popcount(S) + 1) &\tof(i + 1, j + 1, (2S + 1)) \\f(i, j, S) &\to f(i + 1, j + 1, (2S))\end{aligned}$$ 直接矩阵快速幂即可。 1234567891011121314151617181920212223242526272 ...

Problem - 843D - Codeforces 竟然直接被我想对了。 首先这个 $O(nq)$ 貌似是可以过的，可以发现是求最短路问题。所以做法应该比较直观就是考虑每次暴力 $O(n)$ 进行更新。 如何进行更新呢？ 考虑原来的最短路，不妨设为 $d(i)$，现在有新增加的路径 $add(i)$。可以发现我们可以直接通过宽搜看一下 $add(i)$ 能否进行更新。 但是我们这样还是需要优先队列，我们考虑如何模拟这个过程，可以发现每次是 $+1$，所以距离最多是增加 $n$。我们直接开桶暴力存即可，如果发现 $add(i)$ 与当前信息不符合可以直接剪枝，复杂度是 $O(n)$ 的。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021 ...

Problem - 687E - Codeforces 图是不变的，如果出现环我们肯定是必须要一直遍历，所以我们肯定是考虑通过改变遍历顺序得到最小的环。 考虑缩点之后的强联通分量，如果一个强联通分量没有出边肯定是要自己内部构造环。 如果不然我们肯定是可以构造出一个到另外强联通分量的最短路径。 考虑一个环的贡献就是 $\text{点数} \times 999 + 1$。 对于全局来说就是 $\text{点数} \times 998 + n + \text{环数}$。 直接 $\tt tarjan$ 暴力做即可。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161 ...

Problem - 889E - Codeforces 愚人节快乐。 首先考虑每个 $x$ 最终得到的序列肯定是单调不递增的。 那么对于最终的答案我们可以表示成 $x_n \times i + b$ 的形式。 我们考虑对于这个东西能不能进行 $\tt Dp$，设 $f(i, j)$ 表示考虑了前 $i$ 个数，最终的 $x$ 是 $j$ 得到的最大的 $b$。 我们会发现有很多无用状态，如果存在 $f(i, j - 1) \le f(i, j)$ 那么前面的部分肯定是没用了。 所以我们只需要考虑 $f(i, k)$ 随着 $k$ 增大值是递减的情况，我们转移的时候同时转移 $[0, k]$ 可以发现所有的情况都被转移过了。 对于 $a_{i + 1} > k$ 的情况，我们可以直接转移到 $f(i + 1, k)$。 不然的话我们肯定是考虑最后一段 $0, 1, 2, \cdots k \mod a_{i + 1}$ 的这一段进行转移，这样可以叠加尽量多的 $b$。 可以发现我们的状态 $k$ 每次是 $\div 2$ 或者不变的，所以状态数是 $\log$ 级别的。 不妨 ...

Problem - 1344E - Codeforces 考虑我们肯定是对于每个点最终肯定是要进行若干次操作，每次操作是有时间限制的，不妨考虑需要在区间 $[l_i, r_i]$ 之间做完，那么对于这个东西我们肯定是考虑扫描线 $l$ 对于最小的 $r$ 进行贪心处理。 那么如果处理出来这个区间呢？本质上就是两条边进行更新的时候对于虚边进行翻转，本质就是 $\tt LCT$ 的 $\tt access$ 操作，那么时空复杂度就是和 $\tt LCT$ 操作类似。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412 ...

Codeforces - 1355 F 这个题好神仙呀！等等好像也没有那么难 /qd 显然我们只要知道了 $\tt X$ 的质因子，游戏就结束了。 然后题目还是允许有误差的，所以我们其实甚至不用找到 $ > \sqrt X$ 的质因子了。 之后考虑怎样去试这些质因子，发现 $2^{30} > V$ 感觉不是很行。 但是题目有一个比较松的限制：$\frac{1}{2} \le \frac{ans}{d} \le 2$。这个东西意味着因子个数只要是答案的一半就合法了。 我们考虑这个 $7$ 是来干什么用的，发现我们最蠢也是输出 $1$，所以考虑什么的因子个数是 $8$。 $3$ 个大质数相乘。 那么这个质数极限是多少？$\sqrt{10^9} = 10^3$。 考虑有更多质数相乘的情况，我们考虑肯定只有少量的大质数，根据条件我们是可以忽略一个大质数的，我们显然会忽略最大的那个。 具体来说我们考虑暴力枚举每个质数之后合并起来成为尽可能大的 $Q$，之后得到答案之后分解质因子得到哪些数是可以往大扩展的。 我们考虑对于如果一个数可能往大的方向扩展我们尽量优 ...

事情的起因来自这个： 前情提要：bitset 和 __builtin 函数 | Legendgod’s Blog $\text{Ha宝: bitset 还可以加速字符串匹配}$。 $\text{legendgod: /se/se}$。 如果手动实现一个 $\tt bitset$ 会怎么搞，肯定是通过一个 $\tt int$ 压起来，之后如果范围内的就查表，如果范围外就直接暴力跳，这样复杂度是有一个 $\frac{1}{w}$ 的常数，同理其一位只需要一个 $\tt Byte$。 关于字符串匹配我们考虑对于文本串 $S$，找出每个字符 $c$ 出现的所有位置，存在 $bt_c$ 中。 对于一个串 $T$ 考虑对于其每个位置都与 $S$ 进行一次暴力匹配，不妨设其长度为 $m$。 考虑记录一个答案 $\tt bitset$，$ans$。其中 $ans_i$ 表示位置 $i$ 能否成为答案。 对于位置 $i$ 的元素 $T_i$ 我们考虑让 ans &= bt[T[i]] << (m - i - 1)，可以发现这个东西本质就是对于每一位都进行一次验 ...

[省选联考 2020 B 卷] 丁香之路 - 洛谷 感觉题目比较神仙。 首先画画图，第一个很明显的就是如果每条需要走的边的点都是单调的，那么答案肯定就是直接按照最近的点连接。根据这样的情况我们发现这个就是一条链。 之后考虑一个点度数比较大的菊花的形式，菊花就会导致我们被迫走回头路，这个东西不好考虑。鉴于我们可以随意加边，我们不妨将回头路看成一条新的边，这样我们最终的答案就是每条边都只经过了一次。 每条边只经过一次的路径 $\to $ 欧拉路径。 对于欧拉路径的情况我们只需要保证每个节点的度数即可。 对于欧拉路径我们可以让 $S \to T$ 进行连边，这样我们可以不用考虑起始点和结束点究竟连接的是那个点，直接变成欧拉回路。 之后我们考虑对于奇数点进行连边。 但是可能会出现若干个环的情况，我们还是需要考虑图的连通性。直观的想法就是考虑将不同连通块之间连边之后最小生成树。 显然我们贪心考虑相邻连边即可， 为了保证欧拉回路所以最小生成树上的边肯定会经过两次。 或者说如果要遍历一遍最小生成树而且回到起点，那么每条边肯定会经过两次。 回到起点的原因就是我们将起点和终点连边，他们肯定在一 ...