首页 > 搜索 > DFS搜索 > hdu 2208 唉,可爱的小朋友-DFS-[解题报告]C++
2014
01-04

hdu 2208 唉,可爱的小朋友-DFS-[解题报告]C++

唉,可爱的小朋友

问题描述 :

唉,小朋友是比较麻烦的。在一个幼儿园里,老师要上一节游戏课,有N个小朋友要玩游戏,做游戏时要用小皮球,但是幼儿园里只有M个小皮球,而且有些小朋友不喜欢和一些小朋友在一起玩,而只喜欢和另一些小朋友一起玩,比如傻妞只喜欢和傻瓜,傻根,傻蛋们一起玩,傻根又不喜欢和傻蛋一起玩,傻蛋喜欢和傻子一起玩。所以老师只好把他们分组,每个组至少有一个小球可以玩,而且每个组内不会有两个小朋友,相互不喜欢。现在给你这样一个幼儿园里小朋友之间关系的描述,做为老师,是否可以上好这节游戏课。

输入:

数据有多个case,每个case先输入两个值N(1<=N<=10)和M(1<=M<=10),表示有N个小朋友(从0到N-1标号),和M个小皮球。接着有N行,第i行先输入一个K(0<=K<N),表示第i个小朋友有喜欢一起玩的其他小朋友的个数,然后后面有K个整数,表示K个小朋友的标号(不重复)。如果A喜欢和B一起玩,则B也喜欢和A一起玩,这个数据在输入时保证。两个case之间有空行

输出:

数据有多个case,每个case先输入两个值N(1<=N<=10)和M(1<=M<=10),表示有N个小朋友(从0到N-1标号),和M个小皮球。接着有N行,第i行先输入一个K(0<=K<N),表示第i个小朋友有喜欢一起玩的其他小朋友的个数,然后后面有K个整数,表示K个小朋友的标号(不重复)。如果A喜欢和B一起玩,则B也喜欢和A一起玩,这个数据在输入时保证。两个case之间有空行

样例输入:

3 2
2 1 2
2 2 0
2 0 1

样例输出:

YES

自己写了半天 WA了很多次

后来就请教了留上星

题目意思就是需要使用到并查集的 然后进行顶点着色似的枚举 很简单的枚举 不过暴力的实在不会 只好重新学习学习了

代码如下

 

 

解题转自:http://www.cnblogs.com/zhuangli/archive/2008/09/10/1288632.html


  1. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  2. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  3. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n