当前位置: 首页 > news >正文

有关三角剖分的性质

考虑三角剖分对应的弧。

删,加边使得三角剖分的所有边都有公共端点,设这个公共端点为 \(x\)。我们令所有边对应的弧都是不经过 \(x\) 的弧。要使在删除过程中保持三角剖分,则:

  • 两条弧的关系要么是相交,要么是包含。

  • 每次删除的边对应的弧都是极大的,即不被任何弧包含。

  • 最小次数为 \(n - 3 - cnt\),其中 \(cnt\)\(x\) 端点的弧。

于是我们可以将删边的操作看做对森林的拓扑排序,方案数为 \(\frac{n}{\prod sz_i}\)

考虑原本的弧为 \((l, r)\),则其子树的大小为 \(r - l - 1\)。然后随便维护即可。

感觉像是 P10230 的口胡,不管了。

http://www.hskmm.com/?act=detail&tid=23786

相关文章:

  • 西门子通信-自制示意
  • Vue之刷新页面会触发的生命周期函数
  • 傅里叶的一生
  • Dos命令学习(新手)
  • 吴恩达深度学习课程一:神经网络和深度学习 第一周:深度学习简介
  • 实用指南:AI Agent开发平台如何设计?核心架构与工作流实战案例详解
  • Numercial result of HAA-DRSM
  • 防重复提交的实现
  • Day25错误(error)与异常(exception)的简单认识
  • 算法课第一次作业
  • 1. 对拍板子
  • Luogu P14122 [SCCPC 2021] Direction Setting题解 最小费用流
  • MySQL_基础
  • 5 qoj14553 序列与整数对 题解
  • AT_arc064_d [ARC064F] Rotated Palindromes
  • vscode代码块格式转换器
  • 二分模板
  • 如何控制事务?
  • C语言速成秘籍——跳转语句(goto) - 实践
  • 五子棋-下满了格子平局
  • 从免疫原性突破到技术迭代:全人源抗体如何重塑靶向治疗格局?
  • 工作感受月记(202510月)
  • 欧几里得算法与扩展欧几里得算法详解
  • 题解:AT_agc038_f [AGC038F] Two Permutations
  • 10.3 考试总结
  • CSP-S 复赛指南(2025年版)
  • AI元人文系列文章:AI元人文的未来——软硬件协同
  • 10.3考试反思
  • 10.2 考试总结
  • 20251003国庆模拟3