传送门

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

    待补。

01-19 18:19