UOJ Logo zgjkt的博客

博客

【GDKOI'2017'】总结与反思

2017-02-20 13:08:09 By zgjkt

这是ZGJ升上高中之后,考得很好的一次比赛,虽然也有很多遗憾



Day0

中午看了看以前的题目,心态不错

晚上回到家已经十点了,困得不行



Day1

压缩包密码是"扎西德勒",这是一句祝福语

这次有个新东西"check.pyc",可以帮你检查文件名,避免出现低级错误,好评

打开之后先扫了一眼题目,感觉都挺可做的[捂脸

做题顺序123431


看完题目之后把第一题想复杂了,一开始我还以为是KD Tree

捂脸熊

然后非常不自信,按着部分分的数据迅速搞定,不过数组大小开了100%

期望得分:60,此时剩下3h


刚好在想第二题的时候,宣布更改题面,萌新瑟瑟发抖

想了很长一段时间,感觉后面的题更可做,至少先把暴力思路打出来

还是不要在一道题上花太多时间去思考

期望得分:60,此时剩下2h


还剩下2h,我只打出两题暴力,其实我是很慌张的

抉择了一下先搞第三题还是第四题,和第三题刚了十分钟之后转向第四题

此时剩下1h50min


因为心态不是很稳,第四题只想了十分钟不到强行用DP去做

写了半个小时越写越卡顿,发现这个递推式其实有一个关键的地方没有考虑

体积和质量,两个元素?优先级?还是根本没有优先级?

这很尴尬,但是已经没有时间再思考DP的正确性了,我迅速把它改成一个容错率较高的贪心

看了看数据范围,有部分数据是只用考虑其中一个元素的,顿时放松了些

期望得分:50,此时还剩下1h


回头去看第三题的时候目光已经不一样了,无视了100%的数据

出考场之后我才发现这是我本次比赛犯的最大错误之一

当我发现看上去特别简单的数据加起来有50分这么多,真的可以用一个成语来形容

虎躯一震

然后疯狂推公式,找规律,剩下30min时,无果

但是可以打表,然后带着遗憾放弃了这道题

期望得分:???


最后时间我在检查第一题,感觉应该这个60分相当稳

出来之后和同学聊了聊,好像大家都说第一题暴力即是正解

原来是签到题???

同时发现自己第三题忽视了一个很重要的东西[嗨呀好气啊

题目保证在100%的数据里,gcd(n,m)=1


下午听讲评的时候,记得大概是这样

T1签到题,T2括号序列前缀和去想,T3神奇插头DP

T4记忆就很深刻了,具体看我朋友圈有一条

“下面这个同学80ms跑到了八十分,让我们听一下他是怎么水到这么多分的”

“blablablabla,其实我看错了题目条件”

“再下面这个同学仅4ms也跑到了八十分…”

“我和刚才那个同学一样,也看错了…”

“让我们请上这位同学,他0ms跑了七十分”

“我也看错了…”

“我觉得这道题不用再讲下去了”

最终得分:90+50+10+20=170(至今不知道第一题怎么跪的十分)



Day2

压缩包密码是"with no regret"

做题顺序:123


看完题目就花了半个小时,主要是边看边想花了点时间

第一题的就有点感觉这题难度应该不大

第二题的第一想法,贪心???

第三题的第一想法,欧拉函数???

第四题感觉非常复杂啊,果断放在最后

此时剩下:3h30min


开始怒推第一题公式,先画了个维恩图

做容斥的时候,先用图形概念表示一下不容易出错,反正也就1s的时间

非常工整地推出O(n)的递推式

期望得分:70,此时剩下:3h


其实只要再化简一下公式就可以切掉第一题了

当时想着,很多人应该都可以推出第一题满分做法,在这里放弃三十分很吃亏

然后就有点急躁,潦草无比的字迹写满了草稿纸,终于推出O(1)的公式

外加要取模等细节操作,边写边看草稿纸特别慢

居然花了一个小时!!!

期望得分:100,此时剩下:2h


比第一天同一时间还慌,而且还担心自己推出的公式是错的

但是看第二题的时候突然想到了一个贪心

把每个人的二元组(ai,bi)存进一个数组,同时把逆序的(bi,ai)也存进去

以第一个数为第一关键字,第二个数为第二关键字从小到大排序

当时想到如果一个人的bi特别大,在与别人ai相同的情况下尽量放后会更好

然后扫一遍可以过样例,也不知道能拿多少分

当时心态其实稳了很多,毕竟有玄学贪心加成

期望得分:???,此时剩下:1h30min


终于开始思考第三题,感觉二十分可以迅速拿到手

完全是能拿多几分就直接写了再说

期望得分:20,此时剩下:1h10min


做了一下艰难的抉择,看了一眼第三题后面的数据大小

感觉不一定能继续从这题拿到很多分了

主要还是知识点不扎实,明明学过欧拉函数,但是却不记得能用它来求互质数的和

要是记得,其实完全可以花10分钟再拿走三十分的

但是想起dwj学长说过:“当你知道有一道题得分可能会占你的总分相当大的比重时,就一定要确保你拿到这道题的分。”

于是我转头去对拍第一题,共计花了接近三个小时在第一题上


出来之后还是问了一下第二题正解是什么

二分图,网络流

???

我立刻想起来我做过类似的一题

第四题听说暴力也挺长的,没去尝试...


下午听讲评的时候,只记得第三题有个同学上去表演了一波炫酷反演魔术

提前发了成绩

最终得分:100+60+20+0(看到第一题没有爆炸就感觉还好)



两天总分:170+180=350,可惜NOIP没考好,离省队还有很远的距离

未来的日子仍需努力

稍微总结一下

这次考试还是很依赖于玄学贪心和强行暴力

看不出二分图很遗憾,没想起欧拉函数的性质很遗憾

以后训练做题,尽量要看出一道题的本质模型

至少也要学会如何简化题目

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。