考试总结 模拟55.5

T1「贪心」

看了25分钟模了几个样例,误以为剩的人不会积累下来,然后打了个正解和暴力对拍一直AC,然后自以为已经A了

WA80,非常感激出题人的数据
正解:感性理解一下如果先打省的多的点,

那么下一个需要新加的不会更多,

而sum_a一定,所以直接排序就行了

题解写出锅了,应该是从大到小排序

T2「组合数学」

这分明是一道高考数学题,$(C_n^m)^2 = C_n^m*C_n^{n-m}$

接下来接着找数学规律是徒劳的,那么就可以考虑实际意义,

也就是现在n个物品里选m个,再在另n个物品里选n-m个,

那加和就是$C_{2n}^m$

T3「回文串」

上一次考回文是个数学题,这次考场上yy了好几种回文串的求法,

然后写了个时间复杂度$O(n)$空间$O(n^2)$求lr是否为回文串,正解是用g[i+1][j-1]推到g[i][j]

然后我用了排序和lower_bound $O(n^2logn)$来求和,

用dp就可以很简单的求了f[i][j]=f[i+1][j]+f[i][j-1]-f[i+1][j-1]+g[i][j]

愿你在迷茫时,记起自己的珍贵。
原文地址:https://www.cnblogs.com/casun547/p/11616188.html