2016 Multi-University Training Contest 2 总结

又一场多校打下来,虽然比上一场要好看一点,但是依然存在好多的不足。主要问题出在两点:1. 有些智商题建模比较慢,看不出题目要考察的方向,导致漫无目的。2. 对于细节的处理比较糟糕,导致已经想出算法的题目提交次数过多,罚时较高。3. 卡题时的对策不够好,找WA点过慢。
总之,要多打练习赛,多学习大神的程序的写法。
 

1001 Acperience

这道题看成一个 n 维空间,就是求出一个向量到一条直线的最短距离。应为 B 是单位向量,所以与 W 同方向的时候答案最小。所以不如将 W_i 全部取成正数。当 W\ -\ aBaB 垂直的时候距离最短。这样就可以求出 a 来。最后将 (||W||)^2 化简求出答案。中间注意大数的处理。

 

1005 Eureka

这道题首先得得出 best pair 其实就是共线的点集。首先按坐标双关键字排序,接着每次取最左边的点。然后极角排序,将所有的共线的点排到一起。然后通过组合算出答案。注意:1.重点需要单独处理,因为重点和任意一组都贡献。2. 按照 \frac{????(dx,dy)}{gcd(dx,dy)} 排序,这样避免了斜率带来的精度问题,也要不叉积要快,这也是标程出众的地方。

 

1009 It's All In The Mind

运用贪心,a_1,\ a_2 尽量大,后面的数尽量小。不知道为什么,WA 了好几次,重写一遍也就 A 了, T^T 郁闷。

PS

似乎很久没有更新了

End

发表评论

电子邮件地址不会被公开。 必填项已用*标注