2015 UESTC Winter Training #10
最近集训都不在状态啊,嘛,上午一直在练车,比赛时也是刚吃过午饭,状态不好也难免,下次比赛提前吃饭休息一会儿吧。。
一开始卡在B题,后来发现是题意理解错了,没有看见above,就是不可以回到原点,WA了5发也是够可惜的。
顺利地过了G题之后,就卡在了C题上,要T成doge了T T。
A - Asteroids
三维凸包,等看计算几何之后再写
B - Business Center
有一座高楼,有无数层,且没有负数层,你现在在第0层,给了m(m<=2000)个电梯,每个电梯只有两个键,一个是向上走u层,一个是向下走d层(u,d<=1000),从一开始选出一个电梯,中途不能换电梯,问按n(n<=1,000,000)次按钮,最低能到第几层(不包括第零层)
一开始想用贪心法去做,但是TLE,后来发现可以通过调整公式来求。
显然分别对每个电梯求最低可达的层数,然后挑出最小的就可以。
那么具体对于一个电梯,一次向上走u层,一次向下走d层,假设有x次向上走,y次向下走,答案ans应满足ans=ux-dy ,变换一下公式ans= ux-d(n-x) = (u+d)x – dn,这样ans只与x取值有关,由ans为最小正整数,所以x可以确定出来,所以答案也可求出来。
C - Database
G - Headshot
【水】简单地统计即可