CSP-S 2020 初赛 最优子序列

题面：

分析：

这道题目，存在一些疑惑，这和子序列有啥关系，直接全部异或起来，不是最大的吗？

对Max[x][y]的定义，表示当前的子序列下一个位置的高8位是x、最后一个位置的低8位是y时的最大价值。这个定义李，下一个位置的高8位是x，不理解最后一个位置的低8位是y是什么意思，然后第一个数的高8位哪去了？

// 分析代码
#include <iostream>

using namespace std;

typedef long long LL;

const int MAXN = 40000, M = 4, B = M >> 1, MS = (1 << B) - 1;
const LL INF = 1000000000000000LL;

LL Max[MS + 4][MS + 4];

// lower_bit操作
int w(int x) 
{
    int s = x;
    while(x) 
    {
        x ^= x & (x ^ (x - 1));
        s++;
    }
    return s;
}

// 手法专业，赞
void to_max(LL &x, LL y) 
{
    if(x < y)
        x = y;
}

int main() 
{
    int n;
    LL ans = 0;
    cin >> n;

    for(int x = 0; x <= MS; x++)
        for(int y = 0; y <= MS; y++)
            Max[x][y] = -INF;

    cout << B << ' ' << MS << '\n';
    for(int i = 1; i <= n; i++) 
    {
        LL a;
        cin >> a;

        // x是a的高8位，y是低8位
        int x = a >> B, y = a & MS;
        printf("===========x, y: %d %d\n", x, y);

        // 初始化成0
        LL v = 0;

        // 固定高8位，变化低8位，Max[x][z] + w(y ^ z)
        for(int z = 0; z <= MS; z++){
            to_max(v, Max[x][z] + w(y ^ z));
            printf("---%d %d y^z:%d, Max[x][z]:%lld w(y^z):%d 更新v:%lld\n", 
                    x, z, y ^ z, Max[x][z], w(y ^ z), v);
        }

        // 变化高8位，固定低8位，v + w((x ^ z) << B)
        for(int z = 0; z <= MS; z++){
            to_max(Max[z][y], v + w((x ^ z) << B));
            printf("---%d %d x^z:%d, v:%lld + w((x^z)<<B):%d 更新:Max[z][y]%lld\n", 
                    z, y, x^z, v, w((x ^ z) << B), Max[z][y]);
        }

        printf("===========v: %lld\n", v);
        to_max(ans , v);
    }

    cout << ans << endl;

    return 0;
}

// 输入
// 2
// 1  4
// 观察输出

2
2 3
1 
===========x, y: 0 1
---0 0 y^z:1, Max[x][z]:-1000000000000000 w(y^z):2 更新v:0
---0 1 y^z:0, Max[x][z]:-1000000000000000 w(y^z):0 更新v:0
---0 2 y^z:3, Max[x][z]:-1000000000000000 w(y^z):5 更新v:0
---0 3 y^z:2, Max[x][z]:-1000000000000000 w(y^z):3 更新v:0
---0 1 x^z:0, v:0 + w((x^z)<<B):0 更新:Max[z][y]0
---1 1 x^z:1, v:0 + w((x^z)<<B):5 更新:Max[z][y]5
---2 1 x^z:2, v:0 + w((x^z)<<B):9 更新:Max[z][y]9
---3 1 x^z:3, v:0 + w((x^z)<<B):14 更新:Max[z][y]14
===========v: 0
4
===========x, y: 1 0
---1 0 y^z:0, Max[x][z]:-1000000000000000 w(y^z):0 更新v:0
---1 1 y^z:1, Max[x][z]:5 w(y^z):2 更新v:7
---1 2 y^z:2, Max[x][z]:-1000000000000000 w(y^z):3 更新v:7
---1 3 y^z:3, Max[x][z]:-1000000000000000 w(y^z):5 更新v:7
---0 0 x^z:1, v:7 + w((x^z)<<B):5 更新:Max[z][y]12
---1 0 x^z:0, v:7 + w((x^z)<<B):0 更新:Max[z][y]7
---2 0 x^z:3, v:7 + w((x^z)<<B):14 更新:Max[z][y]21
---3 0 x^z:2, v:7 + w((x^z)<<B):9 更新:Max[z][y]16
===========v: 7
7

这个题目，先打到这里，做一个备忘，还需要进一步研究。