CVBB ACM Team

水

题意：计算几何射线三维反射问题。

题解：暴力。

题意：一次抽卡为 $SSR$ 的概率为 $p$ ，求 $n$ 次抽卡中存在至少连续 $K$ 个 $SSR$ 的概率。$k\le n\le 10^5$

题解：考虑 $dp$，$dp[i][0]$ 表示到第 $i$ 位且第 $i$ 位没有抽到 $SSR$ 且不存在至少连续 $K$ 个 $SSR$ 的概率，$dp[i][1]$ 表示到第 $i$ 位且第 $i$ 位抽到 $SSR$ 且不存在至少连续 $K$ 个 $SSR$ 的概率。$$\begin{cases}dp[i][0]=(dp[i-1][0]+dp[i-1][1])\times (1-p) \\ dp[i][1]=\sum_{j=\max(0,i-k+1)}^{i-1}dp[j][0]\times p^{i-j}\end{cases}$$ 下面那个式子可以用前缀和解决，然后答案即为 $1-dp[n][0]-dp[n][1]$

考试的时候忘了容斥了，直接把答案算了出来，多花了挺长时间。

题意：$a_i$ 为最接近 $\sqrt{i}$ 的数，求 $\prod_{i=1}^{n}a_i$

题解：有个神奇的规律，$\prod_{i=1}^{n}a_i=1^2\times 2^4\times 3^6\times \cdots \times k^{2k} \times (k+1)^{(n-k-k^2)}$

本质上是个水题但是 $dfs$ 写挂了很久不太应该，最后还是 $dp$ 过的。