2016 Multi-University Training Contest 6 - 8 总结

这三场打的不是很好,所以总结一起写了。
这三场打下来基本就感觉智商被掏空了。第 7 场发挥最差,第 8 场小小的爆发了一下,但还是无济于事。总之我还是过于 Naive 啊,要提高自己的姿势和水平。

 

2016 Multi-University Training Contest 6

题解链接, 一些公式的推导就不在这里写了,可以看题解。
 

1001 A Boring Question

结论题,考察数学基本功。

 

1002 A Simple Chess

转换一下就是马走日字,有些点地方不能走。首先可以求出任意点 (x_0,\ y_0)\ ->\ (x_1,\ y_1) 的方案数目。这个用组合数可以算出,对于取模用 Lucas 定理即可。第二部分就是容斥,这里的容斥非常巧妙。先将所有点按 x y 排序。这样就保证了所有能到打当前点的点都在当前点前面。接着另 f[x] 为从起点到 x 点且不经过其他点的方案数(把终点也看作一个坏点一起考虑。) 这样 f[x] 就等于从起点到 x 点的方案数减去 所有 f[i]\ (i < x) 乘上 从起点到 i 点的方案数。最后就能求出答案。

 

1010 Windows 10

贪心。每次不停地降,降到必须用加号,统计一下答案。然后恢复到上一次,继续从 1 开始往下降。一直做到答案不能被更新。注意休息的次数可以用加号的次数来顶替。

 
 
 

2016 Multi-University Training Contest 7

题解链接
 

1002 Balls and Boxes

结论题,考察概率论。 ps:感觉智商被压制了。

 

1005 Elegant Construction

按需求从小到大排序后构造。因为每次都是从前面选取点,所以连接到一个点带来增益只能是 1 ,他能到达的点在之前也已经被连接了。所以这样构造能保证正确性。记得判断一下无解的情况。

 

1010 Joint Stacks

这题是拿 STL 强行过的,题解的方式要更加的优美。还是感觉到智商被压制了。

 
 
 

2016 Multi-University Training Contest 8

题解链接

 

1001 Ball

这题是全场第六 A 的,所以还有点小激动呢。
做法很讨巧。将 A 中的球按颜色(包括0)按顺序一一对应到 B 中,并记录下位置。之后每处理一个区间,就将这个区间排序。最后判断是不是 1..n 按顺序排列

 

1006 physics

物理水题。首先考虑清楚,既然是完全弹性碰撞,那么就相当于两个物体交换速度,对答案没有任何影响。所以位置和方向都是无关条件。通过速度与加速度的关系积分,得到速度平方式线性增长。做法就是将速度从小到大排序,每次询问就用第 k 小的速度算是 t 时刻的速度。积分的过程也不是太难。

完结

发表评论

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