tarjen edited 1 年，3 月前
A Extra Large Knapsack
当所有数异或起来等于0时，怎么选都是对的，否则无解。
注意特判n=1的情况。
B Bare Minimum Difference
区间和的数量不超过 $n^2$ 个，因此我们可以枚举下界，二分上界，使用滑动窗口或者暴力来实现dp的维护。
复杂度 $O(n^3log(n))$ 或者 $O(n^4log(n))$，都可通过此题。
也可以维护 $dp[下界]=上界$ 的这样子的dp，复杂度同上。
C Kaleidoscope
考虑轮廓线dp，我们可以发现对于点 $(i,j)$ 最远只会从 $(i-1,j-1)$ 转移过来，然后把这个二维的东西压成一个序列，原来 $(i,j)$ 的位置就相当于序列的第 $(i-1)m+j$个数，于是 $(i-1,j-1)$ 离$ (i,j)$ 的距离只有 $m+1$ ，因此我们只需要需要状压前面 $m+1$ 个位置有没有填过东西就行。
复杂度为 $O(nm2^{m+1})$。
或者我们进行逐行状压dp，我们先考虑只有 $1 \times 2$ 方格的情况，我们可以设0为竖着放的上格子，1为竖着放的下格子，同一行内相邻的两个1为横着放的 $1 \times 2$ 。在这个状态设置下，我们可以做出只有 $1 \times 2$ 填充的方案数。
考虑加入 $2 \times 2$ 方格，会发现这就是2个竖着 $1\times 2$并在一起，因此我们只需要在转移的时候，计算一下转移能有多少种方案可以把竖着的$1\times 2$ 拼成 $2 \times 2$即可。
最后，通过打表，我们发现可行的转移数非常少，因此预处理后直接进行转移即可通过此题。
复杂度 $O(nA)$ 其中 $A$ 是一个小于6000的常数。
D Mutton string
首先我们考虑 $f(A,B)$ 怎么求得，显然我们有一个贪心策略，每次选最长的可以选择的子串，得到的次数就是最小的次数。
我们可以对 $A$ 串建出一个SAM，把 $B$ 串在里面跑，跑不出来的时候就从源节点开始跑下一次。
回到本题，我们可以设出 $(SAM上的节点,长度,段数)$ 这样子一个状态，通过bfs转移，bfs得到的第一个串就是字典序最小的串。
最暴力的解法即可通过此题，复杂度 $O(26nmk)$
E Egg to be got
我们首先从$1$号点出发强制优先走向上的点跑一遍$dfs$，再从$1$号点出发强制优先走向右的点跑一遍$dfs$，并在两次$dfs$的过程中记录后续遍历的$dfn$序，可以发现从点$u$可以到达点$v$当且仅当点$u$在两个$dfn$序中都比点$v$的序号大。
证明：
对于这张图我们建出反图，考虑所有互相不可达的点对$(u,v)$，由于$u$和$v$都可以到达$n$点，也即在反图中$n$点可以到达$u$和$v$，那么在反图中一定存在一个点$k$，使得点$k$是可以同时可以到达$u$和$v$的点中最靠左下角的点，从点$k$出发到达$u$和$v$时，一次向左走，一次向下走，使得两个$dfn$序的大小比较结果互逆。
而对于所有互相可达的点对$(u,v)$，同时可以到达$u$和$v$的点中最靠左下角的点就是他们其中一个，两个$dfn$序的大小比较结果必然相同，此时我们便可以得到，从点$u$可以到达点$v$当且仅当点$u$在两个$dfn$序中都比点$v$的序号大。
之后就转化为了一个二维偏序问题，我们按照其中一个$dfn$序将点排序，按排序后的顺序处理每个询问，记录当前出现的每种类型彩蛋对应的另一个$dfn$序最小是多少，对于每次询问，答案即为当前小于它对应的另一个$dfn$序的彩蛋种类数，这个可以用树状数组实现。
复杂度$O(n\log n)$