2024.7.9

T1

题面

Alice 和 Bob 在玩一个游戏：有一个由正整数组成的集合 \(S\)，两人轮流从中选数，Alice 先手。每次一个人可以从当前集合中选一个数 \(x\)，把 \(x\) 以及 \(x\) 的所有在集合中的因数从集合中删除，注意 x 必须在集合中。当一个人无法选数（也就是集合为空）时这个人就输了。问当一开始集合 \(S\) 为 \(\{x|1\le x\le n\land\varphi(x)\le m\}\) 时，当两个人都采用最优策略时，谁会赢？
\(1\le n\le 100,0\le m\le n\)

题解

考虑如果初始集合为空则后手胜。
如果初始集合非空的话，则 \(1\) 一定在其中。如果先手第一步选除去 \(1\) 之外的某个数能够胜利的话则选这个数，否则就选 \(1\) ，将抉择留给对方，依然能获得胜利。
实际上就只要判断 \(m\) 是不是 \(0\) 即可，复杂度 \(\mathcal O(1)\)。

方法

利用了一个公平组合游戏局面不是先手必胜就是先手必败，那么就可以假设一个局面是先手必胜还是先手必败，思考其决策。

在本题中，发现无论出去 \(1\) 后的局面是先手必胜还是先手必败，都可以通过相应的决策使得初始局面时先手必胜。

T2

题面

有 \(n\times m\) 的 \(0/1\) 矩阵。你每次将会进行这样的操作：等概率 \(\frac 1{2nm}\) 随机选择一个位置 \((x,y)\)，和一个数 \(c\)（\(0\) 或者 \(1\)），然后将在 \((x,y)\) 左上角的所有格子置为 \(c\)。这次操作的代价为 \(x\times y\)。给定初始状态和终止状态，问期望要花费多少代价才能将矩阵从初始状态变为终止状态。

\(1\le n,m\le 5\)

题解

设 \(f_x\) 为假设当前矩阵状态为 \(x\) 时到最终形态的期望代价，可以列出 \(2^{nm}\) 个方程，然后高斯消元解一下方程即可。

下一步考虑如何减少状态，实际上就是看原先的两个状态下在什么情况下是等价的，即一定有相同的答案。

如果一个位置的右下角有位置还没有变成最终的状态，那么他的状态也不考虑，因为一定会在更改那个右下角的位置时被改变。设 \(p_{i,j}\) 表示 \((i,j)\) 的右下角的所有位置是不是都变为了最终的样子且自己没有被改变，即是否可能起作用，容易发现只有可能有 \(n\) 个横纵坐标互补相同的位置为 \(1\)，总共只有 \({n+m\choose n}\) 种状态，于是就可以做了。

方法

• 寻找本质不同、实际状态数

T3

题面

有一个 \(n\times m\) 个的地图，其中有 \(k\) 个点为关键点。现在要从 \(n\times m\) 个点中等概率选取 \(r\) 个点，定义其权值为：螺旋形走法下，这 \(r\) 条路径在前 \(k\) 个经过的点是否为关键点的状态下两两不同的最小的 \(k\)。 求其权值期望。

螺旋形走法如下，起始点要被算上，可以走到地图外面：

\(1\le n,m\le 300,r,k\le \min(300,n\times m)\)

题解

方法

• \(E(X)=\sum_{i=1}P(X\ge i)\)

• 动态维护生成函数的多项式系数

T4

\(n\) 个随机变量，对于第 \(i\) 个随机变量有 \(k_i\) 个取值，取到 \(a_{i,j}\) 的概率为 \(p_{i,j}\)。选择一个随机变量的代价为 \(c_i\) 。最后的权值为这些被选择的随机变量的取值的最大值，请找出一种策略，使得取得权值的期望最大，输出这个期望。注意，在决定是否选择这个随机变量前并不知道具体的取值，在选择后才知道具体的取值。

\(1\le n\le 10^5,1\le k_i\le 100,\sum k_i\le 10^6,1\le a_{i,j}\le 10^9,0\le c_i\le 10^9\)

解法

部分分

可知决策只与当前的选择与最大值有关。

即设 \(dp_{s,j}\) 表示已经选择了 \(s\) 中的随机变量，当前取值最大值为 \(j\) 时期望的最大值答案，每次转移枚举每种可能性，并枚举下一步选择什么随机变量，利用期望的定义得到答案。复杂度 \(2^n(\sum k)^2\)，可以得 \(20\) 分。

部分分二

我们发现，选择一个变量的期望收益如果小于了代价，那么我们永远不会选择则这个变量，反之就会选择，因为是否选择一个变量只与当前最大值有关，即 \(\operatorname E(\max(v_i-v,0))\) 与 \(c_i\) 的大小关系，其中 \(v_i\) 为第 \(i\) 个随机变量的取值，\(v\) 为当前最大值。令 \(\operatorname E(\max(v_i-\sigma_i,0))=c_i\)，可知若 \(v>\sigma_i\) 则一定不会选择，否则一定不选择。

于是可以将随机变量按照其 \(\sigma_i\) 从大到小排序，令 \(dp_{i,j}\) 表示对于前 \(i\) 个随机变量，当前最大值取到 \(j\) 时的概率，不会