某camp的补题记录

一月末和学弟组队参加了某camp后,被吊打的很惨,感觉自己这几个月已经什么都不会了,于是想了想不管退不退役,总得把题目补完。。。

【#1】I
题意:现在有n个物品,每个物品有a属性和b属性,分别代表作为a的价值和代表作为b的价值。现在最多可以购买A个物品和最多B个物品。一个物品不能同时作为A和B物品,问最大化价值的价值是多少。
数据规模:A+B<=n<=10^5,ai,bi的绝对值均不超过10^5。 考虑贪心,因为负数肯定不选,先把负数处理为0,这样不会对答案造成影响,那么我们就可以保证选满A个和B个。按照ai来从大到小排序,先选好了A个。那么在剩余的部分选B个最大的bi,那么这A+B个物品变作为初始的答案。 现在我们考虑最后一个A物品的位置,一定是在按照ai排序后的序列中的第1个到第A+B个之间。再往后的话我们总可以把最后一个A物品变成之前空余的一个A物品从而让答案更优。那么我们移动这个最后的位置,那么移动一次就可以让B中最小的元素转化为A,同时A中bi-ai最大的物品从A变成B,在这个过程一直取max即可维护出最优答案。

【#2】D 题意:给出一个宽为2长为(x+y)的棋盘,用1*2的灰色x个和白色y个骨牌来覆盖,要求灰色骨牌不能竖直放在棋盘上,问方案数。 数据规模:1<=T<=10^3,x+y<=2000,模数为一个大质数。 这个题比赛的时候没有推出来十分可惜。最后的覆盖情况一定是一些白色的骨牌竖直放,还有两个骨牌横着放这样形成的方块状的东西。我们枚举这x+y列中有多少列是由横着躺的方块占据,那么我们发现这相当于从n-2*i+i个物品中选i个方块,然后在2*i个组成方块的骨牌中选择x个染成黑色就是方案数了。 预处理阶乘的逆元然后暴力求组合数。

发表评论

电子邮件地址不会被公开。 必填项已用*标注