published on
tags: tech algorithm topcoder

Topcoder题解 - UnkownTree

2013年开始了,今年我准备学不少新东西,而且已经学过的东西也挑选了一些内容准备 进行提高,而算法就是其中之一。因为以前已经在里面投入过不少功夫,所以想试试看 最高能达到怎样的程度。

对于训练来说,有两个很重要的要点如下:

  • 反馈,做了练习之后能够得知正误,反馈越及时越好
  • 在学习区练习,这一点简单来说就是练习需要能学到新东西,不要老是搞自己很容易解决的,但是也要是自己目前的能力可以接受的,要是完全搞不懂,也是浪费经理。

由于上面的第二点,我选择了Topcoder DIV1下面的1000pt的题目。这些题目的素质比较稳定,大多属于我个人可以接受的范围,也能够在线提交,得到方便的测试,及时的反馈。所以我今年关于算法方面的主要工作就是慢慢分析一些Topcoder的题目,可能不定期参加一些比赛。为了整理在思考这些题目中的思路,故预备整理一系列的题解。

这些题解主要记录我在分析这些问题中的思路,所以和正统的习题解答看上去可能不一样。不过对于想要借鉴的同学应该会有一定的帮助。

题目大意

这回我们选择的题目叫 UnkownTree 是SRM565 Div I的1000pt题

题意是说我们现在描述一棵树:

  1. 树上有3个点被标记为A B C
  2. 除了这3个点外还有N (1<=N<=50)个点,编号为1到N
  3. N个点到A的距离用数组distanceA记录,同样到B的距离用distanceB记录,CdistanceC同理
  4. 图中边的长度都是正整数

现在给定了distanceA distanceB distanceC, 问满足条件的树有多少棵(最后模一个数M避免大数运算)

初步尝试

拿到问题后最先想到的就是找几个例子,画几个图看看有没有什么规律。

画了两张纸后,看不出什么头绪,放弃……

于是转入了逐步分析的路线。

分析: 标记1个点的情况

首先想到简化题目条件,最简单的当然是只给定一个distance数组的情况。即只限制到A点的距离。

这样不是很难想到,我们将这个A点作为树的根,那么每个点的父亲要么就是A,要么是一个到A距离比自己更小的点。于是要计算方案也很简单了,我们知道每个点有多少个点可以作为它的父亲,那么这个点就有多少方案,整个树的方案数就是将各个点比其小的点的个数+1(根)乘起来即可。

这个状况可以参考下图来理解:

图1

分析: 标记2个点的情况

现在考虑给定到两点的距离的情况,现在A B被标出来了,已知所有点到A的距离和到B的距离。那么满足条件的树是什么样的?

首先我们会想找出A B之间的关系。很容易想到就是先计算A B的距离是多少。

一旦想到距离,我们就很容易考虑到一个问题: A B 是直接相连还是经过了中间某个点连接?

根据已有的条件,我们倒是肯定不了实际情况是哪种。但是我们可以分情况讨论:

A B 直接相连的情况

简单的分析可以得出现在任意一个点到A的距离和到B的距离的差就是A B间的距离。而且必须满足所有的点到A的距离和到B的距离差必须是都等于同一个值。此时AB的路线上不存在别的点

A B 不直接相连的情况

如果A B 没有直接相连,那么至少有一个点在A B之间的路径上,那么A B间的距离应该等于这个点到A的距离加上这个点到B的距离。在这个条件下,我们可以对所有点计算出两个距离的和,很容易想到最小的就是A B间的距离。

有了上面的思考A B,不难想到所有到A距离+到B距离等于A B距离的点都在AB的路径上

不在A B路径上的点

简单的画一下图容易发现,这些点肯定都通过AB路径上的某个点(包括A B),连接到的A B这两点。那么,我们把路径上的每一个点都看作根,别的每一个点很容易计算出是连接到哪一个根的,并且到根的距离是多少,这样我们就转化到了一个点的距离的问题!!用上面分析的方法算吧。

2个点的方法总结

最后回顾下两个点的情况的计算方法:

  1. 分两种情况(直接相连和不直接相连),分别统计可能的结果再加起来
  2. 对于每种情况,计算出A B路径上的所有节点 (为了方便,我们称这条链为骨架
  3. 对于不在骨架上的点,计算其通过骨架上哪个点连接到骨架中,并且距离对应点的距离是多少。
  4. 对于骨架上每个点,现在知道所有连接它的点和到它的距离,用前面分析的方法计算方案数,再把所有骨架上点的方案数乘起来即可。

完成: 标记3个点的情况

有了2个点的思路,很容易想3个点的情况类似,也是要先找出骨架来,不过再那之前,我们会发现这回要枚举的情况挺恶心的,因为每两个点都有可能直接相连,所以要枚举7种情况(不可能3个点两两相连,否则出现环了)。

枚举完之后,会发现骨架也有2中类型,如下面的图所示,这个可以通过计算确定出是哪一种,而不用枚举,不过要分情况处理。

2种情况

骨架确定之后,工作和2个点的完全一样了:每个点找一个位置挂上去,然后统计方案。

3个点的关键在于将要讨论的情况变多了,需要合理设计程序,使得共同的逻辑部分可以公用代码。各种情况处理的时候多加小心即可。这个代码量问题完全符合Topcoder一贯的作风,使得这题最后只有3人提交,2人pass了系统测试。