g*******y
发帖数: 1930 | 1 November 06
一日3题
第一题。给一个数组a[1]到a[n] : 例如 1，2，3，4，5，6
现在随机生成a的一个permutation: b[1]到b[n] （例如：3 1 5 2 4 6）
问, a和b数组在每一位上都不相同的概率是多少？假设a本身没有重复的数
我的解法：
主问题：F(n) = 给定长度为n的a数组，b数组有多少种取法
辅助问题：结果用f(n)表示。 b数组是{1….i-1,x,i+1…n}的一个排列，其中x!=i，满
足a，b在每一位上都不相同，有多少种b？例如，a = 1,2,3,4; b是{1,2,5,4}的一个排
列。换句话说，组成b的元素中，有且只有一个数不在a中。
这样定义了F(n),f(n)后，很显然有递推关系：
F(n) = (n-1) * f(n-1) //解释：第一位有n-1种选择，任意一种选择后，问题变为
一个 n-1规模的辅助问题
f(n) = F(n-1) + (n-1)*f(n-1) //情况一，在b数组的第i位置填入x，考虑剩下的n-
1个位置，即是一个n-1规模的主问题；情况二，i位置填入非x的数，考虑剩下的n- | w******1
发帖数: 520 | 2 static int BitSetCount256[256] =
{
#define B2(n) n, n+1, n+1, n+2,
#define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2),
#define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2),B6(0), B6(1), B6(1), B6(2)
}
这个不是很明白。。。 定义完了， 直接用么？ | c*********s
发帖数: 92 | | s*********t
发帖数: 1663 | 4 我也想知道。呵呵
我自己做topcoder做了一个礼拜，还都是300分的弱智题，结果卡在第22题了，后来就再
也没登录过。。。
【在 c*********s 的大作中提到】
: 一日三题,坚持了多久啊?
| c******f
发帖数: 2144 | | E*S
发帖数: 790 | | l***r
发帖数: 241 | | g*****e
发帖数: 282 | 8 第一题就按组合数学想好了，有一重复的case，有两个重复的case，。。。全部重复的
case，处理之。
第三题数1有点意思。这样写更容易理解些:P
int c=0;
while(i>0)
{
c+=(i&0x1)
i=i>>1;
}
return c;
【在 g*******y 的大作中提到】
: November 06
: 一日3题
: 第一题。给一个数组a[1]到a[n] : 例如 1，2，3，4，5，6
: 现在随机生成a的一个permutation: b[1]到b[n] （例如：3 1 5 2 4 6）
: 问, a和b数组在每一位上都不相同的概率是多少？假设a本身没有重复的数
: 我的解法：
: 主问题：F(n) = 给定长度为n的a数组，b数组有多少种取法
: 辅助问题：结果用f(n)表示。 b数组是{1….i-1,x,i+1…n}的一个排列，其中x!=i，满
: 足a，b在每一位上都不相同，有多少种b？例如，a = 1,2,3,4; b是{1,2,5,4}的一个排
: 列。换句话说，组成b的元素中，有且只有一个数不在a中。
|
|
