莞中松山湖长沙一中三校联考试题

莞中-松山湖-长沙一中三校联考试题

莞中、松山湖学校、长沙一中 三校联考试题 提高组

SubRaY被布置了n道作业题,可是他一道也不会..但他知道有w位高手,并知道每位高手会做哪些题,请问SubRaY至少请多少位高手,才能把所有的题都做出来? [输入][solve.in]

第一行两个整数n,w表示有n道作业题和w位高手,作业题以1..n编号.接下来w行,第i+1行第一个数li表示第i位高手会做的题目的数量,接下来li个数表示第i位高手会做哪些题目.

[输出][solve.out]一个数,SubRaY至少要请多少位高手. [样例输入] 4 4 2 1 2 1 4 3 2 3 4 2 1 3

[样例输出] 2

[数据范围]

对于40%的数据,3<=n,w<=10,

对于100%的数据,3<=n,w<=60,1<=li<=6

解法：

搜索题,本来打算n只开到10作为一道送分题的(这也是为什么这道题是第一题的原因),但是鉴于如果真这么做实在太水(掉RP),所以改为设4个送分点….

搜索是基础算法.虽然近几年中NOIP搜索题占的比率并不大,但是在考试临近结束时,或者有题不会时,写一个简单的搜索程序往往会带来意想不到的结果.比如2006年的金明的预算方案,有很多大牛虽

第2页 共15页

莞中、松山湖学校、长沙一中 三校联考试题 提高组

然写了DP但是某一个小细节处理错了,0分;那些写搜索的反而至少能得40-50分,加几条剪枝甚至能达到80-90分.可见搜索在实战中的作用.

这道题并不难,只需加几条剪枝就可全过:

1 可行性剪枝,如果当前选择的高手的数量已经大于等于当前最优解的数量,剪.这也是最基础,最简单,但却是最实用的剪枝之一.

2 重复数据 数据中不可避免地会出现某一个高手会做的题目,有另外一个高手全会做的情况.这种情况下,这个高手就不需要了,因为它完全可以被另外那个高手取代.

3 仅有情况 有的题只能被一位高手解决,所以在搜索之前把这位高手会做的题目删去吧,最优解中一定包含这位高手,所以这些题一定能被解决. 其实这道题模型就是2011年东莞特长生考试最后一题。 程序：

var i,j,k,n,m,ans,max,x:longint; a:array[1..60,1..6] of longint;

第3页 共15页