CF1152F2 Neko Rules the Catniverse (Large Version) 题解
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 ...
CF843D Dynamic Shortest Path 题解
Problem - 843D - Codeforces
竟然直接被我想对了。
首先这个 $O(nq)$ 貌似是可以过的,可以发现是求最短路问题。所以做法应该比较直观就是考虑每次暴力 $O(n)$ 进行更新。
如何进行更新呢?
考虑原来的最短路,不妨设为 $d(i)$,现在有新增加的路径 $add(i)$。可以发现我们可以直接通过宽搜看一下 $add(i)$ 能否进行更新。
但是我们这样还是需要优先队列,我们考虑如何模拟这个过程,可以发现每次是 $+1$,所以距离最多是增加 $n$。我们直接开桶暴力存即可,如果发现 $add(i)$ 与当前信息不符合可以直接剪枝,复杂度是 $O(n)$ 的。
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021 ...
CF687E TOF 题解
Problem - 687E - Codeforces
图是不变的,如果出现环我们肯定是必须要一直遍历,所以我们肯定是考虑通过改变遍历顺序得到最小的环。
考虑缩点之后的强联通分量,如果一个强联通分量没有出边肯定是要自己内部构造环。
如果不然我们肯定是可以构造出一个到另外强联通分量的最短路径。
考虑一个环的贡献就是 $\text{点数} \times 999 + 1$。
对于全局来说就是 $\text{点数} \times 998 + n + \text{环数}$。
直接 $\tt tarjan$ 暴力做即可。
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161 ...
CF889E Mod Mod Mod 题解
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$ 级别的。
不妨 ...
CF1344E Train Tracks 题解
Problem - 1344E - Codeforces
考虑我们肯定是对于每个点最终肯定是要进行若干次操作,每次操作是有时间限制的,不妨考虑需要在区间 $[l_i, r_i]$ 之间做完,那么对于这个东西我们肯定是考虑扫描线 $l$ 对于最小的 $r$ 进行贪心处理。
那么如果处理出来这个区间呢?本质上就是两条边进行更新的时候对于虚边进行翻转,本质就是 $\tt LCT$ 的 $\tt access$ 操作,那么时空复杂度就是和 $\tt LCT$ 操作类似。
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412 ...
CF1355F Guess Divisors Count 题解
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 关于字符串匹配的应用
事情的起因来自这个:
前情提要: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),可以发现这个东西本质就是对于每一位都进行一次验 ...
P6628 [省选联考 2020 B 卷] 丁香之路
[省选联考 2020 B 卷] 丁香之路 - 洛谷
感觉题目比较神仙。
首先画画图,第一个很明显的就是如果每条需要走的边的点都是单调的,那么答案肯定就是直接按照最近的点连接。根据这样的情况我们发现这个就是一条链。
之后考虑一个点度数比较大的菊花的形式,菊花就会导致我们被迫走回头路,这个东西不好考虑。鉴于我们可以随意加边,我们不妨将回头路看成一条新的边,这样我们最终的答案就是每条边都只经过了一次。
每条边只经过一次的路径 $\to $ 欧拉路径。
对于欧拉路径的情况我们只需要保证每个节点的度数即可。
对于欧拉路径我们可以让 $S \to T$ 进行连边,这样我们可以不用考虑起始点和结束点究竟连接的是那个点,直接变成欧拉回路。
之后我们考虑对于奇数点进行连边。
但是可能会出现若干个环的情况,我们还是需要考虑图的连通性。直观的想法就是考虑将不同连通块之间连边之后最小生成树。
显然我们贪心考虑相邻连边即可, 为了保证欧拉回路所以最小生成树上的边肯定会经过两次。
或者说如果要遍历一遍最小生成树而且回到起点,那么每条边肯定会经过两次。
回到起点的原因就是我们将起点和终点连边,他们肯定在一 ...