CFR576

CFR576
题号开头为CF1198
我的id是Zory,所以不贴代码了
好题:C、D

A MP3

B Welfare State

直接看我的代码

C Matching vs Independent Set

In particular, if there are both a matching of size n, and an independent set of size n, then you should print exactly one of such matchings or exactly one of such independent sets.

请先思考后再展开

因此,枚举所有的边,每次能选就选,最后剩下来的点集一定是独立集
如果匹配成功了就输出;否则设当前失败的匹配大小为k<n,则独立集大小为 3n-2k>n,也满足条件(所以其实没有impos情况

D Rectangle Painting 1

请先思考后再展开

我的做题思路:
先分析一下,发现肯定只画正方形,而且可以把每个连通区域转化为一个矩形,然后只画一次,正方形可以在某个方向对矩形滑动
假如矩形都是正方形,那么就不会滑动,那么对于某个二维区间,只看大的一维,如果投影到那一维上不是满的,那么就应沿着那条线裂开
可以用类似整体二分的写法,这样子的复杂度极低,然而没法处理滑动

想来想去这个滑动可能还是要靠合适的dp解决,而不是单纯的策略,但就是想不到……
结果正解是直接基于图而不是分析矩形啥之类的……
就是f(l1,l2,r1,r2)然后O(n)枚举分界线转移,常数挺小的

E Rectangle Painting 2

注意这次代价是min而不是max

请先思考后再展开

既然是min,肯定一次选一行或一列,拆成二分图,离散化后最小点覆盖,用网络流实现即可
边数为n方

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/ac11.html
转载请注明出处,谢谢!