SZTU邀请赛游记

· · 生活·游记

10:00

开始看题。

首先看到B是个交互，看了一下发现不会遂继续往后看。

注意到I题是签到题，先写了。

然后看到F题似乎做过，是对于数字串建AC自动机然后跑在Trie图上跑数位dp,状态是第 x 位，在Trie图上的 p 点和是否最大和是否为 0。队友：上来就冲紫？于是写了快一个小时没写出来，被处理分数的细节卡住了。

队友发现K题很多人过，看到样例解释“初始有 2 只蚂蚁向左，所以最多有 2 只蚂蚁从左边掉下”，于是大胆猜测初始朝向为左的蚂蚁数量就是最终从左边掉下独木桥的蚂蚁的数量，显然只要靠左的蚂蚁才会掉到左边。于是队友光速打完。

接下来继续调F题，依旧没调出来，此时队友想到H题做法，于是将电脑交给队友，不久就过了。听队友说思路是终极技能没用，一个人发动后另一个人可以也发动，两个抵消就没用了。然后让 n 为偶数时Aura必胜，最后操作 1\oplus 或 0\& 将 1 变为 0。n 为奇数时Frieren在最后一步操作时如果剩余的数为 1 则可以将 0 变为 1，所以要求 1 的数量大于 0 的数量。

然后依旧调F题，想到计算分数可以是当前分数乘上剩余数字状态，和赛后题解一样，但因为神秘原因没调过。

然后队友提出写G题，于是把电脑交给他写。决定放弃写F，转去想队友之前没想出来的E。设 dp_{i,j} 表示 i 维立方体中有几个 j 维立方体，则 dp_{i,j}=2dp_{i-1,j}+dp_{i-1,j-1}，即上一维移动后要乘二并加上上一维升维的。快速写完果然过了。此时看了眼榜在20名左右。

经过inf分钟后队友调过了G，直接冲到了第4，非常爽啊。

队友写G期间去看了N，发现了一个类似启发式合并的算法，就是用类似归并排序的思想将两个力量值序列结合起来，顺便二分统计答案。不过仔细分析了一下发现是 O(n^2) 的遂放弃。然后想到查询子树本质上是查询一段dfn序的答案，于是想到树上莫队，每次往力量序列加入删除数用树状数组维护，不过时间复杂度是 O(n\sqrt n\log n)。

等队友写完 G 后开始写，写到一半发现封榜了。写完后交了一发WA了，对拍发现是取模的问题，调了半小时没调出来，结果把+mod*2改成+mod*10就过了？？？O(n\sqrt n\log n) 卡过 2\times 10^5？？？太逆天了

发现封榜前没人过N，感觉是N题首A。

最后看了眼A，感觉不会，就开始颓了。不过怎么那么多队都在看J，看着完全不会啊。听到旁边队伍爆发了几次欢呼让我感觉是不是该奋斗一下……

最后封榜前排名rk6，滚榜滚半天发现痛失N题首A，但凭借N题跳到了rk4，金尾，就很爽啊。

严肃在SZTU校赛中混到金牌。