kangaroo 题解 dp板子。 首先我们应该是很容易想到将口袋与球分开处理，因为自己的口袋是肯定装不下自己的，所以分开处理也不会有任何偏差。 所以我们很快想到将所有的口袋与球根据大小排序后做dp，保证前面的一定装不下后面的，这样dp也就很好想了。 令 d p i , j , k dp_{i,j,k} dpi,j,k​表示已经处理了前 i i i个，剩下 j j j个口袋永远不会选， k

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

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

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