2015 UESTC Winter Training #10【Northeastern Europe 2009】

2015 UESTC Winter Training #10

Northeastern Europe 2009

 

最近集训都不在状态啊,嘛,上午一直在练车,比赛时也是刚吃过午饭,状态不好也难免,下次比赛提前吃饭休息一会儿吧。。

一开始卡在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

【水】简单地统计即可

 

2015 UESTC Winter Training #10【Northeastern Europe 2009】

上一篇:c# 获取 本周、本月、本季度、本年 的开始时间或结束时间


下一篇:CENTOS7安装JDK1.8.0_261