题目链接 https://www.lydsy.com/JudgeOnline/problem.php?id=4221 题解 orz WYC 爆切神仙DP 首先将所有袋鼠按大小排序。考虑从前往后DP, 设\(f[i][j]\)表示前\(i\)个元素形成了\(j\)条链。 然而需要处理“套到不能套为止”的问题，因此再加一维: \(k\)表示目前有多少个元素确定了必须要套后面的袋鼠。 设\(cnt[i

题目链接 https://loj.ac/problem/2731 题解 首先一个很自然的思路是，设\(dp[i][j]\)表示选了前\(i\)列，第\(2\)行第\(i\)列的格子是第\(j\)个被填上的。 还要加个第三维\(0/1\)，表示第\(2\)行第\(i\)列不是/是这一列最后一个被填上的（这决定了它是被上下填上还是被左右填上）。 转移: 若第\(2\)行第\(i\)列是棋子，则所有的

题目链接 https://loj.ac/problem/2733 题解 神仙题…… 首先可以观察到一个结论: 目标块的两块小三明治一定分别是最后和倒数第二个被吃的。 由此我们可以考虑这两块谁先被吃。这样的好处就是，起初我们一个块被吃的依赖条件是某两个块中有一个被吃就行，现在两个块中的某一个已经钦定了比它更晚，另一个就一定要比它早，这样依赖关系就形成了一张图。 那么有一个\(O(n^4)\)的做法

题意 题解 又是一道神仙题…… 显然的做法是大力splay，时间复杂度\(O((N+Q)N\log N)\), 可以卡掉。 正解: 使用十字链表维护矩阵，在周围增加第\(0\)行/列和第\((n+1)\)行/列，设\(li[x][d]\)表示\(x\)这个点在\(d\)这个方向上的下一个元素的编号是什么（一开始给每个元素都编上号）。那么对于一次旋转，子矩形边界上的格子暴力修改，内部相当于把\

题意 题解 神仙结论题。 结论: 一个点集合法当且仅当其凸包上的两种颜色点分别连续。 证明: 必要性显然。 充分性: 考虑对于一个不同色三角形\(ABC\)，不妨设点\(A\)为白点，点\(B,C\)为黑点。若形内无白点，则随便连，显然成立。若形内有白点，则任取一白点\(S\), 对三角形\(SBC,BAS,CAS\)内部的点分别连边（递归构造），最后连接\(SA\). 再考虑一个凸包，设在