a230: APIO2007 3.动物园
Tags :
Accepted rate : 14人/16人 ( 88% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 02:15

Content

新建的圆形动物园是亚太地区的骄傲。圆形动物园坐落于太平洋的一个小岛上,它包含一大圈围栏,每个围栏里有一种富有异国风情的动物。如下图所示:

你是动物园的公关主管。你要做的是,让每个参观动物园的游客都尽可能高兴。今天有一群小朋友来到动物园参观,你希望能让他们在动物园度过一段美好的时光。但这并不是一件容易的事——有些小朋友喜欢某些动物,而有些小朋友则害怕某些动物。例如,Alex喜欢可爱的猴子和考拉,而害怕拥有锋利牙齿的狮子。而Polly会因狮子有美丽的鬃毛而喜欢它,但害怕有臭味的考拉。


你可以选择将一些动物从围栏中移走以使得小朋友不会害怕。但你移走的动物也不能太多,否则留给小朋友们观赏的动物就所剩无几了。


每个小朋友站在大围栏圈的外面,可以看到连续的5个围栏。你得到了所有小朋友喜欢和害怕的动物信息。当出现下面两种情形之一时,小朋友就会高兴:


* 至少有一个他害怕的动物(从视线可见的范围内)被移走,或
* 至少有一个他喜欢的动物没有被(从视线可见的范围内)移走。

例如,考虑下图中的小朋友和动物:

小朋友

可见的围栏 害怕的动物 喜欢的动物
Alex 2,3,4,5,6 围栏4 围栏2,6
Polly 3,4,5,6,7 围栏6 围栏4
Chaitanya 6,7,8,9,10 围栏9 围栏6,8
Hwan 8,9,10,11,12 围栏9 围栏12
Ka-Shu 12,13,14,1,2 围栏12,13, 2 -

假如你将围栏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个小朋友会高兴。这种方法使得最多的小朋友高兴。

Input

输入的第一行包含两个整数N, C,用空格分隔。N是围栏数(10≤N≤10 000),C是小朋友的个数(1≤C≤50 000)。围栏按照顺时针的方向编号为1,2,3,…,N。


接下来的C行,每行描述一个小朋友的信息,以下面的形式给出:

E F L X1 X2 … XF Y1 Y2 … YL


其中:


E表示这个小朋友可以看到的第一个围栏的编号(1≤E≤N),换句话说,该小朋友可以看到的围栏为E, E+1, E+2, E+3, E+4。注意,如果编号超过N将继续从1开始算。如:当N=14, E=13时,这个小朋友可以看到的围栏为13,14,1, 2和3。


F表示该小朋友害怕的动物数。L表示该小朋友喜欢的动物数。


围栏X1, X2, …, XF 中包含该小朋友害怕的动物。
围栏Y1, Y2, …, YL 中包含该小朋友喜欢的动物。


X1, X2, …, XF, Y1, Y2, …, YL是两两不同的整数,而且所表示的围栏都是该小朋友可以看到的。


小朋友已经按照他们可以看到的第一个围栏的编号从小到大的顺序排好了(这样最小的E对应的小朋友排在第一个,最大的E对应的小朋友排在最后一个)。注意可能有多于一个小朋友对应的E是相同的。

Output
仅输出一个数,表示最多可以让多少个小朋友高兴。
Sample Input
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

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
Sample Output
5

6
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1M
公開 測資點#3 (5%): 1.0s , <1M
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1M
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (5%): 1.0s , <1M
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <1M
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#15 (5%): 1.0s , <10M
公開 測資點#16 (5%): 1.0s , <10M
公開 測資點#17 (5%): 1.0s , <10M
公開 測資點#18 (5%): 1.0s , <10M
公開 測資點#19 (5%): 1.0s , <1M
Hint :

上面的样例1给出了前面描述的示例情形。它使得所有小朋友(C=5)高兴。样例2给出了这样的情形,要使得所有小朋友(C=7)都高兴是不可能的。

感谢morris1028补上图片!
Tags:
出處:
APIO2007第三题 [管理者:
liouzhou_101 (王启圣)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」