2022NOIP A层联测20
T4 猜数游戏
感觉有点阴间。有人能告诉我大家都贺的哪篇吗，我看大家的代码真的没看懂，最后还是结合讲题视频贺的xmz的代码。
首先第一步题意转换我就没想到，就是如何记录当前的状态。我们的状态不可以只和某一个特定的 \(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\)，一堆 \(2\)，一堆 \(1\)
- 一堆 \(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\) 的右数第 \(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} \] -
选到第二段 \(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} \] -
选到中间的 \(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\) 个格子的方案数，然后就能轻松用组合数计算出方案数了。
注意到每一行/列都与对角线只有一个交点，而实际上对角线上每四个点与交于这四点的四条直线是独立的，于是我们可以直接枚举这四个交点，像剥洋葱一样从最内圈到最外圈一圈一圈枚举，然后再决策所在的这四条直线是否强制不选，做下背包，这样就能记录出选几行几列且选了几个对角线上的格子的方案数了，再组合数统计答案就行了。
感觉主要难想的就是容斥之后如何统计方案数，比较难想到可以将对角线和行列同时进行统计方案数。
标签：le,text,赛题,我们,ge,对角线,aligned,杂写,模拟 From： https://www.cnblogs.com/apjifengc/p/16862889.html