0103abc 的网站

简单签到题，考虑建图。 首先有一个 $O(nk)$ 个点的建图方式是直接拆 $k$ 层然后层和层之间连边，但是肯定过不去。考虑优化，发现两个点同层之间的连边大多都是无效的，只有两个点这一层上都有路才连边，如果只有一个点在这一层上有边那么把这...

这题真的有黑吗？？？？？？？？？？？？？ 贪心或者 dp 都是困难的，因此考虑一些奇奇怪怪的建图。考虑到一个拼图的作用其实是连接左右两个拼图，然后发现中间部分的作用是连接左侧和右侧两个部分，因此左侧和右侧也可以单独考虑，也就是说让一个拼图的...

题目就是说让你用 $1\sim k$ 填一个 $n\times m$ 的表格，要求表格任意两行不同且每一行单调不递减，求方案数。发现行与行之间互相独立，因此考虑分开统计，计算出有多少种可以选择的行填法，设这个值为 $x$ 那么答案显然就是 $A_x^n$，此时问题变为有多少个长度为 $m$ 元素在...

manacher 算法通常用来在 $O(n)$ 时间复杂度内求解字符串最长回文子串 / 以串内一点为中心的最长回文半径问题。 一些前置定义： 回文串：定义一个长度为 $n$ 下标从 $1$ 开始的字符串 $s$ 是回文的，当且仅当 $\forall...

一个按值插入 dp 的做法，感觉更好想到。 把 $1\sim n$ 中的元素从大到小依次插入到 dp 中。设 $fi$ 表示当前数组中有 $n-i+1\sim n$ 的值，局部最大值的期望是多少。那么显然有初始值 $f1=1$。设当前要转移 $fi$，那么考虑 $n-i+1$ 这个值插入到由...

我切 $3100$，真的假的？ 容易观察到若不考虑 $\exists i,di\neq 0$ 的限制，那么 $\forall i\in[1,n]$ 都给 $di\leftarrow 0$ 就是一组合法的构造。因此图不连通其实就是个幌子，若有一个连通块可以构造出合法解，那么其他连通块全填 $0$...

显然是 dp 题。 先考虑 $O(n^2)$ 的暴力解法。枚举当前出发点为 $x$，设 $fi$ 表示 $i$ 子树内所有点走到 $x$ 结点的期望步数的和。直接转移是困难的，因此套路的考虑列辅助 dp：设 $gi$ 表示当前出发点为 $x$，从 $i$...

糖丸啦。~~是谁在比赛中获得了 30 分的好成绩来着？~~ 首先套路的对图做强连通缩点，得到一个 dag 森林。 考虑什么样的点可以满足题目中给出的那个条件。首先如果 dag 森林在无向环境下不连通那么肯定不可能满足，否则考虑对 dag 森林做拓扑排序，那么 $x$ 点满足条件的充要条件是： $x$...

这题很厉害啊。首先根据题意有 $O(n^2)$ 的简单 dp：设 $f_i$ 表示当前只考虑第 $i$ 个骨牌，把 $1\sim i$ 的骨牌都推倒的代价。那么要么 $i$ 被向左推倒（很显然向右推倒在当前子状态下一定不会更优），要么被前面的某个 $j$ 所推倒。 容易在线性的时间复杂度内处理出...

upd：我觉得我题解格式没问题的啊（ 请务必注意 本题解中下标从 $0$ 开始。 首先 $n$ 很小的情况会有一叠的 conner case 让人头疼，因此这个时候~~直接暴搜即可。~~ 有个更简单的做法是直接特殊情况全都判掉（搜太难写的/kk）。 当所有字符均为 $0$ 时： 很显然无解。...