27.3.18 考试小记[待补]


今天考了两场好累啊QAQ。第一场俩原题,基本上算比较顺利,但是没啥意思。第二场T3想复杂了码了4K,而且空间没保证,被卡了内存,心累。

题目暂时还没有改完,先把改完了的而且比较有意义的写一写吧。

 

B-T3

树上数颜色,强制在线,路径查询。一眼log^3,目测50~70,去想正解。被int的权值范围冲昏了头脑,认为树剖的性质可能并不够,就彻底抛弃转向普通的DFS序,写了静态主席树+BIT套动态开点的线段树,时间复杂度O(nlog^2n),空间复杂度O(nlog^2n),但是空间复杂度中的一个log能达到31(呵呵),本机测得极限数据2s+,内存没算然后就不管了,最后惨遭MLE爆零。

正解的思路曾一度被我抛弃,因为不需要维护权值的大小关系,所以就可以用map离散化,然后直接做就好了= =。

 

感觉近半个月以来我日常考试发挥的都还好,基本上稳定前三,波动不是很大,但是这次考试却因为这道题彻底翻车了,所以这道题的爆零经历让我不得不重新思考一下自己的做题策略。仔细想想,感觉还是我遇到了新题就会愿意去多骗一些暴力分,如果头绪比较多的话还能冲冲正解,但是一切都是建立在分段算分打暴力的基础上的,而如果我遇到数据结构,有时候就会过于“激动”而去想奇奇怪怪的偏门做法,考场上还自以为写出了优秀的做法,实际上风险却很大。所以,不论如何,如果考场上想出了比较复杂/偏门的做法,一定要再三思考有没有更简洁的做法,然后再写啊。

 

B-T2

给出一棵树,要求在树上选一些点,满足每个点要么被选择要么被最近的选择的点覆盖,选择点有一定的代价,被最近点覆盖也有一定代价且随距离增加而单调增。

显然这是一道DP题,但是状态的设计比较麻烦。设f[u][x]表示离u最近的被选点是x,u和u的子树都被覆盖的最小代价,被选择的点可以不在子树中。

那么,我们在计算一个点的f值时,先枚举最近点x,再枚举每个儿子的子树在这种情况下的最优解,如果当前最近点在儿子的子树中直接用f[v][x]更新,否则枚举儿子选择的的最近点。

考虑一下这种做法的时间复杂度。最坏情况就是在枚举儿子的时候又枚举了两次最近点,但是这种情况只出现在每个点作为儿子时,所以最多有O(n)次这样的枚举,每次枚举相当于枚举子树外的点对,所以是O(n^3)的。

声明:Narcissus' Blog|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 27.3.18 考试小记[待补]


Narcissus | HZOIer | zhuohaoyu1228@gmail.com