Luogu 4310 绝世好题

BZOJ 4300

先把这堆东西丢到博客里，以后再复习。

首先考虑暴力的$dp$，设$f_i$表示以$i$结尾的满足条件的序列的最长长度，有：

　　　　$f_i = max(f_j) + 1$ $j < i $ $,$ $ a_j \& a_i \neq 0$

　　　　$ans = max(f_i)$ $1 \leq i \leq n$

这样是$n^2$的。

考虑二进制意义下的按位与，如果要使这个运算的结果不为$0$的话，必须要有一位两个数都是$1$，那么我们可以考虑拆位进行$dp$，设$g_j$表示第$j$位是$1$结尾的最长的满足条件的序列的长度。对于每一个$i$，有:

　　　　$f_i = max(g_j) + 1$ $0 \leq j \leq 32$ 并且$a_i$的第$j$位为$1$。

　　　　$g_j = max(f_i, g_j)$ $a_i$的第$j$位为$1$。

　　　　$ans = max(f_i)$ $1 \leq i \leq n$

事实上在写的时候并没有必要把$f$开出来。

时间复杂度$O(nlog(Maxn))$。

Code：

#include <cstdio>

#include <cstring>

using namespace std;

const int N = 1e5 + ;

const int M = ;

int n, a[N], f[M];

inline void read(int &X) {

    X = ; char ch = ; int op = ;

    for(; ch > '' || ch < ''; ch = getchar())

        if(ch == '-') op = -;

    for(; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    X *= op;

}

inline void chkMax(int &x, int y) {

    if(y > x) x = y;

}

int main() {

    read(n);

    for(int i = ; i <= n; i++) read(a[i]);

    int ans = ;

    for(int i = ; i <= n; i++) {

        int now = ;

        for(int j = ; j <= ; j++)

            if((a[i] >> j) & ) chkMax(now, f[j]);

        ++now;

        chkMax(ans, now);

        for(int j = ; j <= ; j++)

            if((a[i] >> j) & ) chkMax(f[j], now);

    }

    printf("%d\n", ans);

    return ;

}

巴特西

Luogu 4310 绝世好题

最新文章

热门文章