2016 Multi-University Training Contest 3 总结

这次多校一共出了 5 题,整体上来说是很满意的。因为其中有 4 题是一遍 AC, 没有花太多的时间去纠结。但是这场比赛本可以做的更好。在事后才发现,许多答案推起来可以更加简单,这也是提醒自己数学姿势水平还是要加强的。但愿今天下午这场也能如此轻松。

 

1001 Sqrt Bo

这题题意是求一个 n 在多少次开根下去整之后变为 1。乍一看还需要写高精度开根。但是题目有一个要求:如果不能在 5 次只能变为 1 则输出 TAT, 很容易推算出上界为 2^{32}, 所以读入发现这个数大于 2^32 就直接输出 TAT。注意特判 0.

 

1002 Permutation Bo

简单的概率论题,分开来求出每个位置对答案的贡献。可以算出两边的概率为 \frac{1}{2}, 中间的为 \frac{1}{3}, 特判一下 n\ =\ 1 的情况即可。

 

1010 Rower Bo

这题我开始用了二重积分积出路径,但并没有啥用。后来在数一的提示下才发现轨迹是一个抛物线。不过最后看了题解才不得不感叹自己数学太差了。这题还是直接贴题解吧。 1010题解

 

1011 Teacher Bo

题目要求在 n 个点中选取两对不同的点对,使得他们之间的 manhattan 距离相等。暴力加哈希。一开始以为暴力的复杂度为 O(n^2) ,但后来才发现,因为地图最大为 m*m 的,所以最多只可能有 2*m 种距离,根据抽屉原理,暴力枚举不会超过
2*m+1 次,否则一定会出现一组解。所以暴力加哈希的做法的复杂度其实是 O(min(n^2,\ m)) 的。第一次遇到这种题型,算是学到了。

3 thoughts on “2016 Multi-University Training Contest 3 总结

发表评论

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