我在这里对我今天在牛客考试中进入洛谷做出深刻的反省,我不应该在考试的时候上与考试无关的网站(洛谷),保证没有下犯,在该做什么的时候就做什么,分清主次。
10.7 noip多校联考与牛客CSP-S总结
noip 联考
T1
是一道类似于概率计数DP的题,统计概率。通过题目给出的信息,可以发现使用概率,而统计又让我们想到了DP。
T2
考场上想了很久的这题,发现可以通过维护区间最值的方法来剪掉许多无用的决策,而又因本题的特殊性,导致了正确的决策比错误的决策要少很多,可以有效剪枝。
其实题目可以转化为扫描线问题来求解,使用树状数组+扫描线。
T3
看到这题感觉就是个博弈论,但只推到了分成两个连通块,以及都是完全图,但没有想到可以以奇偶性来分类。
T4
在考场上发现了 k=1 的特殊性质,求了前缀和。
实际上这题可以用扫描线扫一个直方图,并对每个条来统计答案。
牛客CSP-S模拟考
T1
就是一个求二次函数顶点的问题,求出二次函数的对称轴并带入求值即可,但需要分类讨论0的情况。
T2
求 max 的操作的优化是比较好想的,分类讨论一下字符串是否全部相等,并用第一个字符去求答案。
求 min 的操作的优化需要对最后三个字符进行考虑,判断是否相等,并算出答案,难点在于为什么考虑最后三个字符是对的。
T3
一道感觉比较难的博弈论,考场上只想到了 k=1或2 的做法,就是将它们放到一个格子中,保证必胜。
T4
考场上感觉可以将问题转化为差分约束系统进行求解,但是它们两所求解的问题本质好像有点不同,没有想到如何转化。