CF 1720 D1. Xor-Subsequence (easy version)

标签：Xor int max CF 1720 ++ oplus dp

传送门： Xor-Subsequence (easy version)

思路：
这个问题的描述类似最长不降子序列，不难想到可以设 \(dp[i]\) 为以 \(a[i]\) 结尾的最长子序列，进而得到递推方程：

\[dp[i] = max\{dp[j] \ | \ a_j \oplus i < a_i \oplus j\} + 1 \]

显然，直接接递推方程计算的复杂度为 \(O(n^2)\)，还需要进一步优化。注意题中还有一个条件，即 \(a_i<200\)

因为 \(200<256\)，所以 \(a\) 数组中的数只会影响异或值（二进制下）的后 \(8\) 位。因此，当 \(i-j>256\) 时，我们可以忽略 \(a_i\) 和 \(a_j\) 的影响，原不等式 \(a_j \oplus i < a_i \oplus j\) 变为 \(i<j\)，与 \(j < i\) 的前提矛盾，显然不可能满足

所以，对于 \(dp[i]\)，我们实际上并不需要从 \(0\) 开始枚举 \(j\)，只需从 \(i-256\) 开始枚举，于是复杂度变为 \(O(256n)\)

#include <bits/stdc++.h>
using namespace std;
#define fsio ios::sync_with_stdio(false)
const int maxn = 3e5+10;

int s[maxn], dp[maxn];

int main()
{
    fsio;
    int T; cin>>T;
    while(T--)
    {
        int n; cin>>n;
        for (int i = 0; i < n; i++) cin>>s[i], dp[i] = 1;
        int ans = 0;
        for (int i = 1; i < n; i++)
        {
            for (int j = max(0, i-256); j < i; j++)
                if ((s[j]^i) < (s[i]^j))
                    dp[i] = max(dp[i], dp[j]+1);
            ans = max(ans, dp[i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}

标签：Xor,int,max,CF,1720,++,oplus,dp
From： https://www.cnblogs.com/pannta/p/16715092.html