抱歉来晚了。

上午状态很差，睡了两个多小时，最后没啥时间了就写了个 T1。

T1 「SDWC2018 Day2」优秀

首先考虑一个单调不降的序列能生成多少“良好序列”，这是个线头 DP，记录缺口数即可。从值域从小到大放，每次要把缺口全填满，每多放一个就多产生一个缺口。

然后就是经典的 DP 套 DP，把生成“良好序列”的方案数也记进状态里即可（超过 \(k\) 的可以不转移或对 \(k+1\) 取 \(\min\)），朴素实现一下复杂度 \(\mathcal O(mn^3k)\)，实际跑起来松松松。

T2 「SDOI2014」向量集

相当于将所有点 \((x,y)\) 变化为 \((zx,wy)\) 后，最右上方能切到直线 \(y=-x+b\) 的点。

答案点一定是在凸包上，建出凸包，凸包上答案是个单峰函数，可以二分。

对于区间询问，考虑二进制分组。往线段树末尾位置插入，某个一个节点的区间恰好填满时归并两个儿子得到该节点的凸包，建树复杂度 \(\mathcal O(n\log n)\)，单次查询 \(\mathcal O(\log^2 n)\)。

T3 「十二省联考 2019」皮配

\(k=0\) 的部分，发现两维独立，分别做背包然后相乘。

\(k\le 30\)，那么没有限制的学校、城市独立做背包，有限制的需要两维都记进状态里。然后合并两者。

复杂度 \(\mathcal O(nM+cM+k^2sM)\)。

完了？？？就是有亿点细节。

实现上的小技巧，有限制的做背包时，为了保证同一城市的阵营相同，可以排序将同城市在放在一起，状态多记录一维 \(0/1\) 表示上一个学校的阵营，同城市的只允许 \(0\to 0,1\to1\) 转移，不同城市随意。

---

问题：

• 时间浪费太多，T2 没时间写；
• T3 被题面唬住了，其实有很多部分分是容易拿的；