bnu-faraway/XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Eurasia

Info

Date:2018.10.05

Link

Solutions

A Signal processing

solved by sk


sk’s solution

模拟

B Innovative keyboard

solved by sk


sk’s solution

按长度排序,验证前一个串是不是后一个串的前缀

C Rocket

solved by


’s solution

D Universities

solved by ghc


ghc’s solution

最优策略必然是在有学生申请本学校时开始录取,暴力。

E Sheet music

F Split the sandwich

upsolved by ghc


ghc’s solution

首先用第二个平面的方程减第一个平面,问题转化为求一个竖直平面同时等分两个平面下方的圆柱体积。设所求竖直平面方程为\(x sin \alpha + y cos \alpha + r =0\),根据等分体积可以得到两个关于\(\alpha\)\(r\)的方程,解得\(\alpha = atan2( \frac{ b_2 c_1 - b_1 c _2 }{ a_1 c_2 - a_2 c_1 })\)\(r\)不会解,所幸可以二分。

H Chair quest

solved by sk


sk’s solution

先在正方形区域里二分纵坐标,每次在未知区域里找到有点的第一条横线,y确定后,再二分横坐标,依次找到这个y下的每个点。次数大概是\(2nlogn\)

I Vim

J Acceleration

upsolved by gjy


gjy’s solution

模拟一下即可,注意单位统一,double精度不够,要开long double。

K Unlucky Island

solved by


’s solution

L UTF-8

solved by gjy


gjy’s solution

模拟。

Replay

ghc

gjy

sk