一觉起来到公司做SRM,总感觉没有亲临现场做的时候那么紧张激动了,脑子不会那么迟钝,当然也缺少了些许的灵感。这次的1000又是图论,神奇的没有人过,于是继续果断放弃,要允许自己菜,嗯。
1. 250P Inequalities
给出N<=50个诸如”X op Number”的式子,其中op包括大于,大于等于,等于,小于,小于等于五种,而Number是0-1000的整数。问这些式子最多同时能满足几个。
这题想复杂了,对于250,我还是会先相当枚举的,但是我居然觉得得枚举区间,那就是1000^2了,再乘个50怕是吃不消。于是又想了下,其实每个等/不等式就是一个区间,所以题目问的就是被这些区间覆盖次数最多的点。这个是个挺经典的问题了,具体就是每个区间的开始和结束放到同一个数组里,然后按照坐标排序,接着扫描一遍加加减减就可以了。当然这里区间的转化要利用到数字是0-1000的这个条件,对于大于小于的不等式,下限和上线分别取负数和10000就可以了。同时为了方便处理小于和大于号,直接把所有的数乘以2即可~