山河重整
$O(n^2)$ 的算法容易得出,考虑优化,一个常用技巧是考虑整数分拆,
首先计数不合法方案来容斥,容易知道整数的互异拆分是 $\sqrt{n}$ 级的,
这就相当于有 $\sqrt{n}$ 个物品的完全背包,
最后分治计算就可以了,具体过程
机器人游戏
$bitset$优化题,发现$n$很小,考虑容斥,算法很容易设计。
我们发现有且仅有 $c_i >= n-r$ 的爆炸了,所以并不是所有元素都需要记录下来的。
最后 $bitset$优化 即可。
Student’s Camp
本题「不连通」只可能是被「上下劈开」,不可能是被「左右劈开」。
状态很容易设计,将转移方程展开后前缀和优化即可。
Prefix Suffix Addition
首先考虑只有一种操作时该怎么解决,容易发现我们可以把整个序列看成若干个极长不下降子段,
并且最优情况下一次操作一定不能消去两个不同的不下降子段。
因此只有一个操作的时候就等于整个序列的不下降子段个数。
显然对于另外一个操作也是成立的。这里出现了分开处理的动机。
如果我们可以让它们的操作区间两两不交就好了,事实上确实可以。
本题到这里就很好解决了,具体过程
Negative Cycle
好题,不难想到二维前缀和优化,正反向处理一下二维前缀和,就可以解决了。
Chords
圆上相交等于序列上相交但不包含,分类讨论后用容斥就可以解决了。
Checkers
首先我们将它的决策图画出来,形式是一棵树,考虑子节点对根的贡献在哪些地方,
暴力$DP$即可,
Turtle
切入点在两层,简单构造一下就好了,
不难发现起点和终点必然用的是最小值,剩下的按照结论$DP$就可以了。
记得路径回溯输出具体方案。
Bears and Juice
挺新颖的题,从「信息」的角度考虑即可,
Square Constraints
挺套路的题,先将排列转高维,然后从没有下限的情况考虑,
然后 $DP$ 求下限的贡献就可以了。