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}}$。

题意:设$f(i)$是距离$\sqrt{i}$最近的整数，求$\prod_{i=1}^{n}{f(i)} \mod 10^9+7$。$(n \le 10^9)$

题解:可以发现会有连续多个数的$f(i)$都是一个值，因此我们枚举$1.5,2.5,3.5\ldots$，将其平方后向下取整，就可以确定每个整数对应的连续区间，直接快速幂即可。

题意:语文题，状压dp。

题解:摸了。

题意:矩阵从左上角走到右下角，只能往右和往下走，每个格子有个权值，总权值为路径上所有权值的$AND$值，求最大值。

题解:按位贪心，每次限制某一位必须为$1$，如果存在方案，那么将所有不可走的点全部删除，将对应的次幂加入答案并继续下一位即可；如果不存在方案则直接下一位即可。

题意:$n$张地图，每张地图有两种比赛模式，第一种胜率是$p_i$，第二种胜率是$1-q_i$，如果第$i-1$场你赢了，那么第$i$场按照第一种比赛模式进行，否则按照第二种比赛模式进行。每次比赛会选择一个区间按顺序进行比赛，且区间的左端点也就是第一场比赛按照第一种比赛模式进行。$m$次询问某个区间你的胜场期望。$(n, m \le 100\,000)$

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