published on
tags: tech algorithm topcoder

TopCoder题解 - DefectiveAddition

这次偷了点懒,选了一道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