csp202206
T1 归一化处理
题目大意
给定
n
n
n 个浮点数，求
f
(
a
i
)
=
a
i
−
a
‾
D
2
(
a
i
)
f(a_i)=\frac{a_i-\overline{a}}{\sqrt{D^2(a_i)}}
f(ai)=D2(ai)ai−a
解题思路
模拟即可。注意浮点数判断大小的细节。
//instead of
// if (a<b)
//we use:
const double delta=0.0000001;
if (a-b<delta) //...
T2 寻宝！大冒险！
题目大意
给定一个01矩阵，保证矩阵里的1元素很少。给出若干01矩阵碎片，他们的左下角元素都是1，判断这些碎片是否来自这个矩阵。
解题思路
模拟即可。
T3 角色授权
题目大意
定义属于用户组的用户；定义行动类别、行动材料和行动材料类别；定义行动成功，它指的是拥有行动材料、行动材料类别和行动类别的控制权；定义角色、用户是否属于某一角色的依据，以及判断角色是否能行动成功的依据。回答若干询问，判断用户是否能行动成功。数据规模较大。
解题思路
第一步，模拟，得到70分。
时间超限，使用 set 优化即可。
T4 光线追踪
题目大意
仅有格点的平面上有若干与坐标轴成45°角的无端点理想薄平面镜，光线被反射后会衰减。平面处于变化之中。回答若干询问，判断光线在规定时间内传播后的位置和剩余强度。平面、发光时间很大，平面镜长度总和较小。
解题思路
难点在于判断光线是否反射。若每次遍历每面镜子，时间复杂度难以接受。
注意到反射点数目较小。考虑排序所有可能的反射点，每次只需要
O
(
log
L
)
O(\log L)
O(logL) 便可判断是否反射。
注意到反射水平不超过0.8，经计算最大光强的光至多经过30次左右的反射便失去强度。
则时间达标，复杂度为
O
(
30
m
log
L
)
O(30m\log L)
O(30mlogL)。