2022NOIP A层联测20

T4 猜数游戏

感觉有点阴间。有人能告诉我大家都贺的哪篇吗，我看大家的代码真的没看懂，最后还是结合讲题视频贺的xzm的代码。

首先第一步题意转换我就没想到，就是如何记录当前的状态。我们的状态不可以只和某一个特定的 $y$ 有关，因为此时先手不知道真正的 $y$ 是什么，也就是说此时对于所有的 $y$ 来说他的决策应当是一致的。

从而我们需要考虑对所有可能的 $y$ 一起去记录状态。先考虑不可以撒谎的情况，我们可以记录一个数组，表示每个数现在有没有可能成为答案，这样相当于每一次我们选择一个 $x$，要不就是把 $\ge x$ 的所有数置为 $0$（相当于回答 $y$ 不大于等于 $x$），要不就是把 $<x$ 的所有数都置为 $0$（相当于回答 $y$ 大于等于 $x$），最后当消到只有一个正数时，先手就知道答案一定是这个正数了。

而我们回到可以撒谎上，发现其实相当于每一个 $x$ 只有被覆盖到至少两次后才能确定 $y$ 确实不等于 $x$，那么我们维护一个初始全是 $2$ 的数组，每次让一边全部减去 $1$，最后当仅剩一个正数时先手就能确定 $y$ 是哪个数了。

当我们发现这件事的时候，我们就可以直接暴力将这个数组作为状态 DP，拿到 $n\le 8$ 的部分分。（实际上手模下也可以拿到）

我们考虑压缩这个状态。我们每一次将一边全部减去一个数，发现这东西只有几种情况：

  1. 一堆 $1$，一堆 $2$，一堆 $1$
  2. 一堆 $1$，一堆 $0$，一堆 $1$

如果是第二种情况，显然先手可以直接二分得到答案，也就是次数为 $\lceil\log a\rceil$（$a$ 为非 $0$ 的个数）。

于是我们考虑第一种情况，我们只需要记录这三段数的长度即可，把一个状态记作一个三元组 $(x,y,z)$，于是我们得到了一个状态为 $O(n^3)$ 的算法。

状态数很大，但是我们发现值域是 $\Theta(\log n)$ 级别的，而且发现关于任意一维这个 DP 都是单调的（某一端如果比之前长那答案肯定要更大一些），于是乎我们可以直接把 DP 的第三维与值互换一下，这样状态就变成 $O(n^2 \log n)$ 的了。

具体的，我们设 $D(i, x, y)$ 为至多操作 $i$ 次后，能够将 $(x,y,z)$ 消至只剩一个正数的最大的 $z$。为了方便推导，我们可以记命题 $P(i,x,y,z)$ 为至多操作 $i$ 次后，是否能够将 $(x,y,z)$ 消至只剩一个正数。

那么我们可以得到 $P(i,x,y,z) = [D(i,x,y) \ge z]$，$D(i,x,y) = \max_{P(i,x,y,z)}z$。

同时，我们如果把第一段 $1$ 和最后一段 $1$ 交换顺序，答案应该是不变的，所以 $P(i,x,y,z) = P(i,z,y,x)$。

那么我们可以考虑先手每次都选到哪个数上：

  1. 选到第一段 $1$ 上

    设我们选择了第一段 $1$ 的右数第 $j$ 个数，那么我们考虑后手，如果后手向左消，就会将左面的 $x-j$ 个 $1$ 消掉，变成 $(j,y,z)$；向右消，就会变成第一种情况，也就是答案为 $\lceil\log(x-j+y)\rceil$。也就是： \(\begin{aligned} P(i,x,y,z) &= P(i-1, j, y, z) \text{ and } [\lceil\log(x-j+y)\rceil \le i - 1]\\ &= [D(i-1, z, y) \ge j] \text{ and } [x-j+y \le 2^{i - 1}]\\ \end{aligned}\) 为了满足第二个条件，我们肯定会让 $j$ 尽可能大，且 $j$ 的最大值为 $D(i-1,z,y)$（由于第一个限制），于是： \(\begin{aligned} P(i,x,y,z) &= [D(i-1, z, y) \ge j] \text{ and } [x-j+y \le 2^{i - 1}]\\ &= [x-D(i-1,z,y) + y \le 2^{i-1}]\\ &= [D(i-1,z,y)\ge x+y-2^{i-1}]\\ &= P(i-1,z,y,x+y-2^{i-1})\\ &= P(i - 1, x + y - 2^{i-1}, y, z)\\ [D(i,x,y) \ge z] &= [D(i - 1, x + y - 2^{i - 1}, y) \ge z]\\ D(i,x,y) &= D(i - 1, x + y - 2^{i - 1}, y) \end{aligned}\)

  2. 选到第二段 $1$ 上

    类似的，我们设选到了第二段 $1$ 的第 $j$ 个数，同样有： \(\begin{aligned} P(i,x,y,z) &= P(i-1, x, y, j) \text{ and } [\lceil\log(y+z-j)\rceil \le i - 1]\\ &= [D(i-1, x, y) \ge j] \text{ and } [y+z-j \le 2^{i - 1}]\\ &= [y+z-D(i-1, x, y) \le 2^{i - 1}]\\ [D(i, x, y) \ge z]&= [2^{i-1} - y + D(i - 1, x, y) \ge z]\\ D(i, x, y) &= 2^{i-1} - y + D(i - 1, x, y) \end{aligned}\)

  3. 选到中间的 $2$ 上

    我们设选到了 $2$ 中的第 $j$ 个数，有： \(\begin{aligned} P(i,x,y,z) &= P(i-1, j, y-j, z) \text{ and } P(i - 1, x, j, y - j)\\ &= [D(i-1,j,y-j) \ge z] \text{ and } [D(i - 1, y - j, j) \ge x]\\ D(i, x, y) &= \max_{D(i - 1, y - j, j) \ge x} D(i-1,j,y-j) \end{aligned}\) 我们发现，$D(i-1,j,y - j)$ 随着 $j$ 增加而增加（总数相等，$2$ 的数量越少，本身花费次数就要更少，那右面那段 $1$ 就可以更长），于是我们可以预处理出来一个数组 $f(x, y)=\max_{D(i - 1, y - j, j) \ge x} j$，那么： \(D(i, x, y) = D(i-1,f(x, y),y-f(x, y))\) 维护 $f(x, y)$ 也是比较容易的，我们可以先设 $f’(D(i - 1, y - j, j), y) = j$，然后对这个数组关于第一维做后缀最大值就得到了 $f(x, y)$。

以上三种情况的值取 $\max$ 即可，于是就做完了。

2022NOIP A层联测21

T4 方格计数

其实还挺好的容斥？

容斥强制哪个位置选很显然，然后容斥对角线是否不选，几行几列不选都比较显然，主要是考虑怎么计算方案数。

发现对角线这东西很难搞，但是我们发现对角线的点其实很少，那么如果把强制不选的行列刨去，剩下的方格里面强制不选的格子是 $O(n)$ 级别的。那么我们只需要记录一下删去了 $x$ 行 $y$ 列，并且除了这几行几列外还删去了 $c$ 个格子的方案数，然后就能轻松用组合数计算出方案数了。

注意到每一行/列都与对角线只有一个交点，而实际上对角线上每四个点与交于这四点的四条直线是独立的，于是我们可以直接枚举这四个交点，像剥洋葱一样从最内圈到最外圈一圈一圈枚举，然后再决策所在的这四条直线是否强制不选，做下背包，这样就能记录出选几行几列且选了几个对角线上的格子的方案数了，再组合数统计答案就行了。

感觉主要难想的就是容斥之后如何统计方案数，比较难想到可以将对角线和行列同时进行统计方案数。