博客详情 - oirush

今天是第一天比赛（天呐学了这么久 whk 我还有手感吗？），由于昨晚过于活跃导致早上比较困。

赛时

$7:30$ 开题， $2 \min$ 秒掉 T1 思路：记录 $dp[i][j]$ 为目前分到 $i$ ，且该块的开头为 $j$ 的最小块数。相应的方案直接开个 $pre$ 回溯到 $j-1$ 就行。

大约 $7:45$ 写完，为什么 RE 了？因为这个红温了 $5$ 分钟，最后发现空间太大了，此时 $7:50$ 。

但是还是没过。找了 $5$ 分钟没有找到哪里有问题。

于是写了个状压暴力，但是在第一档部分分有一些点没过，调了 $2$ 分钟还是没过。此时 $8:05$ 。

不管了直接拍，先找到原代码的问题。找到几个问题，一改直接交，过了，此时 $8:10$ 。

接下来是 T2，想了一会认为将原串化成 $1$ 和 $-1$ ，然后计前缀和，区间里面的最大值和最小值对 $s[l-1]$ 取绝对值的最大值就是答案。

（这个解法已经非常接近 wyh 的最优解了，但是我没有去手推样例导致我没有继续发现）

写完发现没过样例，如上所说我一点办法没有，有点恼（连道青都做不出来？）。

但是我打开 T3 后一眼就想到了思路：注意到把一个点拆成 $8$ 个点，按照他们的方向先在点内建边，然后再按照坐标找到该方向的下一个点再连边，这样会得到一堆环。我们只需要判断两个点能否到同一个环上就行。

理想很丰满，现实很骨感，建图的时候不知道为什么出问题了，还给我来了个负编号的点。

此时我的脑子很乱，去上了个厕所清空一下大脑。T3 不是一时半会能写完和调完的，先回去看 T2。此时 $9:30$ 。

回去 T2 先把暴力打了。然后依旧一点思路没有，于是盯着暴力发呆。

突然，我想起来暴力不是类似 DP 的做法吗？那么我们是不是可以把这个过程变成动态 DP？

这是个好主意，我花了 $5$ 分钟左右去构建矩阵，但是我妄想一个矩阵维护两个值走偏了，不过还是建出来了。

接着就是直接开写了，很幸运这题不带修。

约 $9:55$ 写完，但是没有过样例。不是我记得这玩意不是满足交换律的吗？

期间我测试了矩阵版暴力，没有问题，说明问题不在矩阵上。

突然发现我把一个 && 打成 || 了，严肃气笑。然后又发现运算时矩阵应该全部初始为最小值，这样修改就过了，此时 $10:20$ 。

然后我觉得 $1$ 个小时应该打不完 T3 了，而且 T4 看起来不可做，于是提前结束比赛回位置上休息看题解了。

首先我认为如果今天是 OI 赛制的话我也可以拿这么多分数（因为我的所有错误都是基于样例和对拍检查出来的，不存在什么“没过然后发现自己的问题”）。

对于 T1 我是非常满意的，就比较中规中矩的对拍出来的，拿下了一血。

T2 说实话挺 atc 的，样例给的很全但是我并没有认真分析导致与正解失之交臂；不过令我欣慰的是幸好学了一堆紫算法，动态 DP 和广义矩乘救我一命。

然后 T3 其实有点难以实现（简称 shi），这就导致我在建图时出现了问题（主要是足足 2k 代码也找不出哪里出了问题），但是我其实想到了正解而做不出来这也是本场比赛比较难受的一点。

T4 的话，这里还是不予评价了。

另外我在比赛后期出现了一些消极情绪，这是我放弃 T3 的主要原因，并导致我四处走动等。我觉得这并不是很好，但是一时也不清楚为什么会这样，以及怎么解决。

好了，总结就是这场比赛我有点手忙脚乱，算发挥失常吧。至少 T2 不应该做的这么差。

看看明天的情况吧。