0103abc 的网站

插头 dp 入门题，（建议先做这题然后再做 ~~5066~~ 5056）。仍然是套路的搞一个轮廓线然后按照顺序处理每一个轮廓线打折的地方。假设当前枚举到 $(i,j)$ 格子，左插头为 $p$，上插头为 $q$。 这里定义插头 $x$ 的状态： $x=0$，表示该方向无插头。...

看到代价为平方式，可以想到拆括号列一次函数然后扔到李超线段树中维护，但是这个题和李超线段树没有关系。 观察题目，发现给出的操作十分奇奇怪怪，因此考虑手玩小数据然后观察性质。 容易发现，$2$ 操作若操作的区间为 $[l,r]$，则必须满足 $r-l+1=2$，可以证明其他情况一定不优：...

比较奇怪的 dp 题。设 $f_{i,j,k,p}$ 表示 $i\sim n$ 的点中路径条数为 $j$，黑色奇点数目为 $k$，白色奇点数目为 $p$ 方案数是多少。转移直接计数即可是容易的，时间复杂度为 $O(n^4)$。 是否可以优化？答案是可行的。观察到其实路径条数 / 黑色奇点数目 /...

一个神经的单 $\log$ 做法。直接做十分神秘，考虑先转化问题：考虑到对于两个有共同父亲结点的叶子结点，她们到根节点的距离的差的绝对值必然为 $1$。因此问题转化为： 给定一个长度为 $n$ 的序列 $a$，现每一次可以选择相邻的两个位置，满足她们的差的绝对值为...

不会杨表，所以使用 dp of dp 来求解这个问题。 有一定思维含量的 dp of dp 题。先考虑内层求 LIS 的过程。设 $fi$ 表示当前以 $i$ 结尾的 LIS 长度最长是多少，转移就是再插入一个数是容易的，但是将其压缩到 dp 数组中是困难的。有一个想法是康托展开，但是仍然有...

经典套路为 $\text{dist}(i,j)=\text{dep}i+\text{dep}j-2\text{dep}{\text{lca(i,j)}}$。考虑先求 $\text{dep}i$ 的期望：显然有 $\text{dep}1=0,...

目前这题 C++ 题解全都可以被下面数据 hack： 所以这里提供一份可以通过数据和 hack 的 C++ 题解。 考虑贪心。很显然把一个边长为 $a$ 的正方形劈开一定不会更好，因此考虑贪心的在长方形中选取最大的正方形。发现这就是辗转相除法，因此直接按辗转相除法模拟即可。时间复杂度为...

考虑到 $d\ge k\times k$ 的时候一定可以在两次转弯之内得出答案，因此特判即可，剩余情况均满足 $d<k\times k$。 此时暴力枚举答案为 $i$，则使用 bitset 维护当前所有可以到达的位置即可，更新答案可以直接暴力更新。

（标题有含义） 比较困难的题，考察了大量点双的性质 考虑对于一个点双连通分量，其具有下面的性质： 无割点。 任意两个点 $a,b$ 均可存在一条简单路径连通。 递进于上一条，任意两个点 $a,b$ 都存在两条简单路径，使得这两条路径除了 $a,b$ 两个点以外其余点两两不相同。 对于任意两个点...

狗屎题。下面提供一个在原有时空限制（$\textbf{2s}\ /\ \textbf{500MB}$）下能通过的算法。 首先因为图是网格图，所以容易想到设 $f{i,j}$ 为从 $(1,1)$ 开始向下走到 $(i,j)$ 所需要的最小边权，转移容易。若此时无删除操作，则答案即为...