【HDU 4876多校】ZCC loves cards【搜尋】

題意：給你n個數字，讓你選出k個按照一定順序圍成一個環，然後每次可以任取連續的m個（m <= k)數字進行異或，看能構造連續的數列【L，R】求出最大值R。

思路：就按照正常思想來做，對于n個數字。枚舉從中選出k個數，然後再對于這個k個數進行全排列，對于每次排列都更新答案。不過這裡要進行一個優化，因為資料是随機生成的。是以每次進行全排列時，都需要2^k的複雜度來判斷這k個數字不按照順序任取幾個進行異或，得到的連續數列是否比已知的答案更優，不然則不對次k個數字進行全排列。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n, K, L, ca, cnt[120], val[22], tmp[22], ans, num[10], dn[10], S[22];
bool vis[220];
int TF[220] = {0}, F[220] = {0};

void getans() {
    int i = L;
    for (i;;i++) if (F[i] != ca) break;
    if (i > L) ans = ans>(i-1)?ans:(i-1);
}

void ddfs(int d, int v) {
    int i, j, qb, k;
    if (d == K) {
        for (i = 0;i < d;i++) {
            qb = 0;
            for (j = 0;j < d;j++) {
                qb ^= dn[(i+j)%d];
                F[qb] = ca;
            }
        }
        getans();
        ca++;
    }
    vis[v] = true;
    for (i = 0;i < K;i++) {
        if (vis[i]) continue;
        dn[d] = num[i];
        ddfs(d+1, i);
    }
    vis[v] = false;
}

void cal() {
    int st = 1<<K, i, j, tm = 0, f = 0, tf = 0;
    for (i = 0;i < st;i++) {
        tm = 0;
        for (j = 0;j < K;j++) {
            if (i&(1<<j)) tm ^= num[j];
        }
        if (tm >= L) TF[tm] = ca;
    }
    for (i = L;;i++) if (TF[i] != ca) break;
    ca++;
    if (i == L || i-1 <= ans) return;
    for (i = 0;i < K;i++) {
        dn[0] = num[i];
        ddfs(1, i);
    }
}

void dfs(int d, int id) {
    int i, j, c;
    if (S[n]-S[id]+d < K) return;
    if (d == K)
    {
        c = 0;
        for (i = 0; i < n; i++)
        {
            for (j = 0; j < tmp[i]; j++)
                num[c++] = val[i];
        }
        cal();
        return;
    }
    if (id == n) return;
    for (j = 0; j <= cnt[val[id]]; j++)
    {
        tmp[id] = j;
        dfs(d+j, id+1);
        tmp[id] = 0;
    }
}

int main() {
    int i, j;
    ca = 1;
    while (~scanf("%d%d%d", &n, &K, &L)) {
        memset(cnt, 0, sizeof(cnt));
        S[0] = 0;
        for (i = 0;i < n;i++) scanf("%d", &val[i]), cnt[val[i]]++;
        sort(val, val+n);
        n = unique(val, val+n)-val;
        for (i = 0;i < n;i++) S[i+1] = S[i]+cnt[val[i]];
        ans = 0;
        dfs(0, 0);
        printf("%d\n", ans);
    }
}