10.25模拟赛总结

2023-10-25 19:28

文章标签 总结模拟 10.25

本文主要是介绍10.25模拟赛总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

考试时间及策略

7:40 - 8:00         开题。读题感觉 T1 是个贪心或者性质啥的。T2是个DP，而且和之前一场模拟赛的一道题很像。T3是个神秘字符串，T4感觉也是DP？？
8:00 - 8:20         想T1，发现好像如果有删除次数，一定要删除和最大的一对的其中一个，并且要删最大的那个。简单证明了一下，感觉没啥错。然后可以用堆加速找和最大的对的过程。写了个堆加链表，过了大样例。交了。
8:20 - 8:40         开始想T2，发现这玩意儿跟上一次做的题真的好像，但是它的限制条件变成了每一个节点如果有儿子的话它的儿子的最大编号要大于它的编号。所以不是小的一定要成为大的的儿子，而是也有可能成为父亲。想到我之前在那道题的DP方法，我把这两种思路综合了一下，惊奇的发现：好像可以做了？？？！！！
8:40 - 9:30         想了想转移后开始写，写道9：30的时候写完了，测了测样例，发现没过。火速查错，但是发现在我的想法中，答案跟样例输出不一样。画画图，想想有哪些情况自己漏掉了，发现当前的点不仅能够成为别人的儿子或者成为父亲，还能够连接一些树！！！！坏了，不会打假了吧。
9:30 - 11:00         上个厕所冷静一下，发现对于那种情况多讨论一下好像也能做，回到机子前开码！10：00写完了，但还是没过样例，只不过更接近了。调了调，发现转移的时候有一个数组下标写错了。赶紧改改，终于过小样例了！！！！！！赶紧测大样例，连过3个样例后，发现第四个又过不去了？？？！！！！但是考虑到前面的数据也挺大并且过掉了，所以应该不是算法错了，肯定是细节没处理好。本来我以为是乘的过程中爆了，但是改了改还是没过。心态有点炸，不知道能不能调出来。突然，我想到会不会是转移时枚举的边界出了问题。检查了一下，发现好像确实存在问题！！！赶紧改了改，一测，大样例过了！！！！！！！！！！加个freopen交了。
11:00 - 11:20        火速看T3，T4，但是感觉T3没啥思路，好像特殊性质也不会。T4感觉好像还可做，但是想不到一个复杂度靠谱的做法。
11:20 - 11:40         T4突然想到好像可以bfs，复杂度是 $O (q mn)$ ，感觉至少拿点分吧就直接写了。样例也是一遍过。交了。还剩5min，已经啥也不会了。