首页 > 代码库 > SGU 238 Uncle Vasya and Bags for Potatoes 规律+构造

SGU 238 Uncle Vasya and Bags for Potatoes 规律+构造

题目链接:点击打开链接

题意:

地上有n个背包,编号从1-n

下面n行第i行: 第一个数字表示背包i里有几个背包。

这样就得到了n个背包的一个状态。


问:有多少个背包状态可以通过一系列的操作达到输入的状态。

每步操作:

选取一个在地面上的背包a,然后把a背包内部的背包放到地上,把地上的放到a背包内部


思路:

我们可以把背包的嵌套关系 用一个图来表示。

就得到了一个森林,然后以地面为根把所有在地上的包相连,就得到了一棵树。

那么对于每次操作相当于换根操作。

所以一共有n-1个方法可以把根移动到其他地方。(画图模拟一下)

(1个背包时要特判)


#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

int main() {
	int n, x, y;
	while (~scanf("%d", &n)) {
		for (int i = 1; i <= n; ++i) {
			scanf("%d", &x);
			while (x -- > 0) {
				scanf("%d", &y);
			}
		}
		if (n == 1)
			puts("1");
		else
			printf("%d\n", n + 1);
	}
	return 0;
}


SGU 238 Uncle Vasya and Bags for Potatoes 规律+构造