SRM396

早期srm比较简单
今天无聊颓了一下来做这个……

level 1

傻×暴力题……不如考虑怎么做到以下

level 2

说我们要把图像染黑使得黑色的连通块变成光滑的话……
首先内部不能有空洞……
其次我们把一个图切片……
横着纵着切每一片……同一个联通块的黑色段都要连续……
这样就合法了

level 3

等价从一个数字集合中选它的一个子集S,使得S的所有非空子集,异或和都非0
这题是有多经典啊T_T……

容易发现这个问题可以用一个拟阵描述
那么就可以排序加贪心判定的做法搞了……
为啥一个非空子集非0的集合构成了一个拟阵?
证明比较显然……主要是换出性的问题……
就是说一个元素较少的集合A的子集个数一定少于元素较多的集合B
那么如果B不能取出一个元素b∈B来使得A∪{b}仍合法的话
那么B中的每个元素都能用A的一个子集来表示……
接下来就发现矛盾了……因为B的元素个数比A多……
所以换出性得证

接下来就是 高斯消元 +枚举的事情了……

其实可以写得比较简洁……不需要高斯消元,推荐acrush的代码……

吐槽

其实最近一直在推《弹丸论破2》……
今天才通关……
感觉智商被碾压了……
11037这个数字居然到二代还会出现……

Comments

comments powered by Disqus