10月15日
这次考试题目偏难。
考试开始后先看完了三道题, 然后发现竟然一道都不会做, 看第一题数据范围很大的样子感觉是智商结论题, 代码一定很短于是就想了半个小时, 毫无头绪, 然后去看第二题稍微想了一下感觉很分块但是没想出稳定复杂度的解法。
对第一题恋恋不舍…感觉换换脑子一定可以想出这种题, 回头思考第一题二十分钟依然无果…于是想打表找规律, 又花了20分钟没搞出来, 就暂时放弃了。
想第二题, 很快想出来, 写完题目和对拍花了40分钟, 对拍出错, 发现数据生成器有问题, 然后好像拍上了。
接下来想第三题, 开始推递推式, 推了20分钟之后发现满分递推需要写中国剩余定理, 时间只有60分钟了感觉写了也调不出来果断放弃, 尝试写50分暴力, 然后又花了30分钟发现50分暴力答案错误, 感觉时间不够于是就先写个20分保底, 回去写第一题60分。
第一题写完就只有20分钟了, 花这些时间检查了一下第一题暴力和数据表对拍了一下, 然后剩下5分钟文件输入输出…noilinux开成lld…
感觉考得好炸啊, 预计180分, 但是第一题错了一个点, 第二题错了两个点, 没有AC。
总结
时间分配上太偏重第一题了。
试卷拿到应该先看看一共至少能拿多少暴力分, 这样做题时想不到正解就可以权衡取舍了。
以为肯定能想出第一题的, 但是这种题方向不对就基本没戏…后来确实第一题AC的人也非常少, 一般来说想这种智商题最好换换脑子进行多次思考, 一次不要超过20分钟不然就钻到牛角尖里去了, 40分种想不出来必须果断放弃啊…不然在花更多时间思考也基本上没有结果。
然后一般比较难的比赛暴力分都会给得比较好的, 发现题目比较难应该先看看暴力又多少保底, 第三题暴力50分没拿完有点可惜。
另外一大失误就是第二题。第二题又一个细节没有考虑到, 当时对拍其实拍出了错误, 但是我跑了一百多组之后就没关了于是没有发现QAQ, 对拍期望效果其实没有想象的那么好, 还是得一直开着(反正电脑有不会卡死…)。
10月16日
考试题目确实比较简单…
首先开考自然是把所有题都看一遍, 然后肚子痛…去上完厕所回来发现都会了, 而且代码难度也很小的样子?
当时心情是这样的:
0.0太好了大概可以AK了!
回来后感觉第一题很多细节…小心翼翼写完发现写不成对拍, 反正时间那么多可以回头再检查。
然后快速搞完第二题, 发现还是写不成对拍…于是仔细检查了代码。
第三题是去年多校赛一道题的弱化版, 快速搞完, 这时才过去1个小时, 时间非常充裕于是写了第三题对拍开始对拍, 一下就拍上了。
回头检查第一题, 手造了几十组数据感觉没有问题, 感觉第一题对于空格的要求非常诡异…于是又看了一遍题目没有发现理解错误, 然后又手造了十几组数据, 重点放在检测空格格式上。
第二题非常短, 造了一些小数据和特殊情况, 没有发现问题。何老师说我们10分钟之后就交了, 鉴于前一天第二题的神奇经历, 看了一眼第三题发现没拍出错, 感觉这么检查已经很稳了(flag)…然后就发了一会呆, 最后五分钟文件输入输出…就交了。
然后就爆炸了0.0
总结
题目确实没得说…应该AK.
失误在第一题和第二题。
第一题确实和我想的一模一样是个细节题…但是还是爆炸了, 竟然是因为题目看错了(还看了两遍QAQ)!
题目中说:
合理表达式前后可以加入空格
我的眼中:
合理表达式后端可以加入空格
考试的时候就觉得这个要求很诡异但是还是没有发现…自己第二遍看题时算是走马观花同时带上了很强的主观意识吧, 然后就以为没有问题了QAQ, 虽然题目已经看过一遍, 但是依然要重新好好读题像第一遍读一样啊…不然读几遍都没有效果的…
第二题…这个实在有点玄…字符串哈希爆了, 考试时不知道为什么选了一个奇怪的大质数作为哈希种子(平时都没尝试过), 结果就炸了。考试时求稳应该是第一要务, 写哈希之类的玄学玩意应该选取平时经常使用的常数, 不然可能脑袋一抽就炸了…
解释一下为什么哈希会爆炸
字符串哈希:
hash = hash*SEED + str[i]
这里hash选择用unsigned自然溢出, SEED选取998244353(BZOJ素数)。
很不幸的, 998244353这个素数还可以拿来做NTT, 它在二进制下的表示非常特殊:
111011100000000000000000000001
注意到中间的一大串0了吧…
如果选择自然溢出, 那么SEED的平方就可以让大量信息直接溢出丢失, 造成哈希值近乎只存储了str之和…
当然就爆炸了…如果不选择自然溢出而是对质数取模, 虽然牺牲了时间但是应该更稳一点…题目不卡长最好使用对质数取模。
Join the discussion