前言

因为过于摆烂,所以记录一下警醒自己。

赛时

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 这种乱搞题。。。还是太谨慎了?也许应该大胆一点。

真有点《遇到交互摆大烂》啊,明明我也做过好几道交互题来着。

但是我并不是胆大心细的人啊。。。

小错误犯了一堆,以后应该搞一个注意事项合集了。