心路历程
拿到题目之后先看一遍…
第一题好像可做(???), 第二题3w的最大匹配?貌似好神的样子就没去想, 第三题好像是很恶心的计算几何, 感觉写不到那里。
回头开始推第一题的式子, 推了一页一坨式子后以为自己get到正解然后开始写, 写出来wa样例, 感觉不科学啊于是手算样例算出来发现我的公式是错的…没有乘上组合数。但是乘以组合数复杂度就不对了。
有点烦躁, 去想第三题, 半个小时一无所获。
心慌意乱, 和JeremyGuo比手势:
Hineven:[第一题?]
JeremyGuo:[会了!]
Hineven:QAQ
然后和Ender互比手势:
Hineven:[第一题?]
Ender:[OK了。]
Hineven:QAQ
瞄了瞄SunIsMe的屏幕发现他好像在做第二题, QAQ大家都会第一题就我不会。。。第二题和第三题看起来那么神肯定不可做, 继续杠第一题题目那么难杠出来就是胜利…
于是理所当然地杠了两个多小时, 不出所料地杠爆了。
不行了只能弃了先第二题写个暴力!看到数据貌似有梯度想了想怎么骗分怎么压图, 但是短时间没想出来, 权衡匈牙利和最大流之后决定写最大流。然后慌慌地去写第三题, 写了个10分暴力回头写第一题暴力, 当时没怎么想就按照我先前推出来的公式加上组合数暴力计算分子分母, 想了一会发现分子和分母都会炸double于是选择取log加上牺牲精度写了个45pts的暴力, 然后交完就觉得自己已经是条咸鱼了…
事后
Hineven:(兴奋地)JeremyGuo你第一题怎么做的?(想了好久都没有想出来…)
SunIsMe:同问。(Hineven:原来你也没有做出来…)
JeremyGuo:这个, 你先画一个矩阵…
SunIsMe, Hineven:这个矩阵不是N^2大小的么?
JeremyGuo:没问题啊, 复杂度O(N^2logN)啊。
SunIsMe:矩阵乘法不是O(N^3)的么?
JeremyGuo:嗯?是么?
Ender使用暴力插值求值计算多项式求解第一题, 只有Ender的方法是正确的。
总结
第一题的正解是循环矩阵乘法优化, 没学过涨姿势了, 早知道就不杠第一题了…我第一题log炸精度只拿了20pts, lsy等人表示全部写的dp暴力稳稳45pts, 我最后慌慌张张思维僵化在先前的死路上, 没想过更加简洁方便的算法…
次要失误是第一题没有验证思路正确性。第一题手算样例只会花两三分钟就可以Hack掉我的错误思路, 然而咸鱼我的做法就是一阵激动马上写代码, 代码细节很多(为了防止炸double)耗费大量时间(40min), 写完代码过不了样例才发现自己的思路是错的, 血本无归亏大了…还是太激动了, 不过稳。
然后最主要的失误是一开始和第一题杠死了。
当时抱着这样的心态:大家都AC了我一定也可以AC!大家都AC了这题一定比后面题目简单。
误判了题目难度, 实际上没人AC第一题, 殊不知第二题如果花点时间挖掘性质就可以优化建图然后AC掉。一开始对第一题得分抱有很高期望, 后两题草草看完没有经过太多思索就去切第一题。在第一题上画的时间越多, 自然越陷越深…导致第二题几乎没怎么想正解/优秀的骗分(实际上正解的复杂度也不对)。对于想不出来的题目还是不能依依不舍…这种难度的考试卡死1h+可能就已经是极限了吧。
就算要杠正解也得先保证暴力分拿满, 感觉难度偏高或者状态不佳时可以先把暴力码了。三道题暴力写稳可以有45+55+10pts, 第三题骗分还可以多拿20分, 于是初中选手吴凯通过各种暴力姿势碾压全场…然后我就因为花太多时间杠正解(然后没杠出来)暴力写的匆匆忙忙没能保底炸死了…
Join the discussion