这次测试,是福建第三中学的某同学出的,感觉难度还行吧,今天我就浅谈一下这场比赛的时间分配与心得
打开题目,看到了T1,这题是一道计数题吧,感觉心态一下子就崩了,100%的数据点应该是组合数学+容斥原理吧,我是不太会做,于是使用了STL中的next_permutation,这样的时间复杂度是O(n!),只能拿下20分吧,赶紧喝口水冷静冷静,发现写搜索可以加上剪枝,可以减少大概三分之一的子问题,于是写了一发大搜索,运气好的话应该能拿40分吧。
等等,突然看见这道计数可能有一点规律,于是我拿出草稿纸演算,浪费了40minQwQ。
1h就这样过去了,我开始看T2,这题看上去正解是算割边+乱搞?但是我写炸了。。。。。。于是老老实实写暴力,枚举割边使用传递闭包判断连通性,过了所有大样例,但是这个算法的复杂度最好情况只能拿下30分,等等,判断连通性不一定要用传递闭包,我记得丁霸以前写过一个并查集判断连通性的,于是重构代码,写了一发并查集
emmm,现在这个代码最好情况能拿60吧,最坏情况应该还是30分
2h过去了,我开始看T3,这题就是NOIp2015的斗地主升级版啊,多加了几种操作,还搞了个多组数据。打扰了。。。。。。于是开始乱写乱调,各种剪枝什么的全上,但是,第三组大数据WA了,多组数据什么的是真心烦人,于是开始乱调啊之类的,3h就这样过去了
还有最后0.5hQwQ,检查一下文件,再找一下T1规律,就这样交题了。。感觉这套题真心不是提高组难度啊。。至少要来个大水题送送温暖之类的。。。。。。
最后听hyf大佬说她也没找到T1规律,有木有很轻松QwQ
这次最高100+,最低50吧。。感觉还是写暴力最好了,可惜下午要上课,听不到讲解了QwQ