C - Minimization
第一次可能有多种选择,我们枚举所有的选择,然后两边贪心取即可。
D - Snuke Numbers
这个就是打表找规律...但规律也不是很好找,这个规律是变换的规律,可能一次加上\(10^i\),也可以加上\(10^{i+1}\),两个判断一下即可。
E - Independence
题意:
给出\(n\)个点\(m\)条无向边,现在对于任意两个点,至多有一条边直接连接。
现在要将这个图划分为两部分,使得两部分都为完全图,问最终每部分最小边数之和为多少。
思路:
- 划分为两部分之后的答案很好计算,假设两边的点分别有\(x,y\)个,那么最终答案就为\(\frac{x\cdot (x-1)}{2}+\frac{y\cdot (y-1)}{2}\)。
- 现在就考虑如何划分。
- 我们取原图的补图,那么最终两个集合中不存在任何一条边即符合条件。
- 进一步地,我们将这个与二分图等价,其实就将问题转化为二分图问题了。
- 首先判断二分图是否存在,若存在,先有若干个连通块,每个连通块有两种选择,那么直接背包\(dp\)一下求出最终所有方案数就行了。
代码如下:F - Eating Symbols Hard
待补。