BZOJ 2850 巧克力王国

发布于 2017-07-11  265 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2850

题意:每块巧克力有 x,y 两个甜度参数和一个 h 美味值参数。每个人有 A,B,C 三个评测参数。一块巧克力对某人是可吃的当且仅当 A*X+B*Y<C,求每个人可吃的巧克力美味值之和


发现数据范围感人,考虑 KD-tree 暴力

如果 A=B=1,做法是显然的... 看看在不在当前子树即可,加上 AB 也没区别啦

不过有一点是 AxBy 均可为负,负负得正反而会更新答案,所以 check 的时候需要枚举所有四种情况

GXZ 大爷说可以卡掉 qwq 但是蒟蒻不会正解了

 


一个非常弱的准退役OIER