给定N个整数区间[lo_i，hi_i。

Given N integer intervals [lo_i,hi_i].

各区间选择一个数字，这样按位或将成为给定数量X.（这并不重要，如果结果有更多的1位比X;也就是说，如果生成的编号为Y，（X安培; Y）= = X应持有）

From each interval chose a number such that bitwise OR of them become given number X.(It doesn't matter if the result has more 1 bits than X; i.e. if the generated number is Y, (X&Y)==X should hold)

推荐答案

让我们来概括这个问题一点点。我打算写位运算符像OR和AND和SR（右移）。

Let's generalize the problem a little. I'm going to write bitwise operators like OR and AND and SR (shift right).

给定一个自然数X，间隔[lo_1，hi_1]，...，[lo_N，hi_N]选自自然数和比特b在{0，1}，确定是否存在于自然数Y_1 [ lo_1，hi_1]，...，y_N在[lo_N，hi_N]使得让Y = Y_1或...或y_N，它保持（X和Y）= X，并且存在i满足x_i＆所述; = hi_i - B

Given a natural number X, intervals [lo_1, hi_1], ..., [lo_N, hi_N] consisting of natural numbers, and a bit b in {0, 1}, determine whether there exist natural numbers y_1 in [lo_1, hi_1], ..., y_N in [lo_N, hi_N] such that, letting Y = y_1 OR ... OR y_N, it holds that (X AND Y) = X and that there exists i such that x_i <= hi_i - b.

基本情况为我的递归算法是当lo_1 = hi_1 = lo_2 = ... = hi_n = 0存在一种解决方案，如果且仅当x = 0且b = 0。

The base case for my recursive algorithm is when lo_1 = hi_1 = lo_2 = ... = hi_n = 0. There exists a solution if and only if X = 0 and b = 0.

电感，prepare一个子问题通过让X'= X SR 1和lo_i'= lo_i SR 1和hi_i'= hi_i SR 1.让奇（I）为真当且仅当hi_i AND 1 = 1让奇+（I）为真当且仅当奇（i）和lo_i＆LT; hi_i。如果X与1 = 0：

Inductively, prepare a subproblem by letting X' = X SR 1 and lo_i' = lo_i SR 1 and hi_i' = hi_i SR 1. Let Odd(i) be true if and only if hi_i AND 1 = 1. Let Odd+(i) be true if and only if Odd(i) and lo_i < hi_i. If X AND 1 = 0:

如果存在我这样奇数+（I），然后让B'= 0。否则，让B'= B。

If there exists i such that Odd+(i), then let b' = 0. Otherwise, let b' = b.

如果X AND 1 = 1：

If X AND 1 = 1:

如果存在不同的i和j，使得奇数+（i）和奇（J），然后让B'= 0。如果不存在Ĵ使得奇（J），然后让B'= 1。否则，让B'= B。

If there exist distinct i and j such that Odd+(i) and Odd(j), then let b' = 0. If there exists no j such that Odd(j), then let b' = 1. Otherwise, let b' = b.

返回答案的子问题。