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

发布日期：2021-05-06 15:40:53 浏览次数：24 分类：精选文章

本文共 816 字，大约阅读时间需要 2 分钟。

105，rk45

T1

赛时一开始先打了 $m = 0$ 的情况，也就是普通的卡特兰数，然后打了暴力，样例过了，把样例改改就不行了，原因没有保证是枚举的是合法的出栈序列

得分：

WA\&TLE10

正解是从原本的递推式

f_n=\sum_{i=1}^nf_{i-1}\times f_{n-i}

，这里枚举的是最后出栈的数，然后扩展到这道题，将

d p

转为区间

d p

，然后就有了

O(n^3m)

的做法，优化至

O(n^3+nm)

……思考中

T2

名字如此高大上，肯定不会用莫队的（毕竟 $n o i p$ 不考吧）。赛时想着直接按照题意暴力， $q u e r y$ 的时候用个右指针持续维护答案。

得分：

T L E 40

正解是推柿子，线段树维护

说到莫反估计也不会用，因为这是 $N O I p$ ~~lus~~模拟赛。赛时没思路，直接上 $O(n^2m^2)$ 暴力

得分：

T L E 15

正解是推柿子，然后高维前缀和与高维前缀差，不会……

赛时打表 $n,m\leq2$ ，其余盲猜01010

得分：

W A 40

正解是先增加一行一列，估计上界，然后从

n = m

的情况推到

n < m

，懵

T1：暴力一定要多想，暴力分拿满名次就可以往前很多

T2：多推柿子

T3：推柿子，把柿子推成柿子汁

T4：-1之类的可以尝试加回来

上一篇：【2020.12.01提高组模拟】卡特兰数(catalan)

下一篇：【2020.11.30提高组模拟】剪辣椒(chilli)

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！