首页 > 其他 > 详细

[USACO19OPEN]Valleys P

时间:2020-02-17 21:24:49      阅读:138      评论:0      收藏:0      [点我收藏+]

题意

洛谷

做法

用并查集维护区域,剩下的就只用判是否有洞就好了

然后手玩出一个结论:凸角为\(+1\),凹角为\(-1\),和为\(sum\),洞数\(h\),满足\(sum=4-4h\)
位置\((x,y)\)定义一个角:三面为空为凸,旁边两侧为空为凸,旁边两侧为空为凹

然后合并的时候顺便维护下\(sum\)就好了

题外话

貌似那个结论的一般形式跟这个有关:Gauss–Bonnet theorem
然后我比较懒就没管了

[USACO19OPEN]Valleys P

原文:https://www.cnblogs.com/Grice/p/12323518.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!