RSS
 

Posts Tagged ‘Inequalities’

SRM 459

20 一月

一觉起来到公司做SRM,总感觉没有亲临现场做的时候那么紧张激动了,脑子不会那么迟钝,当然也缺少了些许的灵感。这次的1000又是图论,神奇的没有人过,于是继续果断放弃,要允许自己菜,嗯。

1.  250P Inequalities

 给出N<=50个诸如”X op Number”的式子,其中op包括大于,大于等于,等于,小于,小于等于五种,而Number是0-1000的整数。问这些式子最多同时能满足几个。

这题想复杂了,对于250,我还是会先相当枚举的,但是我居然觉得得枚举区间,那就是1000^2了,再乘个50怕是吃不消。于是又想了下,其实每个等/不等式就是一个区间,所以题目问的就是被这些区间覆盖次数最多的点。这个是个挺经典的问题了,具体就是每个区间的开始和结束放到同一个数组里,然后按照坐标排序,接着扫描一遍加加减减就可以了。当然这里区间的转化要利用到数字是0-1000的这个条件,对于大于小于的不等式,下限和上线分别取负数和10000就可以了。同时为了方便处理小于和大于号,直接把所有的数乘以2即可~

Read the rest of this entry »

 
14 Comments

Posted by Hang Hang in 算法 690次浏览

 
 
FireStats icon 由FireStats提供支持