省选联考 2021 游记

· · 个人记录

Day 1

看完 T1 发现一定是修改一个前缀和后缀，看上去比较可做，写了一个双指针过完样例就去冲 T2T3 暴力了.

T2 刚开始考虑了一下固定其他第一行、列的数，只修改某个第一行、列的数时对整个矩阵的影响，再将每个位置上数的限制转换成对第一行、列的数的限制。结果推出一堆含三个未知数的不等式，而且有加有减，并没有什么用。

后来发现可以考虑直接对整行整列作调整（奇数加1偶数减1），然后将每个位置上数的限制转换成对调整的次数的限制。但是推出一堆 l\le x_i+x_j\le r 和 l\le x_i-x_j\le r 的限制，推了半天才想到可以将一部分 x 直接取反，转化成差分约束。

T3 写了一个不知道复杂度的做法。写完之后还有差不多一个小时的时间，就回去测试一下 T1。

随便手造一组数据，结果 WA 了。

调过手造数据，发现样例 1 WA 了。

又调到手造数据、样例 1 都过的时候，样例 2 WA 了。

然后进入调样例 2 ，测样例 1 、手造数据，调样例 1 、手造数据，测样例 2 的循环，最后终于都过了。

发现样例 3 WA 了。

还剩 20 分钟，再修改了一些边界条件。终于还剩 5 分钟过样例 3 时，顺手测了一下样例 2 ，然后WA 了。

预计得分 0+70+44=114

实际得分 ?+0+0=?

Day 2

看完题发现一道不会，于是先花近 2 个小时才把 T1 的大常数 O(qlog^2n) 写完，中途还忘了 -Wl,--stack=XXX 的格式，测不满的大样例跑了 5 秒，相当于写了个暴力。

写 T2 暴力的过程中忘了 next_permutation 怎么拼，然后试了一堆像 next_permunation,next_permucation 之类的词，发现编译错误。于是手写了一个大常数 next_permutation，样例 2 差点没卡到 1 秒内。后来用random_shuffle 调到 stl_algo.h ，搜了一下 perm 时才知道 permutation 怎么拼。改完直接快了 n 倍（虽然没什么用）。

T3 没想到第一档可以先预处理所有答案，于是写了两个几乎一样的程序，复杂度不会算但是能过 1000 的大样例。

预计得分 25+60+30=115

实际得分 0+?+?=?+?

为什么会有 0 :d1t2,d1t3,d2t1 写了 UB，函数忘写返回值，直接功亏一篑。考场上没开 O2，没开 -Wall -Wextra，自寻死路。

update on 4.15

那 3 个 UB 好像没有功亏一篑，刚好能成功运行。

听说 d1t1 数据很水，但是还是挂了。

final： 0+80+80+100+60+35=355 比预计得分高。