[ioi2012] ideal city

考虑把网格的四条边看成图意义上的四条边,那么问题就相当于一张有环图中的两点之间距离之和

同列/行的格子可以缩在一起,那么就变成了一棵树,树上求距离之和非常简单,点分治+FFT就行了考虑记s[i]表示第i个点为根的子树的权值和,那么这条通往父亲的树边的贡献就是s[i]\times(n-s[i]),时间复杂度O(N)

难点在于转化为树,然后缩环这种思想。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注