首页 > itarticle > bzoj 4300 绝世好题

bzoj 4300 绝世好题

admin 1月 18, 2021 0

Description

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

(1leq nleq 10^5,a_ileq 2times 10^9)。

Solution

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

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

Code


#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 () {
  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("%dn", std::max(1, *std::max_element(rec, rec + maxc)));
  return 0;
}