11月做题记录 | zjc's blog

感觉按OJ分类不是很好，直接按时间排算了。

感觉很困难，组合意义果然是我的弱项。

把每个 $\binom{B_i}{A_i}$ 看作是 $\binom{A_i+D_i}{D_i}$。考虑一下组合意义：有 $A_i$ 个黑球，现在要在黑球之间放白球，首尾旁边也可以放的方案数。

那么现在考虑这么一个序列： $A_1$ 个黑球，挡板，$A_2$ 个黑球，挡板，…… $A_n$ 个黑球，挡板。现在可以在这之间放最多 $m-\sum a$ 个白球，求方案数。

枚举一下白球个数，上指标求和即可。

正难则反，二维数点。

不要认为任何一个多限制问题只有容斥原理一种大体思路。考虑DP，$f_{i,j,k}$ 表示填到第i个，最后一个和 $i$ 颜色不同的位置是 $j$，最后一个和 $i,j$ 颜色都不同是 $k$。

限制挂在右端点上，进行转移即可。本题还可以进一步优化到 $O(n^2)$，这是困难的，考虑每一次都是对矩阵进行加一行和删边界，双端队列维护有效值位置即可。

最后双端队列组成的离散图像是单谷的，把删除序列分成两个部分，$[1,k],[k+1,n]$，答案就是前半部分的方案数乘上 $2^{n-k-1}$。分析前半部分的组成，两个单调递降序列的合成，DP计算方案数即可。

DP方程有双射，可以进一步优化成 $O(n)$。

当时应该是优化建图的trick尚未流传，所以这道题被评为了铜牌题。

首先显然是二分答案，考虑check。限制很像是2-sat，考虑图论建模。具体的，设二分的值为 $mid$，如果 $x_i+mid<x_j$ 那么就意味着选了 $x_i$ 就必须选 $y_j$。

这样去建模，然后tarjan跑强联通分量看看 $i$ 和 $i+n$ 是不是在一起，在一起就说明不对。

厉害的结论题。先考虑操作的本质，就是把树上一段路径赋成路径上任意一点的颜色。于是链就只需要看看颜色段数就行了。

看看如果树上有点的度数大于等于3会如何，手摸一下发现儿子颜色可以任意交换，于是不合法的情况只有可能是目标每一层的点的颜色一样且与原色不同。

容易想到DP，但是先考虑一些性质， $\frac{\sum a}{2} \ge S - a_i$，于是考虑状态 $dp_{i,j}$ 表示选了前 $i$ 个政党，内阁有 $j$ 人时最后一支政党是哪个，要是凑不出来的话就是0。

但是注意到一个限制是希望人数尽量多，要是按照原顺序进行DP就会出问题，需要从大到小进行排序。

CQOI2007 涂色的严格加强版，其实本质一样。难点在于区间DP的转移。枚举断点的转移是容易的，但是不够。观察到 $s_l=s_r$ 的时候 $dp_{l,r}=dp_{l,r-1}$。

最后处理不用更改的点一下就行。

平面点对的题可以考虑分治了，这是个新套路，要记住了。

递增序列不好维护就换递降，因为这可以使用类似拆分数DP的方式进行维护，即每次新增一段1，然后给每个数增加一。