2015 UESTC Winter Training #10

Northeastern Europe 2009

?

最近集訓(xùn)都不在狀態(tài)啊，嘛，上午一直在練車，比賽時也是剛吃過午飯，狀態(tài)不好也難免，下次比賽提前吃飯休息一會兒吧。。

一開始卡在B題，后來發(fā)現(xiàn)是題意理解錯了，沒有看見above，就是不可以回到原點(diǎn)，WA了5發(fā)也是夠可惜的。

順利地過了G題之后，就卡在了C題上，要T成doge了T T。

?

A -?Asteroids

三維凸包，等看計(jì)算幾何之后再寫

?

B -?Business Center

有一座高樓，有無數(shù)層，且沒有負(fù)數(shù)層，你現(xiàn)在在第0層，給了m（m<=2000）個電梯，每個電梯只有兩個鍵，一個是向上走u層，一個是向下走d層（u,d<=1000），從一開始選出一個電梯，中途不能換電梯，問按n（n<=1,000,000）次按鈕，最低能到第幾層（不包括第零層）

?

一開始想用貪心法去做，但是TLE，后來發(fā)現(xiàn)可以通過調(diào)整公式來求。

顯然分別對每個電梯求最低可達(dá)的層數(shù)，然后挑出最小的就可以。

那么具體對于一個電梯，一次向上走u層，一次向下走d層，假設(shè)有x次向上走，y次向下走，答案ans應(yīng)滿足ans=ux-dy ，變換一下公式ans= ux-d(n-x) = (u+d)x – dn，這樣ans只與x取值有關(guān)，由ans為最小正整數(shù)，所以x可以確定出來，所以答案也可求出來。

?

C -?Database

戳這里跳轉(zhuǎn)

G -?Headshot

【水】簡單地統(tǒng)計(jì)即可

?

轉(zhuǎn)載于:https://www.cnblogs.com/zhyfzy/p/4271743.html

總結(jié)

以上是生活随笔為你收集整理的2015 UESTC Winter Training #10【Northeastern Europe 2009】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。