标签：lfloor 10 26 right rfloor 2023 left True mathrm

最近需要刷一点博弈论的题目

LG-1288

\(\Rightarrow\)题目链接

可以想到，如果可操作序列的长度是奇数，那么先手必胜，如果是偶数，那么先手必败。

LG-1290

\(\Rightarrow\)题目链接

设 \(f(i,j)\) 表示当前较大的石子堆和较小的石子堆的大小分别为 \(i,j\) ，先手者是否存在必胜策略。
可以想到一种转移方程：

\[f(i,j) = ¬\left[f\left(j, i - \left\lfloor\frac{i}{j}\right\rfloor j\right)\vee\bigvee_{k=1}^{\left\lfloor\frac{i}{j} - 1\right\rfloor} f(i-kj,j)\right] \]

这个转移必然超时。这时候有一个性质：对于 \(i \ge 2j\)，都有 \(f(i,j) = \mathrm{True}\) 。
证明：

设 \(k = i - \left\lfloor\frac{i}{j}\right\rfloor j\) 。

• 若 \(f(j, k) = \mathrm{False}\) ，则 \(f(i,j)=\mathrm{True}\)
• 若 \(f(j, k) = \mathrm{True}\) ，那么显然 \(f(k + j, k)=\mathrm{False}\) ，因此 \(f(i, j) = \mathrm{True}\) 。

因此转移方程如下：

\[f(i, j) = \begin{cases} \mathrm{False} &\mathrm{if}~j = 0\\ \mathrm{True} &\mathrm{if}~i \ge 2j\\ f\left(j, i-\left\lfloor\frac{i}{j}\right\rfloor j \right) & \mathrm{otherwise} \end{cases} \]

标签：lfloor,10,26,right,rfloor,2023,left,True,mathrm
From： https://www.cnblogs.com/juruohjr/p/17789359.html