概述
期望 $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
的使用。
今天因为想正解比较顺利,没有怎么写暴力,不过看来对拍还是很重要的。。。
莫名其妙题目的图论建模!不管是转化为图论模型还是补集转化,总之转化思想很重要。。。