【电影院】

【题目描述】

在日本这片神奇的土地上一共有着m个演员。其中每个演员都有着一个独一无二的编号:1~m中的某个整数。Haruchinsan只看与这m个演员相关的电影,并且她喜欢其中的k个演员。对于在下个月上映的电影,Haruchinsan会观看电影的预告片并记录下这些信息:电影名,演员个数,参演的演员编号。很不幸的是,在Haruchinsan的记录中,每部电影只有电影名和演员个数保存完好,演员编号有一部分看不清楚。对于某部电影,如果没有其它的电影包含比这部电影更多的Haruchinsan喜欢的演员,那么这部电影被称为是Haruchinsan最爱的电影。

由于Haruchinsan最近沉迷于贝斯弹奏中,所以请你帮助她确定每部电影属于以下哪种情况:

I 是否一定会是她最爱的电影。

II 是否一定不会是她最爱的电影。

III 可能是最爱的电影,也可能不是。

【输入格式】

第一行两个整数m和k,表示演员的数量和Haruchinsan喜欢的演员数量。

第二行包含k个不同的整数ai,表示喜欢的演员编号。

接下来n块,第i块描述第i部电影的相关信息:

第一行一个字符串si,si仅包含小写英文字母,长度为1到10,表示电影名。

第二行一个非负整数di(1≤di≤m),表示这部电影的演员数量。

第三行有di个整数bij(0≤bij≤m),如果bij等于0,那么第j个演员的编号看不清了,否则表示第j个演员的编号。保证这一行同一个编号不会出现两次。

保证所有的电影名都不相同。数字之间以一个空格隔开。

【输出格式】

输出n行表示电影的信息。第i行输出:

0,如果第i部电影一定是最爱的电影。

1,如果第i部电影一定不是最爱的电影。

2,如果第i部电影可能是最爱的电影。

【样例输入】

5 3

1 3 5

jumanji

3

0 0 0

theeagle

5

1 2 3 4 0

matrix

3

2 4 0

sourcecode

2

2 4

【样例输出】

2

0

1

1

【数据范围】

对于100%的数据:1≤m,n≤100,1≤k≤m。

逻辑+模拟题。

首先根据剩余普通演员的数量和未知演员的数量可以推知至少还有几个喜欢的演员参演,进而算出一部电影喜欢演员的上下界。

然后就是逻辑分析了,我们选取一部电影i,那么

①i的下界比除了i之外的所有电影的上界都高,那么i一定是最爱的电影。

②如果i的上界比某部电影的下届低,那么i一定不是最爱的电影。

③如果不符上述条件,即i的上界比最大下届要大,那么i可能是最爱的电影。

算出上下界n²扫一遍即可。

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*