CVBB ACM Team

题意和题解:过水已隐藏

题意:三维计算几何，计算射线和球的交点以及反射后的射线方向。

题解:解一元二次方程+模拟即可。

题意:长度为$n$的$01$串，每一位有$p_i$的概率是$1$否则是$0$，求存在一个长度为$k$的连续$1$的子串的概率。$(k \le n \le 100 \, 000)$

题解:考虑反面，不存在一个长度为$k$的连续$1$的子串等价于用数个$0$将原串分为数个长度为$0$到$k-1$的连续$1$子串。我们设$f_{i,j}$为考虑到第$i$位时，这一位是一个长度为$j$的连续$1$子串的结尾的概率，其中$0 \le j < k$。直接求是$O(n^2)$的，观察递推式，有$$ f_{i,j} = \begin{cases} (1-p) \times \sum_{x=0}^{k-1}{f_{i-1,x}}, &j=0 \\ p \times f_{i-1,j}, &j>0 \\ \end{cases} $$相当于，每次$i$增加$1$，第一项变为所有值的和的$1-p$倍，第二项到最后一项变为前面一项的$p$倍，这样我们利用一个双端队列就可以$O(n)$解决了。最后答案为$1-\sum_{x=0}^{k-1}{f_{n,x}$