A,B略

C. Fountains
一开始看错了题,还以为是什么很牛逼的背包题。
认真读了读题目,发现只需要两个喷泉,所以要么两个C、两个D、一个C一个D,用树状数组乱搞搞就行,很简单。

D. Field expansion
题目可以转化为,给一列数字,找不相交两组数字相乘的结果分别大于A和B,使得用到的数字最少。
很容易发现,能用大的数字一定用大的。
因为A和B都不超过\(100000\),所以用不超过\(34\)个数字一定可以找到一组合法解,那么显然就用最大的\(34\)个数字。
然后判断有没有合法解,就拆成两半,然后把所有解生成出来,一半枚举,另一半二分就可以了,蛮常见的处理方式。
要注意这个长方形是可以旋转的…因为没发现可以旋转,错了好多次QAQ

E. Aquarium decoration
把所有的物品分为四份:A和B都喜欢的,A喜欢的,B喜欢的,A和B都不喜欢的。
然后枚举第一部分找多少个,用两个树状数组加速剩下三部分的计算就好了。我的做法是一个树状数组处理前缀个数,然后另一个处理前缀和,到时候二分就可以了。
写错了好多次…码力好差…

发表评论

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