2022.3.5模拟赛

黎曼几何

令 $\text i$ 个盘子从 $\text 1 \rightarrow \text2$ 的方案为 $f(i)$ , 另一个为 $g(i)$.

不难发现， 有 $g(i)=2g(i-1)+f(i-1)+2$， $f(i)=2g(i-1)+1$。

快速幂即可，卡常，需要光速幂。

代数几何

经典结论有一个不会都不行。
属于是考到知识盲区了。

• 序列置换后会变成若干互不相交的环。其中还的个数为 $\gcd(n,k)$

• 最优解中，环内的数是一段连续的区间。

• 单个环内最优的一定是从大往小放，先放左再放右，直觉考虑是让大的贴在一起。

模拟即可。

几何考试

做法也比较显然。

只会 $O(n^2)$ 做法，考虑两个相交的线段，其他情况同理。

设相交后有 $\text{a,b,c}$ 三部分，钦定第一个人输。

概率就是 $\frac{a}{a+b} + \frac{b}{a+b}*\frac{b}{b+c}*\frac{1}{2} + \frac{b}{a+b} * \frac{c}{b+c}$

最后总共求和即可。

考虑把线段按左端点排序，分为相交，包含，相离三种情况可以很好处理这种问题。

反思

还是那句话，即使捏着一个正确做法仍然没写出来，还是思路不够清晰。

代码调试再厉害，思路不清晰也没用。

尤其对于 $\text{T3}$ 这种细节题，思考完每一种细节再动手是好的。