Codechef - Longest AND Subarray(位运算)

codechef,longest,and,subarray,运算 · 浏览次数 : 4

小编点评

```c++ void solve() { int n; cin >> n; int bit = floor(log2(n)) + 1; int res = max(n - pow(2, bit - 1) + 1, pow(2, bit - 2)); cout << res << endl; } ```

正文

题目大意

  给定一个正整数N,其序列为[1, 2, 3, ..., N],找到一个长度最大的连续子列,使得其所有元素取与运算的结果为正(最终输出只需要输出最大长度即可)。

 

思路

  刚开始可能并不好注意到,可以举一些小的样例来找规律。比如2:1 & 2 = 0,不满足条件,所以只能取长度为1的数组[1]或者[2]。对于7:题目给出的样例中呈现的是长度为4的子数组[4, 5, 6, 7](似乎是一定暗示)。可以看到,4,5,6,7的二进制分别为:100,101,110,111,他们相与的结果一定不为0(因为最高位都为1);同样我们可以发现:8到15之间所有数字的二进制都是1xxx的形式,所以所有元素取与运算的结果肯定为正(8到9,8到10,8到11,...,8到14其实也一样)。此外,如果熟悉的话是很容易想到2的1次方是2,2的2次方是4...,分别代表着2到3的长度为2,4到7的长度为4,以此类推。为此,可以给出最终构造出的式子(max(n - pow(2, bit - 1) + 1, pow(2, bit - 2)),bit是二进制的位数,没反应过来的可以代几个数字进去试试。

 

代码

  主代码出奇的短。

void solve() {
    int n;
    cin >> n;
    int bit = floor(log2(n)) + 1;
    int res = max(n - pow(2, bit - 1) + 1, pow(2, bit - 2));
    cout << res << endl;
}

 

题目链接在这里:Longest AND Subarray - Problems - CodeChef

与Codechef - Longest AND Subarray(位运算)相似的内容: