THUWC & WC 2024 游记

· · 生活·游记

前言

对于 THUWC，已经拿过两次“优秀”了（虽然听说上一次优秀有可能是因为上上次优秀所以考的再差也给了），所以没有任何压力。对于 WC，上次发挥得很差，打铜了，希望这次能打得好一点。综合我对 WC 2022 和 2023 的印象，感觉 WC 金牌挺容易的。WC 2022 第二题白送，第三题随便拿点分就金了；2023 第一题 45 第二题 16 第三题 32 也金了。但是期望不要太高，我希望我这次不炼铜就行。

因为这两个比赛是连在一块的，所以写在一起了。我也会写一些比赛之外的东西，使这篇文章真正成为“游记”。

接下来写一下 NOIp 2023 到现在之间干的事。

考完 NOIp 后回去学了三周文化课，当时一直在备考英语听口，所以其他科的压力不是很大。我当时又作死打了 CF 上华为的比赛，因为奖金很多。结果整得我特别累，每天回家就坐在那里，跟打 AHC 一样写工程题。有一个 bug 让我调了好几天。当时我的排名一直在 60 左右晃荡，而 60 名以内就有好几千的奖金，所以我就拼命地打这个比赛。结果最后只有 70 名，最终我文化课也没学好，这个比赛也没得到钱。不过打这个比赛还是有收获的。

后来又参加了我们学校北校区的省选集训。感觉和之前的集训一样，我也在认真地做题，但是就是卷不过别人，感觉别人的实力都很强。相同点还有一个就是听不懂讲课。我一直觉得这种讲课的效果不会很好，因为它会在短时间内灌输很多知识点，无法让人深刻思考，可能会漏掉一些需要思考的地方。秉承着这个观念，我就没怎么听课。不过这一段时间还是学了一些东西，比如一些神秘的 dp，竞赛图什么的。而且这一段时间我感觉我的乒乓球水平提升了很多，那时候有时间都去打乒乓球，每天可以打两个小时。

然后就回去上文化课了。还是跟之前一样，两周的时间上文化课。不过我没有特别紧张的复习，可以算是摆烂了吧。但是至少我考前学了学化学，背了背政治，成绩不算难堪。

考完试就又停课了，算是比赛前的临阵磨枪。感觉水平没有下降太多，至少 2400 的题大部分都能切。周五尝试和 wz 和 zrj 决斗，本来希望决斗可以延续，但是之后就没机会了。

1.24

随家长乘坐飞机来到重庆。到了飞机上发现我的右前方是 cyx 和 wz，不过我们没有过多交流。在飞机上我大部分时间在打麻将。

到重庆之后来到了翰文大酒店。

1.25

上午与家长徒步前往某个索道，走到了发现需要排两个小时队，赶不上报道了，于是开始随机游走。走到了嘉陵江与长江汇合之处。

下午报道。发现试机的第三题是去年的第二题，而当时想出了一个神秘递归思路没能实现。于是我开始沿着递归的思路想，想到每次可以根据两个数组的中间的大小关系与 k 与区间长度的一半的大小关系淘汰某个数组的一半，先解决了 n_c=0，然后顺着就想到了 9 \cdot \log n 的做法，接着发现可以直接记忆化变成 3 \cdot \log n，写完就过了。接着做第二题，发现很简单，于是试机 AK 了。我和 wz 同考场，他不会第三题，可能是没想到递归这块。

晚上去吃了一家涮串的店，挺好吃的。希望我没吃多。

1.26

这一天是 Day1。

顺序开题。先看 T1。最开始将 n,m 看反了，于是写了一个暴力，得了个暴力分。后来发现可以直接 dp 看每个数对应的是哪个集合。这样暴力实现是 \mathcal O(m \cdot 3^n \cdot n) 的。接下来发现可以每次取一个数作为选的，就不用枚举子集了，复杂度变成 \mathcal O(m \cdot 2^n \cdot n)，写了一发得了 77 分。这时候已经过去 25 分钟，有点违背策略了，于是我赶紧看后面的题。（25min）

看 T2，看上去就不太可做。仔细想想也没有头绪。发现 m=1 有很多分，于是放着等一会写。

看 T3，看上去极其可做。这种题是我比较喜欢的乱搞题。想了想前两个 subtask 就跳过了，等着一会认真想。

看 T4，看上去是一个比较正常的数据结构题。很快会了暴力，愣了一会发现可以建图，这样就可以解决 subtask 2 了。看完所有题后，我打算先解决掉 T1，再写 T2 的 m=1，再写 T4 的暴力，再认真想 T3，最后留时间写 T4 的 subtask 2。（50min）

我想使用之间的算法卡常过这道题。我先本地造了数据，然后跑了一发，发现用了 5 秒。我将暴力枚举一个状态中存在的值改成每次找到 lowbit 并减去，用了 2.5 秒。感觉没什么可以卡常的了，于是我打算思考正解。经过认真思考后，我发现对于每个状态，只需要找到总和减去代价最优的人让他来就行了，否则可以替换成那个人，一定不劣。这样转移的时候枚举他最优时的状态，再枚举子集转移即可得到 \mathcal O(m \cdot 2^n + 4^n)（当时没认真算复杂度以为是这个）的复杂度。这样写了之后被卡常了。经过造数据发现时间的瓶颈在找到每个状态的最优的人，因为数组访问不连续。换成先枚举每个人再枚举每一个状态就通过了。（75min）

接下来写暴力。T2 的 m=1 很快就写完了。只需要枚举区间并进行差分。（85min）T4 的暴力也很快写完了，根本不需要思考复杂度怎么样，怎么写都能过。（105min）这时候发现 T2 除了 m=1 还有 n=2 的暴力没打，于是写了。（120min）

接下来思考 T3。看 subtask 1。想了一会发现先查询下面两个位置，再查询 (2,2) 或 (1,2) 即可。看 subtask 2。发现精细实现二分即可。最开始写正常的二分只得了 17 分，于是改成递归，认真实现了就得到了 20 分。（130min）看 subtask 3。很快就想到了可以将一个正方形分成四个小的正方形，再查询右下角将问题转化为三个子问题（根据右下角是否有值可以淘汰掉右下角和左上角中的一个）。先随便写了一发，得到了 29 分。然后改变了递归顺序，并加上了最优性剪枝和如果一个矩阵无值直接 return，得到了 49 分。接着发现如果递归到了右下角，不需要判断矩阵是否无值，于是记录了一下，得到了 51 分。接下来发现因为剪枝， bfs 会比 dfs 好一些，改了，竟然还只有 51 分。（180min）

这时候打算换算法。我还是感觉需要分治，于是这次尝试每次分很多块。经过计算，分块的顺序如下：2^{12} \to 2^8 \to 2^4 \to 2^2 \to 2^1，每次得到若干个块组成的矩阵，求出最接近右下角的位置，那么只有与它的 i+j 距离不超过 1 的才有可能成为答案。于是只需要将这些位置递归下去即可。这样写出来之后，交上去，竟然还是 51 分。仔细想想，好像这个做法和上面的本质相同。于是调了调参，无果后就打算继续换算法。（210min）

我发现在第一个做法中，如果右下角有值，右上角和左下角只需要一半，否则左上角只需要一半。对于一半的，不需要查询右下角是否有值就可以直接递归。这样写了，又得到了 51 分。我发现这个做法和上面的还是相同的，因为即使递归不查询，剪枝也会查的。这时候打算跳过这题，赶紧思考 T2 并写了 T4 的 subtask2。（225min）

重新想 T2，还是没有什么思路，感觉这个东西很难做。尝试对着 n=2 的结论和 n=3 的样例找规律，也无果。（255min）只剩 45min 了，赶紧开 T4 的 subtask2。捋了一下思路，感觉可以先对每行合并区间，再对相邻行的区间连边（最左的点），然后对查询的点找到这一个区间最左的点，将问题转化为多次查询无向图中两点之间路径最小值的最大值，使用启发式合并解决。虽然代码不难写，但是写的东西很多，很繁杂。我就以最快的手速，在 25 分钟写完了。经过简单调试，通过了第一个样例（将中间的那个 2 操作删掉后的样例），但是交上去 RE。我打算下载大样例，并看第一个 2 操作的答案是否正确。果然错了，但是我并没有 RE，而是输出 -1。对着大样例很难调，一直调到了 12:58 还没有调出来。最后一分钟，我打算静态查错。我明知道调出来的概率很小，但是我还是看着代码，追求着一点点希望。最后 50 秒，我打开时间，但眼睛还是看着代码。还剩 40 秒，我发现查询的时候没有判断这个点所在的区间是否存在点。这样确实会 RE！我赶紧加上了判断，提交。我看到这次没有像之前一样瞬间返回 RE，说明有戏！终于刷新出来了，得到了 21 分！而时间是 12:59:48，说明我又一次绝杀了。

于是最终我把该得到的分都得到了。最终的得分是：100+46+75+36=257。

考试结束，与 wz 讨论了一下成绩。发现他虽然 T4 的 21 分没调出来，但是 T2 得到了 90 分。算出总分，他比我多 4 分。看来这个分比较大众。之后看到 cyx，发现他切了 T2 且 T3、T4 得分和我一样，上 300 了。看来我被 T2 区分了。最后看到 hjl，发现他 T2 和我分数一样，但是没时间写 T3 了。看来是策略问题。

下午没听讲座，回酒店，直接睡了一个小时。然后去健身房跑了会步。晚上随父母走到了解放碑，吃了很多小吃，又吃了一顿饭（砂锅）。回家的时候吃得很多，希望睡觉不被影响。

1.27

下面的内容是我在 1.29 时写的，有些记忆已经模糊，写得不太好。

这一天是 Day2。

只有一道题。这次吸取了上次的经验，认真读题。看题面发现要实现一个 AI。接下来我按照题面所述的一步一步建文件夹、操作，然后写了一个简单的代码，按照题面所述的测试。这一次它成功运行了，看来不会重蹈覆辙了。然后我简单地看了一下参考资料，没怎么看懂 \alpha - \beta 剪枝和后面的内容，打算自食其力，写一个有限步数的搜索。（20min）

我先写了一个简单的根据估价函数选择最大的算法，估价函数定义为使己方棋子连成两个或者使对方棋子连不成两个的个数加上三倍使棋子连成三个或者使对方棋子连不成三个的个数。先写一发简单的可能是因为以前打传统比赛的经验（先写一发暴力试试），或者是防止一些问题导致写了一大堆但爆零。这样写了一发，本地测试，发现与 10 打有时会 RE 有时可以完全干掉它。交到第一题中得了 70 分。也许我当时认为这个做法没什么前途，或者是因为代码 RE 了，就没打算扩展下去。（100min）

接下来我打算写有限步数的搜索。仔细想了一下实现，我发现需要在搜索过程中记录一个变量，表示走到当前这个局面的概率。然后在有限步数内如果赢了或者输了就加上或者减去概率。这样就会得到一个值，可以近似胜率。写了一个代码。测试，发现可以薄纱 10，但是又出现 RE 这个困扰我一整场的问题。我又开始测试 20 和 30，发现也可以跟它们五五开。这时候打算交一发第一题。测了几分钟后发现 CE 了，检查了一下才发现压缩包中不让新增文件。又交了一发，等了一会发现只得到了 60 分。（155min）

经过在代码中输出走的位置，模拟了很多情况我发现有的走这个位置就必胜的情况和不走这个位置就必败的情况没被考虑到。加上了这个判断，又交了一发，得到了 90 分。（180min）接下来又模拟了很多情况，发现计算胜率的时候也需要判断一个位置是否必须下。这时候发现有时候已经可以赢 40 或 50 了。这时候发现时间还剩接近一个小时，因为交的次数已经不多，所以我打算在最后时刻再交。我发现每次选择位置的时间跑不够三秒，所以我加了一个卡时，并把递归层数增大。这样确实有改善。根据上面判断一个位置是否必须下的启发，我发现可以在计算胜率的过程中判断一个位置在几步内是否有必胜策略或者对手有必胜策略。于是我赶紧加上这个优化。这个优化还有些细节，如果有必胜策略直接返回，如果有必败策略并不是直接返回，而是跳过这个位置。这样写完之后只剩大概 15 分钟了。没怎么调参，发现仍然有时候可以打败 40 或 50，就直接拿这个代码交了。（230min）

最后直接交了五道题。交的过程中，我非常担心这个代码 CE，因为如果 CE 了就什么分都没有了。最后看到第一题得到了 100 分，才不提心吊胆。最后我多待在考场 10 分钟，与 wz 一起看着最后的评测。最终得到了 100+90+60+20+20=290 的分数。我发现挂了的点中有很多个点都是 RE，而我最终也不知道从始至终一直都在捣乱的 RE 到底是什么问题。如果有更多的时间调 RE 并调参分数可能会更高一些。

出考场发现 wz 不会用 Linux，只能直接交到 OJ 上看写的对不对。最终得到了 200+ 分。这样能写出来 200+ 分很强。然后发现 hjl 得到了 270 分，写的是估价函数，应该算是翻盘了。cyx 只得到了 100+ 的分，可能是摆烂了。

下午参加闭幕式，玩了会游戏，然后想尝试 saiblo，结果发现虚拟机被我删了，自己赛时代码没保存，只好对着录屏文件一帧一帧地复刻代码了，幸好赛时最后时刻翻过一遍代码。发现之前得过一等约的没有纸，这样我打了三年就都没有纸。恭喜 hjl 喜提一等约。因为我的成绩偏序 hjl，所以我应该到一等线了吧。

然后来到了嘉瑞酒店。在酒店附近吃了顿饭。晚上一边看北京北汽打球，一边写 CF1909G 的 fjy666 的做法。恭喜北京北汽绝杀。

之后又打了 CF。一上来就被 A 题卡了一会，可能是因为太累了。然后发现 B 题是线段树板子，写了一个区间加等差数列区间求和。交上去 WA on 2，发现是有一个左儿子写成右儿子了。再交又 WA on 2，我受不了了打算写一个对拍。结果竟然拍上了，而且是最朴素的暴力。调了好久无果后我打算重新读题。我突然发现输入的 X 不满足单调递增，即不一定满足 X_1=1,X_m=n。改了这个问题后就过了。接下来看 C 题。我打算直接模拟折纸过程，结果我裁的纸并不是正方形，导致折出来的折痕不是很精准。通过找规律我发现山谷与山峰的一部分相等，而另一部分是一个正方形。根据这个规律我打算计算相等的那两部分的总和。但是我没细想折痕的形态，导致只能通过找规律来推出其他情况。最终找了一些规律，但是因为推导过程太复杂，最终没实现出来。

1.28

上午在测试复刻的代码。因为虚拟机被我删了，我只能启动我的电脑中很少用的 Linux 系统。首先花了很长时间配置好了 codeblocks，后来发现不需要 codeblocks，可以用 VScode 做文本编辑。我先解决了 RE 的问题，发现在第一次枚举走的步（计算胜率）的时候没有判断是否已经没有位置了导致的。然后尝试将参数开大，取得了更好的效果。后来一直在调参。

下午被家长拉出去玩了，排了很长时间终于排到了长江索道，感觉一般。然后来到了长江南岸，发现比北岸萧条多了。本来打算沿着一条道一直走，直到看到像样的饭店，结果一直走了很久都没看到。于是我们开始定向前往大众点评上看到的饭店。然后就发现直线距离只有 300 米的路线走了 1.1 千米。很喜欢饭店里的青菜波和麻婆豆腐。又吃多了。

晚上继续 saiblo，所以开了 Linux 系统。我又想一遍看北京控股打球一遍写代码，结果发现网站没有声音。我又找了一堆手段，都没解决，反而导致电脑变卡了，经常需要等待。于是我又去找优化电脑速度的手段，加了也没用。后来实在受不了了，打开 Windows 看打球。看完后又打开 Linux，发现声音好了，电脑也不卡了！看来重启确实能解决 90% 的问题。我发现赛时的参数如果不加卡时会 T 飞，说明很多情况都没跑到，需要将参数调小。但是调小之后效果更差了，很奇怪。总之没什么进展。

1.29

上午思考了一下其他的做法，因为发现胜率不是很能体现一个位置的优劣性。但是没什么想法。感觉确实需要学习一下其他算法。之后去育才中学报道了。

下午玩了一会 flowr，一会雀魂，玩了两个小时就感觉游戏没啥意思了，于是去打乒乓球。打完回来又玩了一会。之后去参加开幕式。回来发现摆了半天实在是无聊而且空虚，决定这几天以后不颓废了。

晚上 11:30 睡的觉，因为这一天没啥运动而且这是一个新环境，果然没睡着。一直到 4 点才睡着。

1.30

上午是 lxl 的讲课，我显然听不懂，于是开始补上次 CF 的 C 题。我发现当时的猜想确实是对的，除了第一次折叠，每次折叠的山峰和山谷的数量都是相等的。于是只需要求总和即可，而总和大概是一个等比数列求和。其实到这里就一定结束了，但是我当时不知道可以实现一个 a+\sqrt{2}b 类，导致进行了很长时间的分母有理化，非常烦。最后花了很长时间才调过。

中午尝试去操场踢球，发现主办方提供了一些球，感谢主办方。发现北师大实验中学很多人都在踢球，羡慕。

下午是 xtq 的讲课，我也听不懂，但是中午忘给电脑和手机充电了，导致一上来就啥都干不了了。罚坐了 3h。

晚上发现距离考试只有不到两天了，于是打算开始打板子。整理了一个 50 道题的模板题单，然后分成了两个比赛，分别写。我建议同学也写一写，但是他们在颓废，最终他们都只写了 \mathcal O(1) 道题。当时发现距离省选只有一个月了，而水平还是这么低，NOIp 分数也这么低，心情比较低落，就说了些比较过分的话。比如我对 wz 说“再颓就退役了”，又对 zrj 说“别颓了，要不然就像 wz 一样退役了”。但是道理确实是这样，他们爱听不听。最终我写了 10 道题，而有一大半时间在调线段树 3。

1.31

上午是 qlr 的题目选讲，虽然我感觉认真听的话可以听懂一些，但是因为还有一车模板没写，就继续写模板了。写了几个数据结构的模板。

中午叫上 wz、wrz 和 zrj 去踢球，踢了 2 打 2，然后溜了会猴。之后看了北师大实验的人踢球，体会到了“乱斗”。最后跑了个 300m，本身都很累了，但是还比之前跑得快了 2s（56s），感觉 whk 时期坚持跑步取得了较好的效果。

下午是量子力学的讲座，我打算一边听一边写板子。感觉讲的一些东西挺不可思议的。写了几个图论的模板。

晚上发现明天就考试了，只好挑一些有用的模板写。写了费用流、AC 自动机、三维偏序、杜教筛、CRT、矩阵快速幂、高斯消元、线性基、NTT。我问 hjl 为什么在摆烂不写模板，他说模板会的都能写出来不会的也不会考。但是我觉得提升熟练度对考场上写出板子的能力和码力都有提升。他不爱听。我感觉他有点像骆驼祥子……

晚上还去试机了。没看到 selfeval，导致我试了个寂寞。因为还要打板子所以没怎么试就回来了。

我本来想平稳地睡觉，结果因为各种原因特别闹腾。好不容易睡觉了 hjl 还在拿电脑熬夜追番，很吵。于是我又一次失眠了。也许后来睡着了，但即使如此也是浅睡眠，睡得很不好。

2.1

今天是 WC 比赛日。

早上醒来很困，吃饭的时候也很困。在排队的时候有一个时刻同校的已经进去了，而我还在外面。那时候我感觉很孤独。我想到了 NOIp，想到了还有一个月就进行的省选，想到了自己的水平，想到了即将在困倦中考的 WC，感觉很迷茫。又想到这些同学，除了 cyx 都很颓废，可能他们也是找不到方向吧。估计省选之后很多人都退役了，为他们感到惋惜。

这时我意识到我被我自己搞心态了，没想到心态竟然可以在飘忽的思绪中改变，而不刻意。我赶紧调整好心态，平静地面对比赛。

还是按照 NOIp 总结的策略，先把所有的题看一遍。首先发现三道题都是传统题。看 T1，发现比以前的题目清新很多。想了想，发现可以枚举第一个数组的总和，然后进行一个复杂度中含有 T^3 的 dp。但是分数里没有这一档，不知道为什么。之后又进行了一些思考，比如对每个位置算贡献，但是也不太可做。看 T2，发现也比以前的题目清新很多，而且比较可做。这时我感觉到了不对劲，也许这场的难度很简单。我将相邻两个的选择情况分四种情况讨论，发现 L（下文用 L 代替 2L）本质只有 \mathcal O(n) 个，确定了 L 之后可以对每个左端点做一个 dp，就可以 \mathcal O(n^3) 了。看 T3，发现这道题看起来有难度，不太可做。细想了想发现如果确定了线段树上父子三个中的两个，剩下的就确定了。于是可以暴力枚举，并先向上更新后向下更新。这样就求出了线段树上每个节点是否能被表示出来。然后可以将区间放到线段树上，检查每个节点是否能被表示出来。此时我对这道题初步的感觉是我这个思路不一定对，而且这道题不太可做。

接下来依次对每道题写暴力。我先对 T1 写了一个暴力，结果发现样例 1 过不去。（44min）经模拟，我发现我读错题了。原来做题者不知道他做某道题需要多长时间，无论如何都需要花时间在上面。这样就说明他能过的题是一个前缀。这样就可做很多了。可以对每个位置算贡献，最终只需要求前缀和后缀选择若干个数使得总时间小于等于某个数的方案数。这个问题直接 dp 即可解决。我很快写完并调过了这题。（60min）T1 怎么这么水？看来这场果然不对劲，果然要比以往简单。

因为这场的难度比较简单，所以我也调整了一下对这些题的难度预估。感觉 T2 也不一定不可做，毕竟题面如此清新，题目如此可做。我先写了一个 T2 的 \mathcal O(n^3) 暴力，（68min）然后发现可以双指针做到 \mathcal O(n^2)。但是无论如何都需要枚举 L，看来这个做法没啥前途，我也没写这个 \mathcal O(n^2) 的做法。按照策略来看，我现在应该写 T3 的暴力，但考场上可能觉得我可以在这道题上得更多的分，而 T3 得不了什么分，就继续想这题了。这可能是一个策略失误。

我对相邻两个的选择情况进行了分类讨论，发现两种情况是确定的，形成了两条断断续续的线，都由若干条线段组成，且没有重叠。剩下两种情况要求一种的 a_i+a_{i+1} 之和的最小值大于另一种的最大值。这时候我发现一种合法的转移一定穿过了所有的线段。此时可以对每种从一个线段跳到另一个线段的方案取极值，然后使用 ST 表维护，并二分。但是这种做法有很多细节，比如 a_i=a_{i+1} 的情况，很难处理。这时候还有 3 个多小时，感觉能写出来，于是硬着头皮写下去了这个做法。过了半个多小时写完了，简单地调了调过了前两个样例，却在第三个样例上与答案差几千。这时候我发现我的代码有好多地方细节都出错了。于是我认真调了调细节。但是样例 3 的答案一直在正解左右几千波动，从没有吻合过。调了很久还没调出来，我却又发现了另一个细节需要处理，而这个细节不是很好处理。这时候我打算换思路了，感觉这个思路调下去可能会调一整场。我抱着尝试的心态测了一下样例 4，发现过了，但是发现 a_i=a_{i+1} 的个数为 0。看来这个思路确实死在了细节上。（140min）

我开始尝试 dp。但是普通的 dp 无法处理这种两个值需要同时取最值的情况。不过根据上面的思路，我大胆猜想，这两个值可以同时取到最优值。于是这样就可以将问题转化为求两个 dp 的某个值最后一次满足某种大小关系的位置。而这个大小关系具有单调性，所以相当于若干次求 dp 某个位置的值。很容易想到的思路是动态 dp。但是这里的矩阵乘法和以往的不一样，是 \max-\min。我突然感觉不妙，因为之前从来没有见到这种的矩阵乘法，也许它没有结合律。经过其他尝试无果后我打算拿程序检查一下它是否有结合律，顺便也写一个矩阵乘法以便之后用。我随机了三个矩阵，并将它们按照不同顺序相乘。测试，程序竟然输出了 ok！看来这种思路是对的！而且这种思路极其好写，没有任何细节。我便赶紧实现了这个代码。调过 CE 后，程序竟直接输出了样例 3 的正确输出！我本来只是想测试一下程序是否有 CE 或 RE，竟预料到它竟直接过了！测试样例 1,2,4，也全都过了！而且样例 4 只跑了 0.9s。我简单地卡了卡常，跑到了 0.6s，感觉很稳，就跳过这题了。（180min）

（上面的做法可能没讲清楚，可以看这篇博客以获得更详细的做法）

我开始写 T3 的暴力。写完后，轻松地过了样例 1,2，却在样例 3 上差了 4。我怀疑向上和向下可能需要多次，于是多次执行了这两个操作，却依然差 4。检查代码没写错后我开始怀疑思路的正确性。我发现查询的区间不能直接用线段树上的区间表示，可以将全部的和减去剩下部分的和来得到这一段区间的和。于是这个思路假了。我开始思考特殊性质来寻找思路。我发现特殊性质等价于用线段树上的节点确定所有点的值。可以用之前的思路，先向上后向下判定。接下来考虑判定转 dp。可以设 dp_{i,0/1} 表示它这个区间的总和是否可以只用自己或者下面的区间得到。这样就容易转移了。不过过程中我因为状态没想清楚，调了很久。最终过了样例 8。（248min）

接下来继续思考暴力该咋写。因为已经发现了问题所在，就容易想到解法。可以区间 dp，不只是对线段树上的区间，而是对所有区间得到这个区间是否可以被表示。因为转移的过程比较奇怪，所以我打算使用迭代的方式转移，即以任意顺序转移，但是转移多轮。写完之后果然过了样例 3，但是样例 4 跑了 0.7s，感觉有可能要 T。经过调参后，我将参数（迭代的次数）设为 3。感觉之后的部分分不太可做，于是这道题就写了 25 分，开始检查前面的题。（273min）

我将 T1、T2 的正解与暴力对拍，T1 很轻松地过了，T2 拍了 100 多组后竟然挂了！我猜也许是因为我猜的结论不对，但是在大多数情况下能跑过。我尝试将对拍的 n 开小，竟然还能拍出来。最终调到 n=5 都拍出来了，我开始模拟数据，看是不是暴力写挂了。我发现暴力会在路径中没有 01 或 10 的时候挂，需要对将 L 设置成 a_i+a_{i+1} \pm0.5。改完之后顺利地拍上了。

最后我给 T1、T2 拼上了暴力，然后等待比赛的结束。我思考会有多少人切了 T2，会有多少分 T3 得到了大于 25 的分。最终的结论是这个分数如果不挂分还可以。最终的得分是：100+100+25=225。

出考场，看到了高老师。我说前两题都比较简单。说这句话的时候有种蔑视或者骄傲的感觉。以后不能这样了，要谦逊一些。之后看到了 cyx，竟然他和我一个分。看来第三题确实很难。然后看到的人我忘了，反正剩下的同学里没人切第二题。我便跟他们讲我的做法，发现切了的人的做法和我都不同。看来我确实是运气太好了蒙上了。

中午一个人去踢球。尝试了一下凌空抽射，效果不好但是解压。

后来大概了解到了同学的得分，wrz 70, hjl 129, wz/zrj 169。

下午三点去查分，我跟着 wz 一起查，先看他的。发现他没挂。接着 wz 不知道去哪了，于是我自己去查分。当时觉得 225 的人估计有很多，所以我一旦挂分了就寄了。所以当时唯一的愿望就是不挂分。这个比赛对于我来说不是很重要，但是真正到了查分的时候心还是跳得很厉害。颤动的手慢慢点开得分文件，发现没挂分，很高兴，紧张的心情也放松下来。

接着我出去，等了一会看到了 wz。我打算继续踢球，他也想踢，但是他要叫上 wrz 和 zrj。结果他们刚开了一局游戏，最终没踢成。

下午是在打游戏和写游记中度过的。虽然打游戏很不好，但是毕竟是考后了，就玩一会问题不大。后来没去讲评，因为觉得听讲评不如看题解。晚上的文艺表演也没去，可能是太累了或者是想颓废。

晚上 12:15 睡的，原因是我在写游记没注意时间，而 hjl 和 wz 在 1v1 可能是上瘾了。这次终于睡好了，但是美中不足的是时间有点短。

2.2

上午去听课，发现没听就掉线了。于是我又开始玩游戏了。之后又睡了会觉。我感觉我已经有点上瘾了，这很不好。可能是当时没啥兴趣做题吧。要结束的时候终于想做题了，打算补完考前没写完的板子，结果只写了个 KMP 电脑就没电了。

中午拉着 wz 和 wrz 去踢球，考后第一天肯定得好好玩一玩。通过 cxy 成功与北师大实验以及其他的可能是北京人踢了。其实我们当时也想与他们踢。分队是我们三个加上金牌爷吴畅（？）打北师大实验加上一个 rdf 的还有 cxy。结果我们一上来就把他们打爆了。主要是 wrz 很强，再加上我和 wrz 开场就往死里跑。好像 wrz 连进了三个球。但是到后面因为体力不支，好几次很好的机会我都没把握住，我们队也没怎么进球。不过最后应该还是赢了。但是踢完后我已经要透支了，特别累。

根据前面几次讲座的听课效果，我们打算这次不去听了。我感觉在那里写题不如回宿舍休息后写题。回宿舍后，我直接喝了四分之三瓶水，然后将电脑充电后睡觉。不知什么原因，这次睡觉还没睡着，感觉很奇怪。不过我还是躺了一个多小时。醒来后，感觉头特别晕。本来打算回宿舍好好写题，这次却又忍不住开了游戏。这时候我们同学也都摆烂回来了，可能是 cyx 说的“都考完了还不颓废”支持了这个想法。于是又这样空虚地度过了一个下午。

吃饭的时候我就想，我之前在朋友圈里对自己的评价“我是那种既不卷，也不极度摆的人。每次稍有起色，就开始摆烂；发现自己不能再这样下去了，又开始卷一段时间。”太确切了。当然这个评价所在环境是我们学校，如果放到其他学校里我应该算是最摆的人。看来有一部分原因是环境的问题。不是那么自律的人很难在摆烂的环境下持续卷。根据上面这个结论，我接下来应该会卷一段时间。但是这样下去总是不行的，我需要持续地卷。目前还没有什么好的思路。也许回北京后可以强制改变环境以达到效果。

2.3~2.5

在 2.6 写的，记不太清细节了，于是概括地写。写的事情也不一定按时间顺序。

感觉这几天又辜负了我在 2.2 的游记中写的，当时都意识到了不能颓废，然而剩下的几天还是在颓废中度过的。

2.3 上午听 csy 的课，因为是随机化所以前面认真听了听，他讲到了一个一般图最大权匹配但是保证最大流很小的问题，说可以直接随机染色，概率是 \dfrac{1}{2^{flow}}。于是我就感觉，这个问题都可以用随机化解决。于是接下来的几天就一直在思考一般图最大匹配是否能用随机化做。

最开始看了一下题解发现第一篇就是随机化，那看来随机化确实能解决这个问题。我就写了一个每次随机增广的代码，得了 70 多分。我感觉这个做法不太能优化，于是看题解，发现第一篇题解和我是一个做法。于是我就一点一点改成题解的样子。最后交上去，竟然发现比我原来得分还低！我发现在题解发布之后有人加了 hack。但是这不能阻止我继续想随机化，因为我如果能想出来，就可以申请将第一篇题解撤下并加上我的题解。

之后又想了各种神秘做法，比如随机染色并调整，比如将这个问题转化为最大团问题并使用最大团的随机化算法解决。然而这些做法都没有什么进展。同时，因为我这个问题没有进展，我更想玩游戏了。于是这些天没少玩，可能想这个问题和玩游戏的时间五五开。

后来玩游戏也玩腻了，就打算写一个程序帮我打游戏。最开始写了一个绕着圈走的，效果一般。又写了一个随机游走并随机攻击或防守的，好了点。我发现如果想优化程序必须交互，即随时得到游戏的状态。但是这样就涉及到获取屏幕上每个点的像素。最开始使用 GetPixel 函数，但是这个函数常数太大了。于是我就发了这个帖子。试了很多方法都无法编译成功。终于找到了一个方法可以编译成功且能输出一些东西了，又发现与实际对应不上。最终感觉很难办就不管了。

与在宿舍中干的事同时进行的是踢球。2.3 人数增多了，但是还是踢半场。我的发挥还是很烂。最终踢了一个多小时，我的脚踝特别疼。但是原因并不是崴脚或者摔跤，只是因为踢的时间太长了且连踢了两天，身体受不了。2.4 我又去踢球了，可能因为这是冬令营的最后一天，人变得特别多。于是我们打算踢全场。这次我为了休养一下身体，就没怎么进攻，一直在左后半场待着。最初我们队薄纱了对面，我也没什么运动。后来 wz 去了对面，我的防守压力开始变大，跑动也变多了。我的发挥和以前一样，没什么亮点。回去的时候脚踝又变得特别疼。

考完比赛我最期待的就是闭幕式，因为我这个分数大概有金牌了。我终于得到了 2.4 的下午。听到金牌线是 220，看来我确实是金牌。颁奖的时候颁奖的领导发错奖项了，导致我们拿的奖都错位了。感觉我刚在疑惑中抬起头领导就让我们下去了。

2.5 随高老师和 wrz 坐飞机回北京。早上的时候要乘坐 8:30 的大巴车，结果我们在宿舍里磨蹭了会，又因为脚都废了走得很慢，导致 8:31 才到那里，被高老师说了一顿。候机的时候高老师又从这里出发，结合 wrz 打铁，和我们谈“知行合一”。我感觉他说得很对。但是我认为我们训练问题的关键在于不自律，也没有老师管。于是我向他提议让他在上课的课间等时间来我们机房检查。

总结

感觉这次的比赛我确实发挥出了我的最好水平，算是给 2024 开了个好头。发挥出水平得益于 NOIp 中总结出的策略。

但是这两次比赛也让我意识到了与高水平选手的差距。比如 THUWC 的 D1T2 就是能将我区分掉的题目。当时我觉得这题完全不可做，结果出考场之后发现很多人都有 90 或 100 分。WC 也能看出这一点。我当时认为 T3 得到比 25 分多的分数很难，但是出考场后发现很多人都比这个分数高。

关于 WC 考场上我并没有严格落实策略这个问题（当时我先想 T2 的正解再写 T3 的暴力），我感觉这也不一定是错误的。如果我先写 T3 的暴力，可能我会在特殊性质上浪费一些时间，再去写 T2 的时候也许换思路已经来不及了，只能一直调原先细节很多的思路，很可能调不出来。如果我先想 T2 的正解，一种可能是和考场一样，想出来了并写出 T3 的暴力。但还有一种可能是像 CSP、NOIp 一样死磕没磕出来，满盘皆输。

这个问题可能取决于策略的激进或保守，而这两种都没错，取决于比赛和对比赛的目标。像 CSP、NOIp 这种比赛，得保守；而对于接下来要进行的需要翻 100 多分的省选，就得激进。我认为策略的本质是：需要全面评价每到题目，并根据性价比依次实现每道题的每个档。而性价比并不只取决于分数，还取决于分数带来的价值。这就关乎到对比赛的目标了，所以激进和保守并不与策略矛盾。策略中也允许先做签到题而不是先写暴力，这也体现了性价比。不过对这场比赛，我认为还是需要先写 T3 的暴力的。因为想出 T2 的正解不是很简单，我这次也是因为侥幸才想出来的，而 T3 的暴力就相对简单。我还需要在接下来的比赛中逐步完善策略。

接下来是一些技术性的总结：

除了比赛，我对这次我在其他时间干的事很不满意。我感觉自己特别不自律，一旦处在颓废的环境就完全没有心情做题。我的看法详见 2.2 这一部分。我以后再也不能这样了。在 2.2 中我说我可以通过强制改变环境来达到效果，我认为这虽然不是本质的解决方法，但是至少可以在我探索到本质的解决方法之前使用。我可以结交一些卷怪，以后外出集训的时候直接去他们宿舍写题。或者我可以在宿舍的走廊里直播写题。我也学习了 cyx 的卷题方法：每天干的事都写到一个云剪切板里给家长看，让家长监督。