前言
因为过于摆烂,所以记录一下警醒自己。
赛时
8:30 拿到了压缩包,发现有一个文件夹里有一堆东西,很明显是交互题了。
开题,发现 T1 奇妙构造,然后没大样例,没 spj,一看到括号就头大,跳了。
T2 明显数据结构题,有人说背景和坦克世界有关,是 lxl 出的,大概看了看就扔了。
对 T3 比较感兴趣,认真读了题,没啥想法,似乎需要确定一个很好的策略?(后来发现其实并不太对)
想了想也没想出来啥策略。。。。。
当时有两个很莫名其妙的想法:
- 想办法多排除不合法的,最后在剩下的单词里随机一个;
- 直接在当前可能合法的字符串中找一个最有可能的返回。
回去看 T2,好像是三道题里最正经的。
想了想发现我会莫队,好像能搞到 $O(n\sqrt n\log n)$,一看数据范围,这能过几分全看常数啊。
其实这玩意要是想优化到 $O(n\sqrt n)$ 就是要把查询前驱后继的复杂度搞成 $O(1)$,然后前几天听过用链表+回滚莫队平衡复杂度的一道题,但我数据结构水平是真不行,想不出来怎么平衡复杂度。
写了个 set 做法,常数大到爆炸,$10^5$ 都过不去。
后来得知一个叫树状数组上二分的科技,然后写写写调调调卡卡卡,常数小了很多,在我的机子上跑 $10^5$ 需要 $3$ 秒,这下应该是有 $50$ 分了。。。
时间所剩无几,稍微想了想 T1,没啥收获,写了 $25$ 分暴力。。。
还剩一个小时,去肝 T3 吧。
想着先咸鱼一个纯随机选的算法,然后一直调到结束(?)
然后就很悲惨地结束了,到死都不知道怎么回事。
可能太着急了吧。。。。
赛后
听说 T3 乱搞能得很多很多分?
好吧,我没搞出来,也许应该多留点时间搞。。。
然后出分了:
$10+30+0=40$?????
哦我 T1 数组开小了啊那没事了。
那 T2 是什么情况?????????
为什么我少了 $20$ 分?????
罢了罢了,接着去搞 T3 了,真好玩.jpg。
总结
遇到陌生的模型转化能力还是欠缺啊(T1),括号序列转化为二叉树我确实想不到。。。也许需要有意去想办法转化?
T2 其实没啥问题,已经尽最大努力了。
怎么说呢,对题目难度还是没把握,T3 这种乱搞题。。。还是太谨慎了?也许应该大胆一点。
真有点《遇到交互摆大烂》啊,明明我也做过好几道交互题来着。
但是我并不是胆大心细的人啊。。。
小错误犯了一堆,以后应该搞一个注意事项合集了。