[省选联考 2021] 解题报告

标签：dots 省选 矩阵 做题 2021 2n 联考

这两天（2023-3-12/13）开了一场省选 VP，感触比较大，同时也有颇多要总结的地方，因此写下这篇博客。
省选 \(-20\) 多天，我还在补一些没有仔细学的新算法，虽然感觉新学了很多东西，但是感觉在实战中并没有用到什么，所以感觉自己学得并没有很大意义。最近的做题计划比较混乱，基本上是想到什么做什么，再有就是跟着群友的刷题记录，但是自己的做题步骤一般为：开题 \(\to\) 思考 \(\to\) 两分钟没有任何思路 \(\to\) 看题解 \(\to\) 发现做法不难 \(\to\) 开贺。感觉对自己的分析与思考能力没有提升。
趁着周末来了一次 VP，感觉还是要考试性质的做题对自己的实力有一定帮助。
以上均为个人想法。

Day 1

卡牌游戏

不考虑正反面，求一个长度为 \(2n\) 的数列删掉至多 \(m\) 个数的极差是平凡的，显然从两端删起，枚举分别在两边删掉的数的个数。
现在考虑加入限制，那么可以转换为牌有两种颜色，其中一种颜色最多被删去 \(m\) 张，且同一编号的牌不能全部删除，问极差。
思考方式仍然相同，我们将 \(2n\) 个数打上正反面和编号标记，按照值的大小进行排序。
我们维护一个双指针 \(l,r\) 表示我们已经删除了 \([1,l],[r,2n]\) 中的所有数。
假设我们先让 \(l\) 走到最大的位置。那么现在 \(l\) 往回走的时候，\(r\) 就可以移动更新答案。
这题有一定的思维难度，主要是想到通过打标记的方式让所有的数变成一个序列再操作会简单很多。
代码不难，有一定细节。

---

矩阵游戏

2021年真的很喜欢游戏。
有一堆限制的矩阵并不好直接构造，赛时我本来的想法是四个相邻的数中取 \(\min\)，然后用四周的格子填补。这个想法显然是有问题的，因此考虑换一个方式构造。
采用调整法，不考虑限制，先构造出一个符合条件的矩阵，去掉限制后答案非常简单：

\[ a_{i,j} = b_{i,j} - a_{i,j+1} - a_{i + 1,j} - a_{i+1,j+1} \]

规定 \(a_{n,i} = a_{i,n} = 0\) 即可倒序推出。
满足条件的矩阵有一个很好的性质：如果一个矩阵 \(A\) 满足条件，那么

\[\begin{bmatrix} a_{i,j}+k & a_{i,j+1}-k & a_{i,j+2}+k & \dots & \\ a_{i+1,j}+k & a_{i+1,j+1}-k & \dots & \\ a_{i+2,j}+k & \dots & \\ \dots & \end{bmatrix} \]

标签：dots,省选,矩阵,做题,2021,2n,联考
From： https://www.cnblogs.com/misterrabbit/p/17207793.html