题目
题目描述
新建的圆形动物园是亚太地区的骄傲。圆形动物园坐落于太平洋的一个小岛上，包含一大圈围栏，每个围栏里有一种动物。如下图所示：
你是动物园的公关主管。你要做的是，让每个参观动物园的游客都尽可能高兴。今天有一群小朋友来到动物园参观，你希望能让他们在动物园度过一段美好的时光。但这并不是一件容易的事——有些小朋友喜欢某些动物，而有些小朋友则害怕某些动物。例如， Alex 喜欢可爱的猴子和考拉，而害怕拥有锋利牙齿的狮子。而 Polly 会因狮子有美丽的鬃毛而喜欢它，但害怕有臭味的考拉。
你可以选择将一些动物从围栏中移走以使得小朋友不会害怕。但你移走的动物也不能太多，否则留给小朋友们观赏的动物就所剩无几了。
每个小朋友站在大围栏圈的外面，可以看到连续的 $5$ 个围栏。你得到了所有小朋友喜欢和害怕的动物信息。当下面两处情况之一发生时，小朋友就会高兴：
至少有一个他害怕的动物被移走；
至少有一个他喜欢的动物没被移走。
例如，考虑下图中的小朋友和动物：
假如你将围栏 $4$ 和 $12$ 的动物移走。Alex 和 Ka-Shu 将很高兴，因为至少有一个他们害怕的动物被移走了。这也会使 Chaitanya 高兴，因为他喜欢的围栏 $6$ 和 $8$ 中的动物都保留了。但是，Polly 和 Hwan 将不高兴，因为他们看不到任何他们喜欢的动物，而他们害怕的动物都还在。这种安排方式使得三个小朋友高兴。
现在换一种方法，如果你将围栏 $4$ 和 $6$ 中的动物移走，Alex 和 Polly 将很高兴，因为他们害怕的动物被移走了。Chaitanya 也会高兴，虽然他喜欢的动物 $6$ 被移走了，他仍可以看到围栏 $8$ 里面他喜欢的动物。同样的 Hwan 也会因可以看到自己喜欢的动物 $12$ 而高兴。唯一不高兴的只有 Ka-Shu。
如果你只移走围栏 $13$ 中的动物，Ka-Shu 将高兴，因为有一个他害怕的动物被移走了，Alex, Polly, Chaitanya 和 Hwan 也会高兴，因为他们都可以看到至少一个他们喜欢的动物。所以有 $5$ 个小朋友会高兴。这种方法使得了最多的小朋友高兴。
输入格式
输入的第一行包含两个整数 $N,C$，用空格分隔。$N$ 是围栏数，$C$ 是小朋友的个数。围栏按照顺时针的方向编号为 $1,2,3,…,N$。
接下来的 $C$ 行，每行描述一个小朋友的信息，以下面的形式给出$ \ F \ L \ X_1 \ X_2 \ \cdots X_F \ Y_1 \ Y_2\ \cdots Y_L$。
其中：EEE 表示这个小朋友可以看到的第一个围栏的编号，换句话说，该小朋友可以看到的围栏为 $E, E+1, E+2, E+3, E+4$。注意，如果编号超过 $N$ 将继续从 $1$ 开始算。如：当 $N=14, E=13$ 时，这个小朋友可以看到的围栏为 $13,14,1, 2$ 和 $3$。
$F$ 表示该小朋友害怕的动物数。$L$ 表示该小朋友喜欢的动物数。
围栏 $X_1, X_2, \cdots , X_F$ 中包含该小朋友害怕的动物。围栏 $Y_1, Y_2,\cdots , Y_L$ 中包含该小朋友喜欢的动物。
$X_1, X_2, \cdots , X_F, Y_1, Y_2, \cdots , Y_L$ 是两两不同的整数，而且所表示的围栏都是该小朋友可以看到的。
小朋友已经按照他们可以看到的第一个围栏的编号从小到大的顺序排好了（这样最小的 $E$ 对应的小朋友排在第一个，最大的 $E$ 对应的小朋友排在最后一个）。
注意可能有多于一个小朋友对应的 $E$ 是相同的。
输出格式
仅输出一个数，表示最多可以让多少个小朋友高兴。
样例
样例输入 1
14 5
2 1 2 4 2 6
3 1 1 6 4
6 1 2 9 6 8
8 1 1 9 12
12 3 0 12 13 2
样例输出 1
5
样例说明 1
样例 $1$ 给出了前面描述的示例情形。它使得所有小朋友（$C=5$）高兴。
样例输入 2
12 7
1 1 1 1 5
5 1 1 5 7
5 0 3 5 7 9
7 1 1 7 9
9 1 1 9 11
9 3 0 9 11 1
11 1 1 11 1
样例输出 2
6
样例说明 2
样例 $2$ 给出了这样的情形，要使得所有小朋友（$C=7$）都高兴是不可能的。
数据范围与提示
对于每一个测试点，如果你的答案正确，则该测试点得满分，否则得 $0$ 分。
对于全部数据，$10\le N\le 10^4,1\le C\le 5\times 10^4,1\le E\le N$。
题解
发现小朋友看见只有$5$
考虑状压？
$f_{i,j}$表示到第$i$个围栏的时候，往后的$5$个围栏状态为$j$时最多高兴的小朋友数，那么转移就是$f_{i,j}=max(f_{i-1,(j\ and \ 15)«1},f_{i-1,(j\ and\ 15)«1\vert 1})+sum_{i,j}$，$sum_{i,j}$表示以$i$开头往后的$5$个围栏状态为$j$时高兴的小朋友个数，这个可以预处理出来
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=1e4+5;
int n,c;
int sum[51][MAX],f[51][MAX];
int main()
{
scanf("%d%d",&n,&c);
for(int i=1,e,F,L;i<=c;++i)
{
scanf("%d%d%d",&e,&F,&L);
int qaq=0,qwq=0,tt;
for(int j=1;j<=F;++j)
scanf("%d",&tt),tt=(tt-e+n)%n,qaq|=(1<<tt);
for(int j=1;j<=L;++j)
scanf("%d",&tt),tt=(tt-e+n)%n,qwq|=(1<<tt);
for(int j=0;j<=31;++j)
if((qwq&j)||(~j&qaq)) ++sum[j][e];
}
int ans=0;
for(int i=0;i<=31;++i)
{
memset(f,128,sizeof(f));
f[i][0]=0;
for(int j=1;j<=n;++j)
for(int l=0;l<=31;++l)
f[l][j]=max(f[(l&15)<<1][j-1],f[(l&15)<<1|1][j-1])+sum[l][j];
ans=max(ans,f[i][n]);
}
return printf("%d",ans),0;
}
