GT and set

Accepts: 35

Submissions: 194

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

问题描述

有NN个集合，每个集合中有A_iAi个数。

你要将这NN个集合划成LL个部分，使得每个部分的集合至少有一个共有的数。

如果至少有一个解输出YESYES，否则输出NONO

输入描述

第一行一个数T表示数据组数。（TT\leq≤2020）

对于每一组数据：

第一行两个数NN和LL。

接下来NN行每行描述一个集合：

第一个数A_iAi表示该集合的大小，之后xx个互不相同的整数表示该集合的元素。

集合里的数字都是正整数且不大于300300.

1\leq1≤NN\leq30≤30，1\leq1≤L\leq5L≤5，1\leq1≤A_iAi\leq10≤10，1 \leq L \leq N1≤L≤N

hack时建议输出最后一行的行末回车;每一行的结尾不要输出空格。

输出描述

对于每组数据输出一行YESYES或NONO

输入样例

输出样例

NO

YES

Hint

对于第二个样例，有三个集合{1 2 3}，{4 5 6}，{2 5 6} 你要划成两个部分。

有一种方案是把第二个和第三个集合划成一个部分，第一个在另一个部分。有一种方案是把第二个和第三个集合划成一个部分，第一个在另一个部分。 第二个和第三个集合的数字有一个交集{6}，所以合法。

还有一种划分方案就是把第一个和第三个集合划成一个部分，第二个在另一个部分。

题解：

可能一些选手题意不是很清楚，我这里再提供一个转化后的问题：给出N个集合。每次你可以指定一个数，然后所有包含这个元素的集合可以被删掉。问你能否经过最多L轮操作使得所有集合都被删掉。因为LL只有5，考虑直接dfs。对于第一个集合，我们枚举它的那个公共的数是多少。然后线性扫描过去，找到接下来第一个没有这个数的集合。（它显然不能通过这个公共的数与第一个数在同一个部分）。对于这个集合，再枚举它公共的数是多少，然后线性扫描过去找到第一个没有这两个数的集合……这样重复5次后如果还是没有，就直接NO好了。若中途扫完序列就是YES。

自己也写了一个dfs暴力，但不知道为什么一直TLE。。。ORZ。。。

学习了别人的代码之后，发现就是：哇塞，竟然还可以这样搞。。。

其实自己之前做poj有一道题目与此类似，但是自己还是没能想到ORZ。。。。就是如果只判断一个数是否在一个集合里面，只有两个状态，这个数还不大的话，那么bitset一定要加入考虑的范围。

具体解释见代码：

#pragma warning(disable:4996)

#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

#include <string>

#include <cstring>

#include <bitset>

using namespace std;

int n, divide;//表示当前集合数和所要的划分数

bitset<305>set[35];//表示该集合里面有哪些数，一共最多30个集合

int dfs(int id, bitset<305>*tmp)

{

	if (id == n)//如果能够抵达n，说明n个集合都已经划分好了，自然正确了

	{

		return 1;

	}

	bitset<305>ans[35];

	for (int i = 0; i < divide; i++)//tmp代表各个划分当前的状态，即这个划分中是靠哪一个数来维系的

	{

		ans[i] = tmp[i];

	}

	for (int i = 0; i < divide; i++)//枚举该集合能弄到哪一个划分中，没有可去的就单独到一个划分里面去

	{

		ans[i] = tmp[i]&set[id];

		if (ans[i].count())//说明这个集合和之前的集合有交集，即可以放入到这个划分中，扫下一个集合

		{

			if (dfs(id + 1, ans))

				return 1;

		}

		ans[i] = tmp[i];//该集合不放入到这个划分中

	}

	return 0;

}

int main()

{

	//freopen("i.txt","r",stdin);

	//freopen("o.txt","w",stdout);

	int t, cnt, x;

	scanf("%d", &t);

	while (t--)

	{

		scanf("%d%d", &n, ÷);

		bitset<305>tmp[35];

		for (int i = 0; i < n; i++)

		{

			scanf("%d", &cnt);

			set[i].reset();

			for (int j = 0; j < cnt; j++)

			{

				scanf("%d", &x);

				set[i][x] = 1;

			}

			for (int j = 0; j <= 300; j++)

			{

				tmp[i][j] = 1;

			}

		}

		int flag = dfs(0, tmp);

		if (flag)

			puts("YES");

		else

			puts("NO");

	}

	//system("pause");

	return 0;

}

巴特西

HDU 5506：GT and set bitset+暴力

GT and set

最新文章

热门文章