9.4总结

发表于 分类于 ， 阅读次数： 本文字数： 631 阅读时长 ≈ 1 分钟

今天是5校联考的第一天,然而我犯了很多小错误。

T1：感觉像是数学问题，然而并没有发现什么规律。最后还是想着暴力，去打搜索，每一次向上有四种转移。但是我计算的时间复杂度计算错误。所以我认为拿不了太多分。最后，交了搜索，只拿了30分。因为我犯了一个错误，没有把max开到long long的最大范围，只开到了int的最大范围。改一下这个可以拿50分。最后与100分失之交臂，是因为我搜索的减枝做的不是很好。一个很给力的剪枝（r-l+1>l）没有发现，这个剪枝是答案可行性剪枝。

T2：一开始想到与题解类似的想法，但是因为无法处理好合法串中有可能在一个位置右括号多余左括号，最后面发现我完全想错了。所以就抛弃了这种方法。转而向题目所给的（A）与AB方向想，先找到最简单的符合条件的串，再一次扩展，就能把这个字符串中多有的合法子串找出。最后我先打了个暴力，然后就去打这种方法。但最后因为时间不够没有调出来。只不过我觉得调出来也应该拿不到满分，因为有一些东西可以与处理出来，一个个构造相加太慢了。后面是看到一个人的程序，他的想法和我的类似，只不过他通过多个预处理实现了出来，每一组数据的时间复杂度只有O（len）。

T3：这道题非常的神奇，因为完全摸不着正解的头绪，蒟蒻只能打搜索了，然而又一次我的搜索打挂了。我并没有测多组数据，然后多组数据就挂了。最后面发现是哈夫曼树，然后跟着WWT大神的证明听了一遍，然后又请教了一下LB，最后将这道题的解与哈夫曼树相同性的证明弄懂了