CF995F Cowmpany Cowmpensation
CodeForcesLuogu分析设 $dp_{i,j}$ 表示以 $i$ 为根的子树，$i$ 的权值为 $j$ 的方案数。容易得到转移前缀和优化即可做到 $\mathcal{O}(D)$ 转移，总时间复杂度 $\mathcal{O}(nD)$。考虑优化。可以发现，$dp_{1,x}$ 为关于 $x$ 的 $n$ 次多项式（可以理解为每个叶子节点都为一次式，往上合并时做乘法从而次数上升）。那...
M_sea 发布的文章
- 首页
- M_sea
CF500F New Year Shopping
CodeforcesLuogu分析一个不要脑子的做法是线段树分治，即以时间为下标将所有物品与询问挂到线段树上，在线段树上递归时维护一个长度为 $4000$ 的 0/1 背包的 DP 数组即可。标解给的是一个奇妙的分块做法，大概是分成 $p$ 块，从每个交界点往左右跑 0/1 背包，然后每个询问一定会包含一个交界点，直接将左右合并即可。代码因为我懒所以只有第一个方法的代码。// =======...
AGC033D Complexity
AtCoderLuogu分析首先能够想到设 $dp_{i,j,k,l}$ 为左上角为 $(i,j)$、右下角为 $(k,l)$ 的矩阵的凌乱度，然而显然是过不去的。注意到答案在 $\log nm$ 级别，因此可以考虑设 $dp_{i,j,k,l}$ 为凌乱度为 $i$ 时，上界为 $j$ 下界为 $k$ 左界为 $l$ 的矩阵右界最远能到哪。根据横切和竖切的情况不难得到转移如果暴力转移总时间...
拉格朗日插值学习笔记
已知 $n$ 次多项式 $P(x)$ 在 $n+1$ 个点的值 $P(x_0),P(x_1),\cdots,P(x_n)$，则
CF938F Erasing Substrings
CodeforcesLuogu分析注意到删除的顺序不影响答案，从而可以得到一个暴力做法：设 $dp_{i,S}$ 表示前 $i$ 位用掉的操作集合为 $S$ 的最小串。这样子是 $\mathcal{O}(n^3\log n)$ 的。考虑一个贪心。显然我们每次选的一定是能选的最小的字符。因此我们只需要求出每个连续删除长度是否合法。假设当前在算答案的第 $i$ 位，考虑求出 $dp_S$ 表示当...
AGC010F Tree Game
AtCoderLuogu分析考虑一个菊花、一开始在中心的情况。显然先手只会往一个 $a_i$ 小的方向走才能胜利，因为双方会在这条边上反复横跳，然后后手先跳完。考虑加上一层。假设一开始在 $u$，$v$ 子树先手必胜，则先手一定不会往 $v$ 走；假设一开始在 $u$，$v$ 子树先手必败，则先手可以往 $v$ 走，且后手一定回到 $u$，故当 $a_u<a_v$ 时先手胜利。因此只需...
AGC035C Skolem XOR Tree
AtCoderLuogu分析可以发现 $(2i)\oplus (2i+1)=1$，因此可以想到大致的构造方法：连 $(1,2i)$、$(1,2i+1)$、$(2i+1+n,2i)$、$(2i+n,2i+1)$。这样子就满足了 $2i$ 和 $2i+1$。然而有一些问题。一个问题是 $1$ 如何处理。可以仿照样例，使 $2$ 和 $3$ 不按上面的方式连边，而是连 $(1,2)$、$(2,3)...
ARC103D Robot Arms
AtCoderLuogu分析首先，如果存在 $i,j$ 满足 $|x_i+y_i|$ 与 $|x_j+y_j|$ 的奇偶性不同，则无解。因为走到 $(x,y)$ 的步数一定与 $|x_i+y_i|$ 的奇偶性相同。先考虑 $|x_i+y_i|$ 全部为奇数的情况。先考虑步长的问题。可以利用二进制进行构造，即令步长为 $2^0,2^1,\cdots$。容易发现最大只需要到 $2^{30}$ 即...
洛谷5641 【CSGRound2】开拓者的卓识
LuoguKarry is God !!!分析考虑 $a_i$ 对 $sum_{k,1,r}$ 的贡献。显然左右独立，因此只考虑计算左边的方案数，即在 $i$ 个位置中放 $k-1$ 个左端点，因而左边的方案数为 $i+k-2\choose k-1$。类似地可以得到右边的方案数为 $r-i+k-1\choose k-1$。从而得到这样子就可以直接 NTT 了。需要注意的是这个组合数是不太能直...