资讯详情

省流

中期艰难挂机，最后勉强四题仅有铜中。

10.21

内含剧透，请vp后再来。

不是题解！！！！！！！

赛前

点外卖没给一次性筷子，飞奔到食堂获取圣遗物然后 \(4min22s\) 速通结块了的兰州拉面。但还是迟到了。

赛时

开始看题的时候，队友已经吃了两发罚时 \(8min\) 通过签到了，此时正在做 C，我就去简单看看榜上其他的题目。
看了一下当时有人通过的题目，感觉都没什么头绪，于是看他们似乎卡住的 C。C 题给了一个长度为 \(n \leq 5000\) 的序列和一个 \(d\)，要求选择一个区间 \((l,r)\)，使 \(r - l \leq d\)。然后把所有小于 \(l\) 的数变成 \(l\)，大于 \(r\) 的数变成 \(r\)，求变化后最大的 \(\sum_{i}^{n-1}\mathrm{abs}(a[i]-a[i-1])\)。简和我说他们已经发现了区间长度肯定取到 \(d\)，然后我获得一个直觉，只有序列中的点需要作为区间上的点，因为每次区间包括不同的数都只会在遇到一个值时才会变。我讲了只后他们觉得很对，叶神直接上机开码。途中我说了一声保险起见要加一个加减一处的判断，不过叶神应该是自己有正确的想法，没听，结果挂了，超时。我们怀疑是 python 的锅，于是让他 c++ 重新写，结果 wa on \(5\)。我说你试一下加上加减一，结果交上去 wa on \(1\)，我看了一眼发现是遍历时多遍历一个超出了范围，改了之后 wa on \(12\)。于是我上机把他的 \(ans\) 赋初始值，然后增加了加减 \(d\) 的情况，终于过了。
然后我看 L，我简单看了一下关键词发现大概率是模拟，但数据范围不像。结果一直在思考怎么搞，最后发现一个条件没看到，看到后就是模拟。于是转述给叶神，叶神上机开码。
然后我去和简一起看 F，是一道构造题。给一个 \(n * m\) 的 \(01\) 矩阵，对于其中的某个子矩阵，如果全部数都相同则为纯矩阵，否则为混矩阵。要求构造一个矩阵使所有子矩阵中纯矩阵与混矩阵数量相等。我来的时候简告诉我算出总矩阵个数是 \(\frac{n \times (n + 1) \times m \times (m+1)}{4}\)。然后我想到单独考虑每一列，如果第二列和第一列完全相反，那么第二列就不会影响第一列的纯矩阵的个数。这样就可以在确定每一列应该有的纯矩阵个数之后构造出一整个矩阵。然后简指出每列如果这样要考虑除以 \(m\) 后多出来的 \(m+1\)，于是他想到只要每一列和第一列相同就行了，最后就会多一层 \(m + 1\)。至于不可能构造的情况就是当一开始总矩阵个数是奇数的时候。
然后叶的 L 挂了，我找了一会发现是他数组越界了，修改后 TLE。此时简上机码很快过了 F，我优化常数，没过 CF 的，但交到 QOJ 上通过了，此时剩半个小时，A 题显然很麻烦，我们就结束了。

赛后

L TLE 的原因我认为是叶神实现 dfs 的时候每次都传入了完整的数组，实际上数组是可以存在全局的，这样常数会好很多。而且我们也打算以后都挂 O3 优化交题。
C 题挂掉的原因是叶神只写了 \(l\) 作为 \(a[i]\) 的情况，而我一开始想的是 \(a[i]\) 作为每个 \(l\) 和 \(r\)，而我查的时候忘记了，后来乱凑的时候 \(l = a[i] + d\) 就等于了缺少的情况，于是通过了。
这把感觉最主要问题还是我长期挂机，L 题应该更早的给出结论只用暴力 dfs，而我花了太多时间去证明状态的数量，应该大胆去做。这几场沈阳感觉都是要大胆猜测小心求证的场次，感觉风格比较明显。其实我也不是特别擅长这种很数学的场次，希望能有个好结果吧。

2025年9月24日