【7.31】代码源 - 【矩阵操作】【宝箱】【New Stone Game】【等差数列】

#804. 矩阵操作

题意：

题解：(思维) 代码源每日一题 Div1 矩阵操作

思路：首先，判是否有解。如果操作行，那么这一行的差分不变。如果操作列，对应两列的差分变化相同。因此判断每一行的差分是否相同。

如有解，我们不妨先做完所有行操作，再做所有列操作（影响与先后顺序无关）。做完所有行操作后，必然是所有行都相同，且有一行是不会操作的（证明）。那我们 枚举 最终等于哪一行，先把其他行操作与这一行相同，再搞列操作。

证明：如果我们的解是对于每一行都有操作的，那我们把每行进行的操作转化为每列进行的操作（影响是相同的），那么一定可以构造出一组新的解，且存在一行没有行操作。

AC代码：http://oj.daimayuan.top/submission/311931

---

#806. 宝箱

题意：$X$ 坐标轴上有 $N(1\le N\le 10^5)$ 个钥匙和 $N$ 个宝箱, 玩家初始位置为 $x=0$ , 每一步可以走到 $x+1$ 或者 $x-1$ .

同一个位置可以同时出现宝箱和钥匙, 但同一位置不会出现超过一个宝箱或超过一个钥匙.

当玩家到达一个有钥匙的位置时, 他可以将钥匙捡起. 当玩家到达一个有宝箱的位置时, 他可以选择使用一个钥匙将宝箱打开.

试求出玩家最少需要走多少步才能打开所有宝箱.

题解：代码源每日一题-宝箱（贪心/思维）

思路：贪心 / DP。容易知道，我们的路线一定是：向右走，拿到若干钥匙，回头开若干宝箱。重复上述若干次，然后径直走到最后，再回头停留在某宝箱处。

我们可以枚举最终落脚点，那么次数就是 $2\times \max (a_n,b_n)-a_i+s_{i-1}$ ，其中 $s_i$ 表示回头开启前 $i$ 个宝箱要多走的路。我们要递推出来这个 $s_i$ 。

$s_i=s_{i-1}+dt$ 。
当 $a_i\ge b_i$ 时，不需要回头， $dt=0$ 。
当 $a_i<b_i$ 时，我们有两种选择。1. 开完前 $i-1$ 个宝箱，然后拿 $i$ 钥匙回去开 $i$ 宝箱。 2. 拿到 $i-1$ 钥匙后顺带 $i$ 钥匙，回去开 $i,i-1\cdots$ 宝箱。

我写的时候没有考虑到顺带的情况。还是要把所有情况考虑上。

AC代码：http://oj.daimayuan.top/submission/312073

---

#854. New Stone Game

题意：在3*3的格子上玩Nim游戏，特殊的地方是先后手第一次必须全部拿完。存在空行或者空列则无法操作，输。问先手初手有多少种选择是必胜态。

题解：(Nim游戏)代码源每日一题 Div1 New Stone Game

思路：

挖掘性质：

1. 如果一个人操作前，该行或该列上存在 $0$ ，则操作此点为必输态。
2. 最终的必输态一定是一个特殊点为 $0$ ，剩下的点（除特殊点和先后手初手点）为 $1$ 的状态。

那么我们枚举先后手选择哪些格子，转化为 NIM 游戏。

思考普通博弈题时，通常从最终的必输态或必胜态开始研究，向上推结论。 比如这道题最终必输态就如 ∗ , 1 , 1 1 , 0 , 1 1 , 1 , ∗

∗,1,11,0,11,1,∗​ ，然后就是普通的 NIM 了。

AC代码：http://oj.daimayuan.top/submission/313001

---

#843. 等差数列

题意：给定一个大小为 $n(n\le 5000)$ 的集合 { S } \{S\} {S} ， 你可以从中挑选若干个数组成等差数列， 求最长的等差数列长度。

题解：(DP/双指针)代码源每日一题 Div1 等差数列

思路：刚开始写了个 $O(n^2\times \log n)$ 的 DP ，但是会 T 。

我们定义 $dp(i,j)$ 表示后两项为 $a_i,a_j(i<j)$ 的等差数列的最长长度。一个朴素的转移方式是，枚举 $a_k(k<i)$ ，从 $dp(k,i)$ 转移过来，然而这个转移是 $O(n)$ 的，总为 $O(n^3)$

我们考虑怎么优化。我们可以先排一下序（答案与序列顺序无关），这样当我们固定 $i$ ，枚举 $j$ 时， $k$ 也是有单调性的， $j$ 向右则 $k$ 向左。当 $a_k+a_j=2\times a_i$ 时可以进行转移。那么做法就是枚举 $i$ ，$j$ 向右滑动，$k$ 向左滑动，从 $dp(k,i)$ 转移到 $dp(i,j)$ ，时间复杂度平方级别。感觉是一个挺新奇的转移方式。

AC代码：http://oj.daimayuan.top/submission/313331