Codeforces Round #222 (Div. 1)

被虐得神志不清……

这次的题目……难度感觉……比之前的div1的难度稍微大一点……大概是因为代码量大一些?

A

给一个n*m的棋盘,有的格子被染黑,保证白色的格子是四联通的
要我们再染黑k个格子……使得白色的格子仍然四联通……

SOL

对于这种构造性的题目……随便乱搞就可以了……
从一个白色格子开始dfs或bfs……
然后删掉dfs序/bfs序的最后k个节点就可以了……正确性显然……
当然还有别的乱搞方法……

B

有m个bug,n个学生
第i个bug被修复的难度为ai
第i个学生能修复的bugs的难度不能超过bi
我们可以花ci的代价雇佣第i个学生,雇佣了这个学生后,让他修复bug不会产生任何额外代价
一个学生一天最多修复一个bug,一个bug只能被一个学生修复
可以同时雇佣多个学生来修复多个bug
一个修复方案的代价定义为所有雇佣学生的代价之后
我们最多能承受的代价不能超过s
问花费天数最少的修复所有bug的方案
或者输出无解

SOL

直接做不好搞……
答案显然具有二分性质
将学生按能力从小到大排序,bugs按难度从小到大排序……
我们二分天数d
这样子的话,可以发现难度前d大的bugs一定由能力大于等于am的代价最小的学生修复……
难度前2d大的剩下的bugs由能力大于等于am-d的剩下的代价最小的学生修复……
这样就有了一个贪心模型了……
我们二分加贪心
用一个堆来加速贪心就可以了
用priority_queue的话……代码不长……
但是我考试时写的是线段树……太蠢了……

C

有n个物品,第i个的价值为ai,有两个人博弈。
有m次操作机会
操作有两种:
pick:选择剩下的某个物品,操作者得到这个物品的价值,然后这个物品移除剩下的物品的集合
ban:选择剩下的某个物品,操作者啥都得不到,这个物品移除剩下的物品的集合
告诉你第i次操作机会给谁,以及第i次操作的种类
两个人都想最大化自己得到的价值减去对手的价值,问第一个人的得分减去第二个人的得分最大为多少

SOL

n比较大,m很小……
我在比赛时花了好久弄明白题意……论不会打dota的危害……
然后我开始想贪心:每次pick的时候肯定选当前剩下的价值最大的物品……这个肯定是没有错的……
但问题在与ban:每次ban的话……可不一定选剩下的价值最大的物品……
接下来就跪了……更,b的是我没有好好证明贪心的情况下还乱搞了几发交上去……不能更,b……

当时就意识到m这么小……贪心肯定不靠谱……正解应该是某种指数级别暴力……但脑子不清醒……比赛时没有想出来……太蠢了……

总之一个很显然的就是……我们将n排序后……肯定是价值前m大的物品才有可能被ban掉或pick掉……

所有前n-m小的物品是没有用的……
因为只有m个物品……接下来就可以直接状压dp了,复杂度O(2^m*m)……就可以过了……
这种题在考场上都没有过真是不能更,了……

D

n个人,每个人都有三个属性,l,v,r,保证l<=v<=r
然后i对j有好感,当切仅当li<=vj<=ri
然后两个人如果互相有好感,就能一起工作
否则不能
我们要选出最多的人让他们两两有好感

SOL

一道挺好的线段树的题……
先按v排序
从小到大枚举最后选出的人中……最大的v是来自谁,设当前为i
然后开个multiset之类的记录j< i,且rj>=vi的所有j,按右端点排序
multiset里的元素很好维护。
对于i,multiset里的所有元素就是能直接和i共存的所有元素
接下来我们想知道,如果最小的v是k的话,那么最多能选多少人,设为fk
我们想知道max(fk)
这就代表以i为最大值时的答案……
考虑怎么维护k……
对于multiset里的元素……我们算贡献……就比较显然了
multiset里的元素j,那么它对lj<=k<=vj的所有fk,有1的贡献……
正确性显然……
接下来就好做了……
我们要支持区间+1,区间-1,区间最值查询……
线段树就好……

自己傻叉wa了好几发……详见代码吧……

E

还没有看……

Comments

comments powered by Disqus