[GCJ 2020 - Round2] C. Wormhole in One

[Wizmann]

Description

啥时候GCJ能改改这种超长题面的日狗风格。。

在一个二维平面上有N个洞。你可以在平面上选择任意位置，向任意方向打出一颗高尔夫球。高尔夫球在运行中不会改变方向。

你可以在任意两个点(A, B)之间构建虫洞，虫洞是双向联通的。球可以从A点进入，从B点离开；也可以从B点进入，从A点离开。虫洞可以被利用无数次，且虫洞只会改变球的位置，不会改变球的运动方向。

在一个洞上，最多只能构建有一个虫洞。（即可以有A<->B，不能有A<->B<->C）

求一种最优的方法，使得球经过的虫洞数最多（从A进入虫洞，从B离开虫洞，则AB各记1次。重复进出虫洞不记数）

• Small Data
  • T = 100
  • 1 <= N <= 7
• Large Data
  • T = 100
  • 1 <= N <= 100

Problem

Soluton

小数据的解法

因为球在每一个洞上有两种状态”还没进去“和”刚刚出来“。这两种状态所对应的处理逻辑是不同的。

所以可以使用两个dfs函数交替进行递归。但实现起来仍有一定难度。可以参考这个Code。

大数据的解法

初步思路是比较简单的，球的初始方向一定，那么我们会遍历在一条线上的所有洞，然后再通过虫洞跳跃到另一条平行线上。

因为我们需要对虫洞计数，我们可以对球的路径进行红黑（Red，Black）交替染色。红色代表通过虫洞移动，黑色代表离开虫洞后，球通过自身的速度移动。根据题意，红边与红边不能相连，黑边和黑边偶尔可以相连（见官方Sample4）。

如果一条边上有偶数个洞（简称偶数边），我们可以对其RBRB...BR染色。或者对其BRBR...B染色，然后在两端接上两个单独的点（不能与其它洞连成线）。对于多条偶数边，我们可以使用同样的方法将其连接在一起，并且经过所有的洞。

对于一条边上有奇数个洞（简称奇数边），则不能直接连接。参考官方Sample4，我们可以将一对奇数边形成一对，使得两个端点为B染色，这样可以链接所有的奇数边对。

如果有一条奇数边不能成对，那么这条边的最后一个端点就点就是球的运动路径的终点。

所以：

• 如果有x条偶数边，y条奇数边（y % 2 == 0)

  ans = min(单独点, 2) + sum(偶数边上的点) + sum(奇数边上的点)

• 如果有x条偶数边，y条奇数边（y % 2 == 1)

  ans = min(单独点, 1) + sum(偶数边上的点) + sum(奇数边上的点)

Code

并不能给出确切的证明呢。。。