概述

期望 $100+100+100+20=320$,实际 $100+100+80+20=300$。没怎么挂。

赛时

按照计划,打算把每道题都想一想。

于是看到 T1,是个数学题,尝试乱推无果,注意到 $n\leq 10^{18}$,那就有趣了,往矩阵快速幂上靠(((

然后稍微一推发现是个带水题,直接开写。

然后矩阵板子写挂了,然后发现是构造函数没 memset,改完就过样例了。时间还有,写了个线性递推来对拍。差不多在开始考试将近一个小时时搞好了。

去看 T2,完全图三元环,正着乱搞无果,于是考虑转化,用所有减去不合法。

所有的三元环随便就推+找规律蒙出来了,然后不合法的乱推了一下找找规律似乎也找出来了。快速写完,然后写了个 $O(n^3)$​ 暴力对拍。没拍出来错误,放心了(

然后发现 T1 拍出来问题了,仔细一看是正解的特判 $n=1$ 和 $n=2$ 的情况写反了,我谔谔,赶忙改过来,然后接着拍 $n=1\sim5$,没啥问题,放心了(

这时候才过去两个小时,感觉优势很大(((

T3 不是很好做,T4 更不懂,都没读懂题更别说暴力了。

先莽 T3,想了很久,找规律发现实际上只需要选择 $n+m-1$ 个点,然后想到了一个大概是 $O(nm(n+m)\log (nm))$ 的纯粹乱搞做法,这个能过 $50$​ 分。

看时间很充裕,接着想正解(((

瓶颈在找点上,再优化一下,想了一个莫名其妙的做法:直接把所有点都加到堆里,然后取出来看这一行和这一列有没有必要选,可以 $O(nm\log(nm))$​​,想过有点悬,然后发现这个做法取出来判断不是很好实现,又画了画图发现选一个点实际上就是在行和列之间加边。。。

那不如直接枚举行和列,就能搞到 $O((n+m)^2)$​。。。。

写完之后也不想写暴力了,分数应该还算可以,想莽一下 T4。

然后思考许久发现我是真不会。。。。。

注意到有 $20$ 分是 $n\leq8$,于是花了 $20\text{min}$ 手算了一波跑路了。。。。

赛后

T3 MLE 挂了 $20$​ 分,看来 long long 不能随便用啊= =,还好没爆零,这必须得注意。。

然后发现会TLE,需要稍微卡卡常(取模,long long

发现 T4 大数据中有一个是样例,我没输出,于是没拿到这 $10$​ 分。。。

发现 T3 是个最小生成树,第二次遇到这种题了,得注意对这种怪异题目的图论建模+套算法。

T4 真不会,不冤。。。

总结

该骗分还是得骗分,不骗白不骗。。。

空间得算准了。。。。。。。。

这次没爆零还算可以,但是要是有一天因为 MLE 爆零,那我估计就得难受死了。。。。。

换句话说,对于空间复杂度和时间复杂度都是 $O(n^2)$​ 的算法,要注意空间的问题,毕竟此类题目一般 $n=5000$​​,很容易 MLE。。。

要注意 vector 的空间常数,存完全图时不如邻接矩阵。

当复杂度逼近 $10^8$ 时要注意常数。如果可能,减少取模以及 long long 的使用。

今天因为想正解比较顺利,没有怎么写暴力,不过看来对拍还是很重要的。。。

莫名其妙题目的图论建模!不管是转化为图论模型还是补集转化,总之转化思想很重要。。。