%你赛总结

zyywzw · 2018-10-31 16:01:49 · 个人记录

• 两天比赛打下来，唯一发现的是自己的傻。。。
• day1极度沙雕，T3看完以为是不可做题，随手跑了O（n）个Dijkstra，却发现如果跑K个就有60分，而T1是个大%你...大样例都不给，出题人我恨你.
• day1估分:100+52+60=212
• day1实际得分：25+52+10=87
• day2比较坑B，T1推了3个小时式子，最后才发现矩阵不可做，是SB递推，结果T3只来得及打个表，5555，时间够的话我可以写树剖，T2是个背包计数，不造是什么玩意...
• day2估分：100+0+10=110
• day2得分：100+0+10=110大众分吧
• upd:11-01%你赛day1总结，T1是个沙雕题目，但是我不会。。。蛇皮推杨辉三角，O(n^2)在n=2000的条件下居然过了！！！原因是我开了long long，炸成负数又运气好炸了回来，下次开unsigned long long
• T2是个二分+树上贪心，怒日一波贪心，好像很可做的样子，估了一下复杂度O(nlogn)，诶，莫非要切（其实是O(nlogn^2)只不过我沙雕漏算了LCA而已），然而还是跑了100pts，老师电脑快，我也没办法啊。
• T3不会，怒日一波n^n爆搜，mdzz挂了，爆了long long。
• day1估分：60+45+20=125
• day1得分:80+100+0=180
• 11-02 day2更加蛋疼，大众分140，而我100
• T1沙雕，先写了一波O(nm)组合数，裸的60分，但很蛋疼的我改成了O(n^2)递推，蛋疼。。。60->30.后来发现正解是结合杨辉三角形递推组合数的和的规律∑i=(0...k)C(m,i)=C(m+1,k+1)，这个由杨辉三角形可以推出来。
• T2更加沙雕，一眼最小生成树+连额外边，正解是连一堆基环树，我那做法只有50pts，结果沙雕，为了判重边加了个Hash，自己把自己坑死了。。。
• T3只会暴力，这次暴力没挂。。。30pts走人
• day2估分：60+50+30=140
• day2得分：30+40+30=100
• 结果两天下来总分还是没过300，主要死在了day2上
• 同时orz——wph学长，day2直接AK，一天分数比我两天多TAT