[广义后缀自动机+DP+单调队列]洛谷4022(CTSC2012)【熟悉的文章】题解
题目概述Luogu4022解题报告不难想到二分答案 $mid$ ，然后求 $L\ge mid$ 是否可行。令 $K={\lfloor{len\over 10}\rfloor}$ ，那么舍弃的位置...
[DP+分治NTT]HDU5322【Hope】题解
题目概述HDU5322解题报告考虑连通块是什么样的，对于 $n$ 的排列，$n$ 所在位置之前的点肯定都是 $n$ 连通块中的，并且 $n$ 没有往后的边。然后对于 $n$ 右边的数列也可以递归...
[长链剖分+DP]BZOJ4543【[POI2014]Hotel加强版】题解
题目概述给出一棵树，求多少个 $(a,b,c),a<b<c$ 满足三个点两两距离相同。解题报告考虑以这三个点的LCA $x$ 统计答案，则只有两种情况：在 $x$ 不同儿子 $u,v...
[DP+复杂度分析]2022“杭电杯”中国大学生算法设计超级联赛（7）【Counting Good Arrays】题解
题目概述HDU7217解题报告一个显然的想法：定义 $f_{i,j}$ 表示放了 $i$ 位，第 $i$ 位为 $j$ 的方案数，那么：$$
f_{i,j}=\sum_{d|j}f_{i-1,d...
[容斥+DP+多项式求逆]2022“杭电杯”中国大学生算法设计超级联赛（1）1010【Walk】题解
题目概述HDU7147解题报告从来没做过这种容斥，长见识了😭。定义 $f_i$ 表示走了 $i$ 行都合法的权值和，以及 $g_i$ 表示走了 $i$ 行全非法的权值和（特殊的，如果 $i=1$...
[仙人掌DP]BZOJ4316【小C的独立集】题解
题目概述图论小王子小C经常虐菜，特别是在图论方面，经常把小D虐得很惨很惨。这不，小C让小D去求一个无向图的最大独立集，通俗地讲就是：在无向图中选出若干个点，这些点互相没有边连接，并使取出的点尽量...
[贪心+DP]Codeforces GYM103049A【Atomic Energy】题解
题目概述CF GYM103049A解题报告物品体积小，背包容量大的题，我们可以采用大范围贪心，小范围DP的办法。
[思维+DP]XXI Opencup GP of Tokyo B【Bit Operation】题解
题目概述CF GYM 102978B解题报告不难发现 $0$ 和 $1$ 执行and和or操作时，相当于把其中一个元素删掉了。而 $00$ 之间或者 $11$ 之间执行and和or操作时，也可以...
[DP]Codeforces1499E【Chaotic Merge】题解
题目概述CF1499E解题报告这道题想法不难，但是实现的时候很注重细节。首先我们考虑DP $f_{i,j,0/1}$ 表示第一个字符串取到了 $i$ ，第二个字符串取到了 $j$ ，且最后一个取...
[线段树维护DP]Codeforces1479B【Painting the Array】题解
题目概述CF1479B1 & CF1479B2解题报告在本算法下，B1和B2其实没有很大区别，所以下面仅讨论最小值。定义 $f_{i,0/1,x}$ 表示 $i$ 放了 $0/1$ 颜色，并且另...
