2019.08.12【NOIP提高组】模拟 A 组 总结

心态巨崩。。。
考场:(40 + 0 + 10 = 50)


T1:

刚看完题后一点思路都没有,那(n)那么小肯定有问题。
后来想了想就死刚了个分治+(DP)上去。。。
结果有一个地方横纵坐标反了,(RE40).
改后(TLE60)。把数组开小一点(TLE80).
(max)(min)函数手打(AC)且快了(200ms+)。。。
(™)是卡常?!


T2:

看完题后仔细想想发现好难啊,打了个(假)贪心。
正解是扫描线+线段树。


T3:

看完题一脸崩逼,直接(n=1)
正解是(DP)。从题解的证明可得,我们要找一些连通块,使得其每个连通块内两遍都相连。求最小连边数。
我们设(f[S][i])表示状态为(S),当前连通块的左边点数为i的已搞出来的连通块的边数的最小值。转移即可。


总结:

要注意行列坐标,不要交换了。(特别是这种行列坐标范围相差那么大的题,会RE的)
在使用memset的时候要看看数组开的大小,不要TLE了。
(N)(200000)或以上的时候要注意一下常数优化。
对于一道题,要多想想,不要只局限于一点。
还是最后一句话,能水多少是多少。

现在: (100 + 100 + 100 = 300)

转载需注明出处。
原文地址:https://www.cnblogs.com/jz929/p/11342187.html