必威体育Betway必威体育官网
当前位置:首页 > IT技术

G将军有一支训练有素的军队,这个军队除开G将军外...

时间:2019-09-15 17:40:00来源:IT技术作者:seo实验室小编阅读:72次「手机版」
 

松坡将军

此为蓝桥杯2015校内选拔第七题:

G将军有一支训练有素的军队,这个军队除开G将军外,每名士兵都有一个直接上级(可能是其他士兵,也可能是G将军)。现在G将军将接受一个特别的任务,需要派遣一部分士兵(至少一个)组成一个敢死队,为了增加敢死队队员的独立性,要求如果一名士兵在敢死队中,他的直接上级不能在敢死队中。请问,G将军有多少种派出敢死队的方法。注意,G将军也可以作为一个士兵进入敢死队。输入格式:输入的第一行包含一个整数n,表示包括G将军在内的军队的人数。军队的士兵从1至n编号,G将军编号为1。接下来n-1个数,分别表示编号为2, 3, ..., n的士兵的直接上级编号,编号i的士兵的直接上级的编号小于i。输出格式:输出一个整数,表示派出敢死队的方案数。由于数目可能很大,你只需要输出这个数除10007的余数即可。

样例输入1

3

1 1

样例输出1

4

样例说明

这四种方式分别是:1. 选1;2. 选2;3. 选3;4. 选2, 3。

样例输入2

7

1 1 2 2 3 3

样例输出2

40

解此题的思路如下:依照题目,下属的直接上属不能进入敢死队,依照下图,程序最终要求的是将右边树的叶子子节点个数求出,再减去所有人都不来的一种情况即可。

                                         

下面的程序,对于取余数的部分处理的不是很好,应该可以通过的数据范围有限,取余数的有个离散数学的什么定理好像是能解决的,因能力有限,还未掌握。。

函数基本流程:

1、每次计数一次的条件,到达依据士兵编号记录上属的一维数组a[100001]的尾部,count++

2、若此士兵已被访问,则调用dfs,访问下一位士兵

3、若此士兵未被访问,则将其分为来与不来两种情况(被访问意味着不能再次被访问,包括两种情况,情况1为编号为i的士兵来或不来,此时visited[i]=1,情况2为士兵I为某个要来直接上属的下属是,此时visited[i]=2)

具体C代码如下,编译通过的环境为DEV-C++:

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
static int count; //定义全局静态变量,记录总的情况数
void dfs(int a[100001], int visited[100001], int i){
	if (a[i] == -1){ //每次计数一次的条件,到达依据士兵编号记录上属的一维数组a[100001]的尾部,count++
		count++;
		return;
	}
	if (a[i] != -1 && visited[i] >= 1){ //若此士兵已被访问,则调用dfs,访问下一位士兵
		dfs(a, visited, ++i);
	}
	if (a[i] != -1 && visited[i] == 0){ //若此士兵未被访问
		visited[i] = 1; //此士兵来时
		for (int j = 0; a[j] != -1; j++){ //其下属均将visited[j]=2,作为已被访问
			if (a[j] == i){
				visited[j] = 2;
			}
		}
		dfs(a, visited, ++i);
		i--; //此士兵不来时,首先将上面假设他来的数据变回未方式的状态
		for (int j = 0; a[j] != -1; j++){
			if (a[j] == i)
				visited[j] = 0;
			if (i < j && visited[j]==1) //此处需注意,标号为1的,且i<j的才能恢复原状,而标号为2且i<j的不能恢复原状
				visited[j] = 0;
		}
		dfs(a, visited, ++i);
	}
}
int main()
{
	int n, a[100001], i = 0, j = 1, visited[100001] = { 0 };
	char temp[100000];
	a[0] = -2;
	scanf("%d", &n);
	if(n!=1&&n>0){ //输入格式控制
		getchar();
	while (1){
		temp[i++] = getchar();
		if (temp[i - 1] == ' '){
			temp[i - 1] = '\0';
			a[j++] = atoi(temp) - 1;
			strcpy(temp, "");
			i = 0;
		}
		if (temp[i - 1] == '\n'){
			temp[i - 1] = '\0';
			a[j++] = atoi(temp) - 1;
			strcpy(temp, "");
			i = 0;
			break;
		}
	}
	a[j] = -1;
	dfs(a, visited, i);
	printf("%d", (count - 1) % 10007);
	}
	if(n==1){ //考虑只有将军一人的情况
		printf("%d", n);	
	}
	if(n<0){
		printf("Unvalid input!");
	}	
	return 0;
}

相关阅读

分享到:

栏目导航

推荐阅读

热门阅读