派遣敢死队问题

问题描述

​ 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

数据规模与约定

  • 对于20%的数据,n ≤ 20;

  • 对于40%的数据,n ≤ 100;

  • 对于100%的数据,1 ≤ n ≤ 100000。

    资源约定:

  • 峰值内存消耗 < 256M

  • CPU消耗 < 2000ms

请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。

所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。

注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include, 不能通过工程设置而省略常用头文件。

提交时,注意选择所期望的编译器类型。

思路

1、首先将所有士兵直属上级的编号放于数组a;
2、每个人有两种选择,去和不去,用0和1表示,转换为二进制放于数组b;
3、最后判断每个士兵是不是与其直属上级同时执行任务,进而对count进行统计。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//
// main.c
// 派遣敢死队问题
//
// Created by Canvas on 2018/12/31.
// Copyright © 2018 Canvas. All rights reserved.
//

#include <stdio.h>
#include <math.h>

int main() {
int number;
int count=0;
int flag;
scanf("%d",&number);//派遣的人数

int i,j;
int temp;
int a[number],b[number];//a
a[0]=0;//将军

for(i=1;i<number;i++){
scanf("%d",&a[i]);//每个人的直属上级
}

for(i=1;i<pow(2,number);i++){
temp=i;
for(j=0;j<number;j++){
//遍历所有情况
b[j]=temp%2;
temp/=2;
}

flag=1;
for(j=1;j<number;j++){
//将军没有上级,不用判断
if(b[j]==1&&b[a[j]-1]==1){
//判断是否士兵和上级同时执行任务
//b[j]为编号为j+1的士兵去不去
//b[a[j]-1]为编号为j+1的士兵的直接上级去不去
flag=0;
break;
}
}

if(flag==1)
count++;
}

printf("%d\n",count);
return 0;
}
-------------本文结束感谢您的阅读-------------
请站长喝杯咖啡吧´◡`