“范式杯”2023牛客暑期多校训练营1

A - Almost Correct

B - Anticomplementary Triangle

C - Carrot Trees

D - Chocolate

题意：两个人在一个矩阵上博弈，每个人每次可以选一个左上角的前缀子矩阵内的所有点，要求当前选择的子矩阵内的点都没有被选择过，没有办法操作的人输，给出矩阵的大小，求胜者

猜结论题，大胆猜测只有当 $n=m=1$ 时先手胜，否则后手胜，成功通过

E - Heap

F - Intersection

G - LCRS Transform

H - Matches

I - Random

J - Roulette

题意：一个人去赌博，每次赌博的规则为输了投原来的两倍，赢了投一元，赌博的倍率为 $2$，求在初始赌资为 $n$ 的情况下能否赚 $m$ 元钱

容易发现以上述策略赌博每次只能赢 $1$ 元，所以只需要求出在 $n \sim n+m-1$ 元时能赢一块钱的概率，乘起来就是最终的概率

考虑初始赌资为 $n$ 元时赢的概率，可以由 $1-$ 输的概率得到，而输的概率为直到超过位置一直输的概率，容易发现为 $\frac 1{2^{\lfloor\log_2i\rfloor}}$，所以可以按位分块求和，复杂度 $O(T\log n)$

K - Subdivision

题意：给出一张图，可以进行 compress 的反操作，求到 $1$ 的最小距离 $\leq K$ 的最大点数

考虑先把最短路树建出来，分树边和非树边讨论。 - 树边：只有一侧是叶子并且叶子在原图上的度数也是 $1$ 的树边才能够加点，并且能加的点数为 $\max(K-\min(dep_u,dep_v)-1,0)$ - 非树边：可以加的点数是 $\max(K-dep_u,0)+\max(K-dep_v,0)$

直接分类讨论即可，复杂度 $O(n)$

L - Three Permutations

题意：给出三个序列 $a,b,c$，定义一次移动为 $\begin{cases}x=a_y\y=b_z\z=c_x\end{cases}$，求从 $(1,1,1)$ 移动到 $(x',y',z')$ 需要的最小步数，$q$ 次询问

按最终答案 $\rm mod\ 3$ 的结果分类讨论，每次先跳一个小步，再跳整个大步，然后就是求排列不动点的板子了。由于是三个序列，所以同余方程也有三个，需要一个小的 exCRT，复杂度 $O(n+q\log n)$，可通过