【题解】APIO2007动物园

　　首先一眼感受到这题特别的性质……5个？这么小的，感觉就像是状压。脑补了一下，如果没有环的话应该很好做吧……有环怎么办？5真的很小的，随便乱搞肯定也可以。那就放在外面暴力枚举吧。然后正解就出来了。

　　然而这题题面真的有毒吧。说好的不能全部选走？我还多加了一个维度，结果数据里面允许全部取走……然后对于<5的点单独写了个爆搜。代码奇长……大家看看就好吧（以及位运算本人一贯以来又清奇又暴力的脑回路……）

　　dp[][][0/1]，1代表已经保留了至少一个动物……如果要A掉此题的话把转移那里加上dp[][][0]的就好了。整个namespace Speacial都是特判的点……（虽然数据里面并没有）

#include <bits/stdc++.h>

using namespace std;

#define CNST 32

#define maxn 10300

int n, c, tot, fans = , dp[maxn][CNST][];

int num1[maxn * ], num2[maxn * ];

int lst[] = {, , , , , };

int fst[] = {, , , , , };

vector <int> V[maxn];

int read()

{

    int x = ;

    char c;

    c = getchar();

    while(c < '' || c > '') c = getchar();

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x;

}

void gmax(int &a, int b)

{

    a = a > b ? a : b;

}

void print(int x)

{

    int a[], tot = ;

    a[] = a[] = a[] = a[] = a[] = ;

    while(x)

    {

        a[++ tot] = x & ;

        x >>= ;

    }

    for(int i = ; i; i --)

        printf("%d", a[i]);

    return;

}

void work(int x, int sum, int opt)

{

    int tem = ;

    for(vector <int> :: iterator i = V[x].begin(); i < V[x].end(); i ++)

    {

        int k = *i;

        if((sum & num2[k]) || (num1[k] > (sum & num1[k]))) tem ++;

    }

    dp[x][sum][opt] += tem;

    int k1 = (sum << ) & (fst[]), k2 = (((sum << ) & (fst[])) | );

    gmax(dp[x + ][k1][opt], dp[x][sum][opt]);

    gmax(dp[x + ][k2][], dp[x][sum][opt]);

}

int Check(int now, int sum)

{

    int ans = ;

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

    {

        int a = now, b = sum, t = ;

        t = a & (lst[ - i]); t <<= i;

        t |= ((b & (fst[i])) >> ( - i));

        for(vector <int> :: iterator j = V[i].begin(); j < V[i].end(); j ++)

        {

            int k = *j;

            if((t & num2[k]) || (num1[k] > (t & num1[k]))) ans ++;

        }

    }

    return ans;

}

int DP(int sum, int opt)

{

    memset(dp, -, sizeof(dp));

    int ans = ;

    dp[][sum][opt] = ;

    work(, sum, opt);

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

    {

        int maxx = ;

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

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

            {

                if(~dp[i][j][k]) work(i, j, k);

                maxx = max(maxx, dp[i][j][k]);

            }

    }

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

    {

        if(dp[n][j][] == -) continue;

        int p = Check(j, sum);

        ans = max(ans, p + dp[n][j][]);

    }

    return ans;

}

void dfs(int x, int sum)

{

    if(x == )

    {

        sum <<= ;

        if(sum & (CNST - )) fans = max(fans, DP(sum, ));

        else fans = max(fans, DP(sum, ));

        sum |= ;

        fans = max(fans, DP(sum, ));

        return;

    }

    sum <<= ;

    dfs(x + , sum);

    dfs(x + , sum |= );

}

int main()

{

    n = read(), c = read();

    for(int i = ; i <= c; i ++)

    {

        int E = read(), F = read(), L = read();

        int id = E + ; if(id > n) id -= n;

        V[id].push_back(++ tot);

        for(int j = ; j <= F; j ++) //害怕

        {

            int x = read(); x = id - x;

            if(x < ) x += n;

            num1[tot] |= ( << x);

        }

        for(int j = ; j <= L; j ++) //喜欢

        {

            int x = read(); x = id - x;

            if(x < ) x += n;

            num2[tot] |= ( << x);

        }

    }

    dfs(, );

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

    return ;

}