Knots

Subtract: 给定一个绳环构成的图形,求这个绳环能否通过拓扑变换变为一个环。绳环被二维展开在一个平面内,有若干个交点,每个交点处的绳子恰好两根。交点个数不大于 $5000$。

Ideas: 一个比较简单的想法是,我们模拟人解绳子的过程。具体怎么解呢?

  • 1. 如果我们发现,通过平移某一段绳子可以使交点个数减少,那么我们就这么操作。
  • 2. 如果我们发现,通过翻转某一段绳子可以使交点个数减少,那么我们就这么操作。

仔细想想,在人解绳子的过程中,貌似再没有任何其它高级的操作,因此我们可以认为以上两种操作可以解开任何可以解开的绳子。同时,题目中也说,任何一个合法绳环都可以这样生成。

对于第一个操作,我们可以这样判定:如果存在两段绳子 $a,b$,$a$完全在 $b$的上方,并且两段绳子都从交点 $A$开始,到交点 $B$结束,不经过其它任何交点。那么我们可以直接删除这两个交点,因为通过平移 $a,b$,这两个交点可以消失。

对于第二个操作,如果有一段绳子的左右端点重合于交点 $A$,且不经过任何其它交点,我们可以删除交点 $A$,因为我们可以通过翻转这一段绳子使这个交点消失。

实现的方法,可以是一条链表。

TIPS: 我在做这道题时遇到过这么几个问题:1. 误认为操作 1 只要满足其中一条绳子不经过任何其它交点即可,不难通过反例证伪。2. 没有合格的数据生成器保证生成出的绳环可以展开在二维平面内,使得对拍遇到困难。

分类: 文章

0 条评论

发表评论

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