Algorithm

TopCoder题解 - DefectiveAddition

published on

这次偷了点懒,选了一道850分的,吃午饭前看了题意,吃饭的时候简单的想一下,回来写下来也不长就完成了。

题目来自SRM564 Div I,叫 DefectiveAddition

题目大意

给定一个数组 cards[],大小50以内,再给出一个数n,要你找出另一个数组a[],长度和cards[]相同,且对应项都不超过cards, 即满足 0 <= a[i] <= cards[i],并且要求a[0] xor a[1] xor ... a[m] = n,其中m为数组的长度

基本想法

看到xor运算,有经验的人很容易想到每一位之间是互相独立的,很多问题就可以利用这个特性按不同的位单独处理即可。

这个问题稍微有点麻烦的在于,稍微想一下很容易明白,低位上可能的取值是对高位是有依赖的。不过就算是有这个条件,最高的那一位是不依赖别的位的,所以可以从这上面开始考虑。

首先看一下样例,可以先解决掉一种极端情况:n 位数太大了,以至于不管怎样最后xor出来的结果都不可能达到n了,这种可以简单的先排除掉。

现在看所有的数最高为xor起来的结果,就两种可能:01,如果这一位的值和n对应的这一位不相等,那么可以认为至少有一个高位为1的数,最后变成了高位为0的数。 而如果高位异或起来和n相等的话,就存在所有的数高位不变的情况。但是所有数高位不变的情况其实很好处理:我们只要把所有数(包括n)这一位去掉,然后还是同样的这个问题求解即可。

现在就剩下高位至少有一个从1变为0了的情况。

方案计算

现在考虑高位至少有一个位数从1变成0了怎么统计方案数。

直接考虑有点麻烦,先看假如我们枚举每个数高位是0还是1,全都的数都定下来了之后,我们就知道每个数剩下的位数有多少种取值方法了:

  • 如果高位不变,则相当于去掉高位,可以从0取到剩下的数:比如11保持高位不变,则有11 - 8 + 1 = 4
  • 如果高位从1变成了0,那么低位可以任意取01,所以有2^k种:比如11可以选0->7 8种

注意到从1变成0的那些数的低位可以任意取,而且现在至少有一个,所以我们留下第一个(编号最小的),让剩下的数随便取 (用乘法原理即可得到方案数)。这个数的取法会由剩下的数确定下来(可以通过其它数xor完之后再和n求异或的结果确定)。所以这样我们就计算出了方案数。

但是,这样算很慢,因为要枚举方案数,所以复杂度略高。但是熟悉的同学很快会发现这个枚举可以通过动态规划的方来快速计算。方法是这样的:

我们用 f[i][j] 表示前 i 个数中,有j个从1变到0的数的情况下,方案数是多少。计算方法如下:

# if cards[i] 高位是0:
  f[i][j] = f[i-1][j] * (cards[i] + 1)
# else: cards[i]高位是1:
  f[i][j] = f[i-1][j] * (cards[i]去掉高位 + 1) + f[i-j][j-1] * (2 ^ k) [当j>1的时候]

这样递推一遍就是了。

整体做法相当于这样:

  • 检查是否无解,直接返回0
Read More...

Topcoder题解 - UnkownTree

published on

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了系统测试。

Read More...