省流
以为开出 \(5t\) \(winwin\) 了，结果是数据过水惨遭轻松 \(hack\)，打出表现分 \(1898\)。
10.13
内含剧透，请vp后再来。
不是题解！！！！！！！
赛前
最近一周一直掉分，心态已经调理的足够平和了，赛前补了两篇游记就很正常的开始了这一把。对于两个半小时的比赛其实有点担心能不能抗住，毕竟一般我的有效时长也就 \(100min\) 左右。
赛时
先开 A 题，给定一个多重集，要求把这个多重集分成几个 \(mex\) 相等的多重集，问 \(mex\) 最小是多少。一开始凭借着直觉认为答案只有零和一，就只判断了最小值是不是 \(0\) 就匆忙的交了一发挂掉。仔细思考一下，发现 \(mex\) 要求相等所以其实分不分都一样，直接看本身的 \(mex\) 就可以了。
接着看 B 题，题目要求构造一个长度为 \(n\) 的序列，要求第 \(i\) 位的一个函数值为给定的数。函数是从 \(1-i\)，\(2-i\) 直到 \(i-i\) 的这些集合中每个集合中不同数的个数之和。显然是要存一些前面的东西，然而大脑比较混乱，没有很好的想法也不是很想动笔写画，就先跳过看 C。
C 题要求你给出一个数 \(x\)，使 \(x\) 和 \(x\) 的二进制数倒过来，这两个数的异或结果为 \(n\)，如果存在这样的 \(x\) 就输出 \(Yes\)。手玩一下发现要求 \(n\) 是对称的，于是写出测样例发现 \(6\) 不对，于是可以发现往前面填充 \(0\)，然后发现 \(8\) 不对，发现正中间那个数不能是 \(1\)。于是交了一发就过了。
扭头回来看 B，推式子得到当前位置减增长量为同一个数，如果为零就多一个数，按这个模拟就行了。这个时候 \(31min\)，分数不太好，毕竟中间跳了，第一题还吃了罚。
此时 \(Moemi\) 一直在旁边上压力，他写出 D 了说可以下班之类的，非常慌张了。于是接着 D 题，D 题有 \(2n\) 个数，\(1\) 到 \(n\) 各有两个，每次可以询问任意个位置，程序返回给你这些数中出现两个的最大值，要求在 \(3n\) 次询问内给出整个序列。容易想到的是如果我们可以把整个序列分成两个没有重复的部分，那么每次拿一整段，对着另一段的每一个询问一次就能确定另一段的每一个位置都是什么数，于是考虑怎么得出一个没有重复的整段。然后想到我们可以直接一直往后查，每次多查一个数，如果重复了那么新的位置就是这个给出的数，否则加到不重复段中接着询问，这样 \(2n\) 次就可以得到一个不重复串和剩下每个位置。然后再 \(n\) 次询问把不重复串的每个和剩下的全部位置放一起得到的数就是不重复串每个位置的值。
虽然感觉很大可能基本下班了，不过秉持着坚持到最后（虽然最后也没坚持到最后）的思想，坚持看一下 E。E 题给了一个 \(01\) 矩阵，把 \(1\) 为四个角的矩阵内的点填这个矩阵的面积，每个点都取最小值，问最终矩阵每个点的值。\(n * m \leq 250000\)。看到这个数据范围容易想到把 \(n\) 和 \(m\) 拆开，这样较小边最大就是 \(500\)，可以考虑扫描线。假设行数较大列数较小，每行每行遍历，记录每列的两个点间上一次同时出现在第几行，然后把这行有的两列的点与之配对并更新，这样的时间复杂度是 \(O(n^2 * m)\)，但是要考虑怎么更新矩阵内的值。我想能不能暴力更新，然后试了一下感觉可能是最坏情况的全 \(1\) 矩阵，发现复杂度还是这个值，于是大胆猜了一个结论是可以暴力，交上去过了。
F 和 G1 都简单看了一下，但可能是被虚假的胜利冲昏头脑了，F 没太明白，G1 想了一个 \(DP\)，用了单调栈和线段树优化，发现复杂度还是太高，只好放弃了。
赛后
虽然还没打完，但是我一看后面题好像都写不了，就提前写这篇游记了。还想等打完了和别人讨(装)论(x)所以不能提前走人啊！
结果比赛结束被 \(hack\) 了，装 x 失败。
想了一下，如果只有第一行和最后一行全是一，那么就要在 \(n^2\) 个遍历中再去来一个 \(m^2\) 的遍历就挂了。然后看了题解，题解提到了 \(DP\)，于是考虑怎么优化。发现对于一行中记录每一个 \(l\) 到 \(r\) 区间内的最小值，就可以通过固定 \(r\) 增大 \(l\) 和固定 \(l\) 缩小 \(r\) 然后取最小值就可以在 \(O(n^2)\) 的复杂度内解决一行，记录 \(l\) 到 \(r\) 的方法还是用刚刚的，把扫描线到当前行的 \(l\) 到 \(r\) 的值都修改成这个矩阵的大小，这样每行的每个 \(l\) 到 \(r\) 就最多被修改一次，时间复杂度就变成了 \(O(n^2 * m)\)。
2025年10月13日