求一个zju 3005 Bacteria Colony 的算法分析~~谢谢

显示全部楼层 · 2010-7-23 16:53:41

zju 3005 Bacteria Colony这一题应该怎样去做，我不是很懂？求一个算法分析！谢谢

千问 · 2010-7-23 16:53:41

刚开始做的时候糊涂了，学了离散化后硬想离散化，结果效果不好，点多了，其实离散化不好。后来想到后往前扫描，能覆盖就覆盖，但是竟然写成递归的，严重超时了。经CP启发，发现读一个，就可以做往前扫的工作，并且重新分原来的矩形快。晚上想了大半晚，发现，一个矩形，覆盖旧的矩形，他最多只会重生成8+1块，而且是4个角都用到的情况，所以，这样下去500个矩形，最后也就500*8左右的矩形块，500*8*500的复杂度完全可以。后来又发现，如果4个角都能用上的情况，那么前面就必然有4个矩形没分裂成8个，反正最终的情况就是1个矩形最多分裂成4个，空间开4*500就可以了，并且最后提交也没RE，所以证明这样做是正确的。具体做的时候，我用了滚动结构体数