12省联考2019口胡

D1T1,超级钢琴 + 可持久化01trie。

T2,sam上子树优化连边,注意有一堆坑就是多个长度不同的串可能在一个节点...然后长度相同的串在一个节点没影响...然后子树连边的时候别把路过的节点的len值也加上了...

T3,什么SB题guna。

D2T1,只想出了个SB背包套背包,比搜索跑的还慢,非常自闭...

T2,链的时候贪心,然后扩展到树上,注意写法,无论怎么来都是一个log的。

T3,神仙题,溜了。

总结:

D1T1T3不错,T2没写暴力连边的分,沉迷写正解然后一个地方写挂,10分。

正式考试没拍过的代码一定要数据分治!

D2T2又因为一些奇奇怪怪的东西爆了25分(指STL)。还是手写最靠谱。

T1肝了几个小时没写出背包,只有搜索,只得了10分...这题最惨。

T3正常操作12分。

合理分配时间!不求有功,但求无过!

orz被吐槽总结太少于是重新来写一遍。

day1的时候,先看完3题,t2t3看起来不是很可做,先写t1。一个半小时拍上,极限数据1.5s多,感觉稳了。

然后开始分析t2,发现是后缀自动机上子树连边 + 拓扑序DP。预估了一下感觉这题可以做,于是直接开始打正解。

过了一段时间,打完了,发现过不了样例,开始手动调试。

此时出现了第一个失误:发现情况不对之后应该赶紧写暴力 + 数据分治,然后写t3暴力,最后回来写t2正解。

我继续写t2正解,并在考试还有半个小时结束的时候过掉了三个样例。此时由于既不会造字符串数据,也没写暴力,于是没有任何保障的交了一个过了大样例的程序上去。

此时出现了第二个失误:我过于信赖大样例。实际上没对拍的程序写错风险极大,我应仔细静态查错。

剩下半个小时,我花15分钟写了t3的12分,并用15分钟检查文件夹,文件名之类的地方。

day2的时候,先看完3题,发现t1是个计数,t2是个树上最优化问题,好像比较可做。t3一脸不可做。

于是写了t1的搜索,开始分析t1,发现很类似背包。于是写了个iabc的背包。但是转移的地方没想清楚,导致时间复杂度过大,且答案错误。此时时间已过去2个多小时。

我急忙去看t2,分析了一下性质之后写了一条链的部分和暴力枚举。然后看t3,写了一点暴力和特殊性质的12分。

此时发现还有1个小时,我再思考t2,发现链的部分分好像可以扩展到整个树上贪心。于是写了一个用pq的贪心。

剩下的时间想了想t3,不会做。开始检查文件夹,文件名。

主要失误:t2没仔细分析时间复杂度,也不知道pq的时间复杂度。t1写之前想的不够清楚。

原文地址:https://www.cnblogs.com/huyufeifei/p/10666920.html