如果有写的不好的文章欢迎评论，我会在有时间的时候重写一篇更好的。
竟然咕到了 2021 年，还是更一下吧。
都不会做啊
LuoguLOJ分析显然二合一，先考虑 $m=2$ 的情况。可以知道 $2\times n$ 网格的方案数就是 $f_{n+1}$。为了方便，我们把 $l,r$ 都加上 $1$，那么相当于要求用同样的方法扩域计算即可。代码// ==================================== // author: M_sea // website: https://m-sea...
LuoguLOJ分析将每个格点拆成四个点，分别表示从这个点往右走、往下走、往左走、往上走。对每个点维护一个 $nxt$，表示按照题目中的方式下一步会走到哪个点上。可以发现 $nxt$ 构成了一些有向环，我们想办法对其进行维护。考虑将环拆掉一条边变成一条有向链，并用 LCT 维护这条链。我们同时维护每一段墙是否存在，并修改连进某个点的链。在修改时，我们首先断掉连进来的边，然后再根据墙的情况修改...
LOJUOJ分析首先可以通过二分用两次询问把第一个字符问出来，假设是 $\texttt{A}$，那么接下来不会再出现 $\texttt{A}$。考虑依次确定接下来的字符。有一个显然的 $2$ 次询问的方法，但是实际上可以 $1$ 次询问：设之前的串为 $\texttt{S}$，询问 $\texttt{SBSXBSXXSXY}$，那么如果返回值为 $|S|$ 则这一位为 $\texttt{Y}...
CodeforcesLuogu分析首先可以证明图的直径长度不超过 $15$。先预处理 $f_{i,j}$ 表示 $i$ 走到一个颜色为 $j$ 的点的最短路、$g_{i,j}$ 表示某个颜色为 $i$ 的点走到某个颜色为 $j$ 的点的最短路。这可以通过以每种颜色为起点 BFS 一遍求出。接着我们枚举 $i$，并试着找到 $j\in[1,i)$ 使得 $dis(i,j)$ 最小。实际上有 $...
LuoguLOJ分析可以发现一个事情：我们把每个值的出现次数看成这个值对应的一根“柱子”的高度，然后把所有柱子向左推倒，那么最少需要修改的数的个数即为 $[1,n]$ 中未被柱子覆盖的数的个数。于是可以直接用线段树维护，区间平移维护平移标记即可。在平移时两侧的柱子可能会进来、出去，需要及时加入和去除掉。代码// ==================================== // ...
LuoguLOJ分析设 $f_i$ 为从 $i$ 点生命值变为 $0$ 点生命值的期望步数，$p_i$ 为生命值 $\geq i$ 时一回合扣掉 $i$ 点生命值的概率，那么有直接高斯消元是 $\mathcal{O}(n^3)$ 的，只能获得 70 分。但是这个矩阵很有性质。我们从上往下消，消到每一行时只会有 $3$ 个位置（包括常数项）有值，也就是只要消三列。最后一行时只会剩下一个数和常数...
LuoguLOJ分析根据拟阵的相关理论可以知道：$A$ 是权值最小的基当且仅当 $\forall u\in A,v\notin A$，只要 $(A\backslash\{u\})\cup\{v\}$ 是基，则 $v_u\leq v_v$；权值最大的基的情况同理。这样子就把原题中最小值、最大值的限制转化成了若干组偏序关系。现在的问题即为 $p=2$ 时的保序回归问题。根据论文中的理论，考虑整体...
四 倍 役 满
LuoguLOJ分析一次移动后会让左边的空位减少若干，右边的空位增加若干，从而可以转化为一个阶梯博弈。不妨把左右反过来，那么就是要算有多少种方案满足编号为偶数的空位的异或和不为 $0$。再转化问题，相当于求 $n-m$ 个物品放进 $m+1$ 个盒子中，使得编号为偶数的盒子中的物品数的异或和不为 $0$ 的方案数。这个不为 $0$ 不好处理，可以容斥一下，变成算为 $0$ 的。那么就是每一位...
全是定义和结论，没有证明