2017 Multi-University Training Contest 9 总结

被队友带飞,所以没有去做那些不擅长的数据结构题,得以去做其他题目。😁😁省赛加油吧。
 

1004 Dying Light

我的做法是构造一个有向线段 (0,0) (V_x, V_y). 每次穷举射到个镜面,有没有射到交点。找到反射的镜面后将有向线段的两个点做关于反射线段的对称点。公式为 (x - 2A \frac{Ax + By + C}{A ^ 2 + B ^ 2}, y - 2B \frac{Ax + By + C}{A ^ 2 + B ^ 2}). 因为最多反射 88 次,所以可以放心穷举。

 

1005 FFF at Valentine

判断每个点是否可以被其他所有点到达或者被到达。DFS n 次记录达到多少点和被多少个点到达即可。

 

1009 Senior PanⅡ

首先如果 k 是合数则为 0 。
k 大于 \sqrt{{10} ^ {11}} 时显然最多只有 k 一个数。
k 小于 \sqrt{{10} ^ {11}} 时考虑 [1,n] 中筛去小于 k 的质数的和。
f_{i,j}[1,i] 中筛去前 j 个质数的和。
那么有 f_{i,j} = f_{i, j-1} - prime_j * f_{i / prime_j, j-1}.
边界有三种 f_{0, j} = 0, f_{i, 0} = \frac{i(i+1)}{2} 以及 i \not= 0 \  i < prime_jf_{i,j} = 1. 递归即可。

 

完结

发表评论

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