a*****g
发帖数: 110 | 1 面的时候一时没想出来比较理想的方法
还请高手指点
Unsighed 30-bit integer B, 0 <= B < 2^30,
we say integer A conforms to integer B if A has bits set to 1 in all
positions where B has bits set to 1.
e.g. 00 0000 1111 0111 1101 1110 conforms to
00 0000 1100 0110 1101 1010
Write function which takes three 30-bit unsighed integer as input, and
returns the number of unsighed 30-bit integers that conform to at least one
of unsighed 30-bit A, B, C
e.g. A = 11 1111 1111 1111 1111 1111 1111 1001
B = 11 1111 1111 1111 1111 1111 1111 0011
C = 11 1111 1111 1111 1111 1111 1111 0100
Should return 11.
0011, 0100, 0101, 0110, 0111, 1001, 1011, 1100, 1101, 1110, 1111
Time complexity O(1), space complexity O(1) |
c****p
发帖数: 6474 | 2 没理解错的话，如果A conform to A'，那么A'中为1的位，A对应地必须为1；A'中为0的
位，A对应地可以为1或者0。
如果令ones(A)=A中1的位数（对于30-bit unsigned有O(1)算法），
则A'的可能数为2^(30-ones(A))。
令f(A) = A'的可能数，
那么答案应该是：
f(A) + f(B) + f(C) -f(A&B) - f(A&C) - f(B&C) + f(A&B&C)
=====
囧，，，，和例子验证了一下，好像不对。。。。
=====
上式改成
f(A) + f(B) + f(C) -f(A|B) - f(A|C) - f(B|C) + f(A|B|C)
one
【在 a*****g 的大作中提到】
: 面的时候一时没想出来比较理想的方法
: 还请高手指点
: Unsighed 30-bit integer B, 0 <= B < 2^30,
: we say integer A conforms to integer B if A has bits set to 1 in all
: positions where B has bits set to 1.
: e.g. 00 0000 1111 0111 1101 1110 conforms to
: 00 0000 1100 0110 1101 1010
: Write function which takes three 30-bit unsighed integer as input, and
: returns the number of unsighed 30-bit integers that conform to at least one
: of unsighed 30-bit A, B, C
|
a*****g
发帖数: 110 | 3 理解没错
不过好像在考虑A B C 重复的个数里面 不能简单的A&B B&C
我也不是很清楚
0的
【在 c****p 的大作中提到】
: 没理解错的话，如果A conform to A'，那么A'中为1的位，A对应地必须为1；A'中为0的
: 位，A对应地可以为1或者0。
: 如果令ones(A)=A中1的位数（对于30-bit unsigned有O(1)算法），
: 则A'的可能数为2^(30-ones(A))。
: 令f(A) = A'的可能数，
: 那么答案应该是：
: f(A) + f(B) + f(C) -f(A&B) - f(A&C) - f(B&C) + f(A&B&C)
: =====
: 囧，，，，和例子验证了一下，好像不对。。。。
: =====
|
f**********l
发帖数: 1191 | 4 思路是对的，我的理解跟你一样，不过稍微有点变化。
令 zeros(A) = A中0的位数
A'的可能数为2^zeros(A)
f(A) = A'的可能数，
则答案是：
f(A) + f(B) + f(C) - f(A|B) - f(A|C) - f(B|C) + f(A|B|C)
对着例子算了一下，返回是11
觉得象是排列组合的题，这门课我学的不好，:-(
0的
【在 c****p 的大作中提到】
: 没理解错的话，如果A conform to A'，那么A'中为1的位，A对应地必须为1；A'中为0的
: 位，A对应地可以为1或者0。
: 如果令ones(A)=A中1的位数（对于30-bit unsigned有O(1)算法），
: 则A'的可能数为2^(30-ones(A))。
: 令f(A) = A'的可能数，
: 那么答案应该是：
: f(A) + f(B) + f(C) -f(A&B) - f(A&C) - f(B&C) + f(A&B&C)
: =====
: 囧，，，，和例子验证了一下，好像不对。。。。
: =====
|
m***z
发帖数: 26 | 5 用或不用与
0的
【在 c****p 的大作中提到】
: 没理解错的话，如果A conform to A'，那么A'中为1的位，A对应地必须为1；A'中为0的
: 位，A对应地可以为1或者0。
: 如果令ones(A)=A中1的位数（对于30-bit unsigned有O(1)算法），
: 则A'的可能数为2^(30-ones(A))。
: 令f(A) = A'的可能数，
: 那么答案应该是：
: f(A) + f(B) + f(C) -f(A&B) - f(A&C) - f(B&C) + f(A&B&C)
: =====
: 囧，，，，和例子验证了一下，好像不对。。。。
: =====
|
c****p
发帖数: 6474 | 6 嗯，改成or就对了，我也刚推出来。。。
【在 f**********l 的大作中提到】
: 思路是对的，我的理解跟你一样，不过稍微有点变化。
: 令 zeros(A) = A中0的位数
: A'的可能数为2^zeros(A)
: f(A) = A'的可能数，
: 则答案是：
: f(A) + f(B) + f(C) - f(A|B) - f(A|C) - f(B|C) + f(A|B|C)
: 对着例子算了一下，返回是11
: 觉得象是排列组合的题，这门课我学的不好，:-(
:
: 0的
|
c****p
发帖数: 6474 | 7 嗯。。
【在 m***z 的大作中提到】
: 用或不用与
:
: 0的
|
h**6
发帖数: 4160 | |
G****A
发帖数: 4160 | 9 2^{k1} + 2^{k2} + 2^{k3} - 2^{k1&&k2} - 2^{k1&&k3} - 2^{k2&&k3} + 2^{k1&&k2&
&k3} = 2^2 + 2^2 + 2^3 - 2^1 - 2^1 - 2^1 + 2^0 = 11
one
【在 a*****g 的大作中提到】
: 面的时候一时没想出来比较理想的方法
: 还请高手指点
: Unsighed 30-bit integer B, 0 <= B < 2^30,
: we say integer A conforms to integer B if A has bits set to 1 in all
: positions where B has bits set to 1.
: e.g. 00 0000 1111 0111 1101 1110 conforms to
: 00 0000 1100 0110 1101 1010
: Write function which takes three 30-bit unsighed integer as input, and
: returns the number of unsighed 30-bit integers that conform to at least one
: of unsighed 30-bit A, B, C
|
