试题链接：H. Hashing

题意，在序列\({a_i}\)中挑选一个子序列\({a_{s_i}}\)，使得\(\sum i \oplus a_{s_i}\)最大，序列长度不超过\(10^5\)，元素大小不超过0xFF

显然，我们有如下做法

其中，i为处理的第i个数，j为这是选择的第几个数

然而，我们注意到，这个算法的时间复杂度是\(O(n^2)\)的，不足以完成此题

但是，注意到一旦我们确定了选择多少个数，那么答案可以拆为\(\sum i \% 256 \oplus a_{s_i} + \sum i - i \% 256\)

即，答案大小不与i的其它位数相关，因而，我们可以直接用i二进制表示的后8位来表示状态，这样状态数就剪刀了\(2.56 \times 10^7\)，是可以接受的复杂度

同时额外记下前面已经选择了多少个数即可

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <utility>
using namespace std;
const int maxn = 100000 + 5;
typedef pair<long long, int> pli;
pli ans[256][maxn];
int n, aa;
char ai[3];
int main()
{
    scanf("%d", &n);
    ans[0][0] = pli(0, -1);
    for (int i = 1; i < 256; i++) ans[i][0] = pli(0x8000000000000000ll, -1);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", ai);
        sscanf(ai, "%X", &aa);
        for (int j = 0; j < 256; j++)
        {
            pli &lst = ans[j][i - 1];
            pli &llt = ans[(j + 255) & 255][i - 1];
            ans[j][i] = max(lst, pli(llt.first + (aa ^ (llt.second + 1)), llt.second + 1));
        }
    }
    long long aans = 0;
    for (int j = 0; j < 256; j++)
        aans = max(aans, ans[j][n].first);
    cout << aans << endl;
    return 0;
}