APIO2026

· · 生活·游记

前情提要

在 WC2025 中，题目难度顺序是 T1<T3<T2，在那之前我的做题策略一直是正开，如果当前的题还能做下去就一直做，直到做出来或一段时间没思路才尝试看后面的题。

于是我在这场比赛中打出了 100+100+40，通过了全场只有 4 个人通过的 T2 后获得 Ag。

我尝试拟合做题策略。

做题策略就像一个自动机，你的水平决定了你能拟合出来一个能处理占比多少的比赛的自动机。

比如 zak 的水平就能让他拟合出来一个能处理所有比赛的自动机。

而我的水平显然是不足以拟合出来处理所有比赛的自动机，但是我尝试让自己拟合出来一个能保证大部分比赛不会爆的自动机。

而我经过一年训练拟合出来的自动机，在 APIO2026 中为我得到了能使我得分最低的比赛策略。

比赛

首先开 T1，发现这个题不弱于钦定每个位置是否上升，求方案数。而那个题是需要容斥来做的。

于是对 T1 考虑容斥，大概能感觉出来可能可以实现一个比较复杂的 dp。

于是编了一会会了一个状态 n^2，转移复杂度不确定的 dp。

我的做题经验告诉我，这种 dp 即使转移复杂度较高，很多时候也能优化到 n^3，即使优化不了也有不少暴力分，并且存在卡常过去的风险。

于是开始写这个做法，但是比较难写，写+调完大概 2h 多了。

现在写的这个做法是 n^4 的，并且似乎有机会通过分步转移优化到 n^3，但是这个题上我花费的时间太久了。

我的比赛经验告诉我，我不应该在其他题没看的情况下，一个题做了这么久还接着做，即使这个题有思路（WC2025 就是这么爆的）。毕竟这个优化只是一个可能存在的方向，不一定真的可行。并且一场比赛理应有签到题，我认为这个题的难度一定不是签到题，所以此时我应当先看后面的题，过掉签到题后，有时间了再尝试回来写这个题。

于是看了 T2T3，看到 T2 后，第 4 档可以直接看出来一定是直接三分。

而 T3 大概搜了一层思路，没有看起来进展很多的思路。

于是我认为 T2 应该是这场的签到题，开始做 T2。

然后我发现我不会做 T2。对于这种构造题，确实是有被创的可能性。

但是我拟合出来的做题策略比起去年被创了就直接倒闭，现在应该是可以把一些构造题花更多时间做出来。

1h 不会 T2 最后一档后，先把 T2 前三档写了，然后又光速写完了 T3 的 40pts。

T2 第三档我依然没有秒掉，做完这些之后还剩 1h 多。

此时，在我的视角，T2 的第四档是比 T1 的优化更有前途的，因为我已经在 T2 的第四档有了很多进展。

于是又做了一会，会了 T2，然后写代码，快结束的时候写完了代码，但是只有 89 分。

我确定是某个地方的实现不够精细导致的多了一次，但是剩下时间太少了，在比赛只剩很少时间的时候，为了保险起见，我不敢再动 T2 代码。

于是没事可干，就开始随便想想 T3。

遇到这种题应当先试试线段树能不能直接维护，那就是要合并。

然后转化成求邻域交。

我见过树上圆理论，知道邻域交是邻域。

然后做完了？？？？我会 T3 了？？？？

显然这个时候即使会了 T3 也没有用了。

赛后

听完讲题后，我发现：

我的 T1 就是正解的做法，只需要一个很简单的分段转移就对了。

我的 T3 也是正解。

我的得分是 65+89+40=194。

如果死磕 T1，不会 T2 正解，就是 100+56+40=196。

如果开的前两题中包括 T3，而 ds 题的代码能力又是我擅长的部分，我认为我能快速通过 T3。

如果 T2 不被创，或者 T2 放了一道正常的签到难度的题，那我的情况会好的更多。

做 T1 的时候，由于我的做题策略给自己设定了一个阈值，如果做题时间超过了阈值就跳题，因为可以把我需要做比较久的题当成困难题，不在上面浪费时间。

然而 T1 正好是我需要花阈值 +eps 的时间才能解决的题，也就是我的阈值在这个题上取得了最劣解，在快做出来的时候跳了题。

T3 我第一次看的时候只搜了一层。这是因为如果再深一层在很多题上都会花费我比较多的时间，所以我的策略是搜一层，排除掉很简单的题的情况（实际上 T3 确实不是很简单的题）。

然而这个 T3 又恰好是我能秒掉的题。每一步我都见过。但是如果只搜一层又是做不出来的。只需要稍微往深搜一层就能秒掉。

如果想调整策略让我打的更高，我可以选择直接用最劣的策略：死磕 T1。也可以选择直接任意换一个开题顺序。

最后出榜之后我甚至还是 Ag rk1。

本来对这场比赛是没什么感觉的，觉得爆了就爆了。

现在知道爆的原因之后，给我的感觉是：出题人放了一个我需要花阈值 +eps 的时间能做出来的题，放了个能把我控的比赛结束的不算签到的构造题，又把我唯一能秒掉的题放到了 T3 这么一个我不会优先思考的题目位置。

就像是出题人安排了题目难度和题目顺序，让我迭代出来的比赛策略在这场比赛中采取了能使这场比赛打的最低的策略，还调控分值把我控分到了银首。

我一直想尝试构建一个能保证不爆的自动机。不求能让我打的很好，只要能不让我跌出金牌就行。

而现在使用的比赛策略也是我认为已经比较优的策略了。在之前的 dmy 集训中，也确实能在大部分的比赛中取得比较好的成绩。

但就是这么一个我认为失误概率很低的比赛策略，偏偏在正赛中抽出来了一个能把我爆掉的情况。

我该在哪里停留？我问我自己。

upt：还恰好把我控到了 10 级钩 -eps。rp 这块。