BZOJ 4300 绝世好题

发表于 | 分类于

Description

给定一个长为\(n\)的自然数序列\(a_i\)，求一个最长的子序列使得其相邻两项的按位与都不为\(0\)。

\(1\leq n\leq 10^5,a_i\leq 2\times 10^9\)。

Solution

终于有我会做的题力，，，

按位与不为零，就要满足有至少一个共同位。这样的话，我们直接在状态里额外开一维记录这个共同位是啥不就行了……

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <functional>
#include <utility>
const int maxn = 100005;
const int maxc = 31;
int d[maxn][maxc], rec[maxc];
int A[maxn];
int main() {
  int n; scanf("%d", &n);
  for(int i = 1; i <= n; i ++) scanf("%d", &A[i]);
  for(int i = 1; i <= n; i ++) {
    for(int j = 0; j < maxc; j ++) {
      if(!((1 << j) & A[i])) continue;
      d[i][j] = rec[j] + 1;
    }
    int th = *std::max_element(d[i], d[i] + maxc);
    for(int j = 0; j < maxc; j ++) {
      if((1 << j) & A[i]) rec[j] = std::max(rec[j], th);
    }
  }
  printf("%d\n", std::max(1, *std::max_element(rec, rec + maxc)));
  return 0;
}