考试总结（多合一）

0821

总览

212pts，还行（吗？）。还是挂了不少分的，主要是因为一些口胡的结论马上就用（当然，考试要结束时用绝对没问题），导致我本来可以拿到的一些分就在这样的情况下白白的丢掉了。

一句话：缺乏严谨的思考。

T1

96pts = 24 × AC + 1 × MLE

一道最短路+字符串的题。当时的想法一下子就是 Dijkstra，推了一下发现可行，于是马上写了起来，但是再分析一下就会发现确实会 MLE，救不回来的那种，主要原因是字符串太占空间了，结果题解用的是拆点+贪心，很大程度上解决了字符串的占空间问题。

总结：不要拿着看时间复杂度，可行性就开写，也要看空间复杂度。

T2

40pts = 10 × AC + 9 × TLE + 6 × RE

一道数学，和欧拉函数有关。事实证明，我连暴力分52pts都没拿满。最终也是需要一些数学证明才能做出来，还需要一些迭代函数的知识，只能以后再补一下数学了。

T3

24pts = 6 × AC + 19 × WA

明明是一个01背包的问题，结果被我乱瞪成了贪心，而且单纯的01背包还不行，还得针对多重背包进行二进制优化，感觉不像我考试的时候写得出来的。

T4

52pts = 13 × AC + 12 × TLE

字符串操作题，开始以为是trie树，后来看了一下感觉能用rope做（大雾），但是string的常数小，而且好写，所以最后还是用了string骗到了暴力分，正解是FHQ-Treap，还是位置平衡树（出题人编的，用平衡树维护序列，怎么会有人想着用这种奇奇怪怪的东西），好吧，对数据结构理解实在不清晰。

0822

T1

100pts

实在是水，就一个建图，跑最长路，或者DP，实在水。

出题意图：送分。

$\\\normalsize\tag*{\color{grey}\text{——by 题解}} \ $

T2

5pts = 1 × AC + 13 × WA + 6 × TLE

事实证明，我确实能想到正解，但只有一部分。

这种暴力更新的方法，最坏复杂度可能是平方的。我们对非树边按照权值从小到大排序。先处理权值小的，再处理权值大的。这样如果某个边的权值已经被修改过，那么后面的更新就不用重复修改了。

就在题解想着怎么在这里优化时，我：rand()不就好了。成功获得基本全WA的好成绩。

其实我代码在这里改成题解的优化就能A了。

T3

51pts = 17 × AC + 13 × RE

这是最不应该的一题，本来考场上已经想好了正解，结果打的时候发现会MLE，其实数据卡不满，数组开理论极限的$\frac{1}{4}$就能过的，我脑瘫了。

还有就是其实这样改后我是92pts，还有8pts是有一个数组名写错了，但是两个数组内的元素本就同源，所以还是可以拿到那么多分。

我的赛时AC啊~~~~~~~~~~~~~

T4

20pts = 特殊性质

题解好抽象，先用一颗线段树维护[l,r]的影响，再用单调栈维护a[r]对线段树的影响，写不出来，听都差点没听懂，差评。

总结

这次考试基本全是不该丢的分和不该丢的分，还加上听都听不懂的题解和差一点想出的正解，最想打死自己的一集。

0824

0827

0828

总览

最让我没想到的是这次考试考了珂朵莉树，而且我看出来了后还写挂了，最后连暴力分都没拿到，还是只能说明我的代码实现能力太差了。最后只有 T1 拿了 100pts，其他同学都打的暴力，最后分比我高（笑死，我咋这么菜），最后还是说明不要哦拿到题目上来知道正解就开始打，还是估计一下自己能不能打出来再说。

还有就是这套题是 LBY 出的，只能说题面 8 个锅是什么鬼，实在是看不下去，不比某个 CBC，虽然没给形式化题意，而题面 PDF 有 13 页，但是他的题面里没有表意不清的地方。最后这场比赛我也是拿了 100pts 就没了