省选模拟赛 记录

· · 个人记录

2025/07/28

第一场，感觉不太清醒，已经深刻认识到错误。（耳刮子已经打了）

T1

咋是交互题，之前没做过。 花了 10min 看懂了题面，就是要花尽量少的次数得到权值和，然后只需要交一个函数就行。

很快想到了 2nh 次询问，每个点询问 h 次，加起来 /(n-1) 就行。

然后就卡住了，想到 9：50，不会了，开 T2,3。

等到 11:20 回来再看，发现如果每个点访问 1，那么根被加了两次，叶子加了一次，剩下的点加了三次，只需要把根找出来，减减加加就行。很快写完，预计 62pts。

又不会了，一直没有很好的消去贡献，但是感觉和正解很接近。

赛后讲题，发现就是如何凑贡献的问题，可以找出前两层的点，然后算出根的权值来，然后加一加就行了。

但是提交上的代码 CE 了，原因是我定义的 solve 函数是 solve(long long,long long)，但是应该是 solve(int,int)，然后就挂了。

T2

一开始以为是 2-SAT，但是发现并不是，2-SAT 只能做判定和构造解。然后会了最低档的暴力，但是此时脑子已经不清醒了，试图研究特殊性质，但是并没有进展。

赛后讲题，就是从特殊性质入手。然后就是看成一堆区间，答案要么是一堆有交的 a\lt b，或者是一个 a\gt b 和包含的他的一堆 a\lt b，线段树很好维护。

暴力又挂了，原因是左移右移数错位了。

T3

只会阶乘暴力，想到了 dp，但是并没有很好的设出状态，推出式子。

赛后讲题，发现可以设 f_{u,i}，表示说 u 子树内进出了 i 次，转移是容易的。但是优化没听懂，掉线了。

总结

几个问题：

1.在 T1 上花费了过多时间，且因为低级错误 CE，在本地 CE，爆出 undefine 的时候就应该意识到函数写错了，但是我以为是交互库的锅，把函数粘到了 grader 里，实现了自测。赛后看这是很可笑的。

2.在意识到题目可能过难时，我没有很好的稳住心态，脑子成了浆糊，导致 T2,3 应有的部分分没有拿到。

3.dp 太弱，设状态，推式子的能力都不足，应该加强训练。

4.对于简单的部分分实现，出现了掉以轻心的情况，犯了弱智错误。

5.策略出现了失误，比赛节奏被打乱。

6.体力，脑力都出现了掉线的情况。

2025/07/29

感觉状态比前一天好多了。

T1

这个一眼就很数位 dp，然后想，然后发现可以只关心每个数填了多少，感觉状态数不多，发现 10^{10} 只有几万个，然后开写，但是写完发现没有暴力跑得快，10^6 跑了 5s，心态有点崩。冷静算一下，复杂度太高，不太能接受。

一直在想如何优化状态，猜想是不是不关心具体每个数出现了多少次，而是像之前某个题一样只关心出现 i 次的有多少，但是在这种情况下不会处理顶上界的情况。

此时已经九点多了，dp 没有进展，遂打暴力。发现 r 为 10 的若干次幂是容易的，可以爆搜/打表。于是打出了 10^{18} 以内的。然后发现 10^8 以内的可以用分块打表，很快写完。有点不太放心，因为文件大小来到了 95KB。

先去看后面的题。

后面再看，没太有进展。

出成绩，文件过长，表炸了。评测的时候老师的评测机开到 50KB，开到 100KB 重测后没有挂分。

T2

想了一会，只会阶乘暴力。

然后发现要转化成一个排列，之后 dp，但是我不会了，没能想出来暴力 dp。

赛后讲题，发现要注意到先将 a 数组排序，然后注意到最后一个未匹配的 B 类点之前的 A 类点都要匹配，之后的 B 类点都要匹配，基于此可以前后 dp，然后拼起来。和之前讲的某个题是一类套路。

T3

读懂题了，感觉要挖掘一些性质。

研究了一会，发现 DAG 肯定 A 赢，推广一下，后续没有环的一定也不行。

然后就不会了。

赛后讲题，发现还要发现一些性质。

首先删掉只能有限次操作的点。

如果一个点只有一条出边，那么它只能到后面那个点，所以可以合并两个点。

启发式合并一下。

需要惊人的注意力。

总结

好的方面是没有出现前一天的重大失误，比赛节奏策略也逐渐适应。

不好的方面是暴力分依旧没有拿满，回去要摆正好心态，好好练 dp 了。

2025/07/30

状态回来一点了，但是还是有失误。

T1

一看是异或，感觉和前两天 NOIP 模拟赛的 B 很像，因此直接设 f_{i,j} 表示考虑了前 j 位，数字为 i 的代价。写完发现，大样例要跑 5s，回去看看，原来是复杂度算假了。最坏情况下他每次都要更新 2^m 个点，T 飞了。

赶紧看看怎么修，但是到 9:30 没想出来，写了个 c\le 3 跑了。

后面回来再看，没有发现什么好的性质。

赛后讲题，不用记位数，只需要每次暴力访问 m 个可能更新到的点，暴力 bfs 更新，由于每个数最多被更新 m 次，所以复杂度是对的。

没做出来，有点不应该。

T2

2 min 读懂题，暴力模拟就能过第一个 sub。可以倒序考虑每次和哪个位置交换，但是复杂度好像不对，就没写（实际上是可以过 sub2 的）。继续想，没想出来。

讲题，咋是数学题。把开始的 x 看成矩阵，异或就是广义矩阵乘。把每次的乘的矩阵命名为 A。因为倒序考虑，所以 xA^i \bmod i 的结果我是知道的，先只考虑 2^k，那我就知道了结果的底 i 位。由于 x 的每一位都是原来的一些位的线性组合，所以我们就得到了 i 个方程。但是方程数有点少，考虑多用一点。我们知道了 \bmod i 的余数，我们就知道了 \bmod i 的因数的余数，所以我们就知道了 \bmod \operatorname{lowbit} i 的余数，那我们知道了更多方程，自由的位数就更少了。

T3

3min 读懂题，实际上就是要有一个排列满足第 i 行第 p_i 列为 1 的概率。

首先想到暴力全排列，然后想到，这个东西可以 dp，每次枚举出来每位是 0/1，f_{i,s} 表示前 i 行，选了 s 中的列，能不能选出来的全是 1，转移是容易的。

然后又不会了。

$n\le 9$ 要用 Hall 定理，没听懂。 ### 总结 好的方面： 暴力拿满了，思考也比较充分，没有出现低级失误，能像一个正常人类一样想题了。 问题: 对于基础的算法应用转化理解不透彻，把简单问题复杂化了，掌握不完全。 ## 2025/07/31 ### T1 第一眼以为是 2-SAT，然后发现不能处理 $l,r$ 的限制，于是果断放弃（2-SAT 学魔怔了），然后想别的做法，然后想到可以把 $m$ 条限制看成边，一个连通块内确定了一个点就确定了一整个连通块，所以可以枚举编号最小的点，有 25pts。然后就卡住了，想了一会，没有进展，想特殊性质也没想出来，心态有点崩果断弃题。 赛后得知可以用 trie 维护编号最小的点的可行区间，长知识了。 ### T2 第一眼没读懂题，再读一遍，手模一下样例，懂了。注意到 $n\le 200$ 可以暴力跑出来，然后去想特殊性质。 想了一会，发现 AB 性质就是保证永远不会出现 his，A 性质保证只有一开始会有 his，只需要维护一下开始的 he，两种一起跑一下，有 35pts。 继续特殊性质，注意到 his 很麻烦，可能是解题关键。如果任意时刻都没有超过三个 he，说明只有最开始几个串有 his，所以可以暴力跑出前 $6$ 个，然后和前面一样做。 再看，感觉 D 性质没有什么用。发现只有 hihi...his 和 hihihi...he 是难处理的，但是不太会处理。 赛后讲题，得知可以维护一下每个字符什么时候变，每个间隔什么时候插入即可。 ### T3 一看就是性质题，但是推了 30min 没推出来，果断放弃。 正解及其 Ad-hoc 要先给他推到一条线上，然后再做类似数位 dp。掉线了。 ### 总结 还是要稳定好心态，要打好暴力分。 要加强对于数据结构的应用，要加强自己的代码能力。 ## 2025/08/01 终于过题了\ll\ll。 ### T1 先看 T1，一下子会了 $n^2$，有 50pts。然后有点卡住，先去想链，发现可以直接线段树做，那么 $2\times 10^5$j加上特殊性质就有 86pts，时间还早，有充分时间在想一会。 发现问题其实是维护路径信息，那么能不能把询问离线下来，挂到 lca 上一块做。先想了 dsu on tree，发现不太行。又想点分治，可以把询问挂到点分树的 lca 上，然后暴力 dp 一下，就做完了。复杂度 $O(nk^2\log n+qk)$，有点卡常不过问题不大，开了 3s，先看看后面的题，没读懂，先不管了，开写。9：20 写完，大样例挂了，有点慌，一看 dp 式子假了，更慌了。 先上个厕所冷静一下，没事，能修。10：20 写+调完，发现大样例要跑 3.8s，空间要用 400MB 以上，有点危险，关掉 long long，应该没啥问题了。 ### T2 写完 T1，再重新读一下题，会了 20pts 暴力，先写。写完发现卡住了，想一会到 11:00，没有进展，果断弃题。 讲题掉线了。 ### T3 没读懂题，再读一遍，没看懂他给了 $f$ 数组，为啥还要给 fa 函数，有点迷。而且一点思路都没有，弃了。 赛后讲题，原来 50 的部分分（fa 函数）是为了能把两个数组都自己用（因为空间卡的很死，不能再开数组），还要借助链式前向星的思想，用 head 和 nxt 实现以下，很巧妙，有点人类智慧。 ### 经验教训 要大胆冲一些自己有把握的分 要通读所有题。 要增强码力，减少调试时间。