【2020.12.01提高组模拟】A组反思

105,rk45

T1

赛时一开始先打了(m=0)的情况,也就是普通的卡特兰数,然后打了暴力,样例过了,把样例改改就不行了,原因没有保证是枚举的是合法的出栈序列
得分:(WA&TLE10)
正解是从原本的递推式(f_n=sum_{i=1}^nf_{i-1}*f_{n-i}),这里枚举的是最后出栈的数,然后扩展到这道题,将(dp)转为区间(dp),然后就有了(O(n^3m))的做法,优化至(O(n^3+nm))……思考中

T2

名字如此高大上,肯定不会用莫队的(毕竟(noip)不考)。赛时想着直接按照题意暴力,(query)的时候用个右指针持续维护答案。
得分:(TLE40)
正解是推柿子,线段树维护

T3

说到莫反估计也不会用,因为这是(NOIp)lus模拟赛。赛时没思路,直接上(O(n^2m^2))暴力
得分:(TLE15)
正解是推柿子,然后高维前缀和与高维前缀差,不会……

T4

赛时打表(n,mleq2),其余盲猜01010
得分:(WA40)
正解是先增加一行一列,估计上界,然后从(n=m)的情况推到(n<m),懵

反思

T1:暴力一定要多想,暴力分拿满名次就可以往前很多
T2:多推柿子
T3:推柿子,把柿子推成柿子汁
T4:-1之类的可以尝试加回来

原文地址:https://www.cnblogs.com/Livingston/p/14068981.html