Java实现蓝桥杯G将军的示例代码

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；
选2；
选3；
选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

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

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。
注意：主类的名字必须是：Main，否则按无效代码处理。

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
  public static int n;
  public static int MOD = 10007;
  public static ArrayList<Integer>[] list;
  public static long[][] dp;

  public void dfs(int root) {
    dp[root][0] = 1;
    dp[root][1] = 1;
    for(int i = 0;i < list[root].size();i++) {
      int child = list[root].get(i);
      dfs(child);
      dp[root][0] = dp[root][0] * (dp[child][0] + dp[child][1]) % MOD;
      dp[root][1] = dp[root][1] * dp[child][0] % MOD;
    }
  }

  @SuppressWarnings("unchecked")
  public static void main(String[] args) {
    Main test = new Main();
    Scanner in = new Scanner(System.in);
    n = in.nextInt();
    list = new ArrayList[n + 1];
    for(int i = 1;i <= n;i++)
      list[i] = new ArrayList<Integer>();
    for(int i = 2;i <= n;i++) {
      int father = in.nextInt();
      list[father].add(i);
    }
    dp = new long[n + 1][2];
    test.dfs(1);
    long result = (dp[1][0] + dp[1][1] - 1) % MOD;
    System.out.println(result);
  }
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • java冒泡排序算法代码

    复制代码 代码如下: /** * 原理: * 进行n次循环,每次循环从后往前对相邻两个元素进行比较,小的往前,大的往后 *  * 时间复杂度: * 平均情况:O(n^2) * 最好情况:O(n) * 最坏情况:O(n^2) * * 稳定性:稳定 **/public class 冒泡排序 { public int[] bubbleSort(int[] a, int n) {        for (int i = 0; i < n; i++) {            int flag = 0; 

  • java实现的AES加密算法完整实例

    本文实例讲述了java实现的AES加密算法.分享给大家供大家参考,具体如下: import javax.crypto.Cipher; import javax.crypto.spec.IvParameterSpec; import javax.crypto.spec.SecretKeySpec; import android.util.Base64; /** * @author vipin.cb , vipin.cb@experionglobal.com <br> * Sep 27, 2013

  • java实现MD5加密算法的实例代码

    复制代码 代码如下: package other; import java.security.MessageDigest;import java.security.NoSuchAlgorithmException;/* * MD5 算法*/public class MD5 { // 全局数组    private final static String[] strDigits = { "0", "1", "2", "3", &

  • 分享Java常用几种加密算法(四种)

    对称加密算法是应用较早的加密算法,技术成熟.在对称加密算法中,数据发信方将明文(原始数据)和加密密钥(mi yue)一起经过特殊加密算法处理后,使其变成复杂的加密密文发送出去.收信方收到密文后,若想解读原文,则需要使用加密用过的密钥及相同算法的逆算法对密文进行解密,才能使其恢复成可读明文.在对称加密算法中,使用的密钥只有一个,发收信双方都使用这个密钥对数据进行加密和解密,这就要求解密方事先必须知道加密密钥. 简单的java加密算法有: BASE 严格地说,属于编码格式,而非加密算法 MD(Mes

  • 用java实现冒泡排序算法

    冒泡排序的算法分析与改进 交换排序的基本思想是:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止. 应用交换排序基本思想的主要排序方法有:冒泡排序和快速排序. 复制代码 代码如下: public class BubbleSort implements SortUtil.Sort{ public void sort(int[] data) { int temp; for(int i=0;i<data.length;i++){ for(int j=data.le

  • Java 对称加密几种算法分别实现

    Java 对称加密几种算法分别实现

    Java 对称加密使用DES / 3DES / AES 这三种算法分别实现 有两句话是这么说的: 1)算法和数据结构就是编程的一个重要部分,你若失掉了算法和数据结构,你就把一切都失掉了. 2)编程就是算法和数据结构,算法和数据结构是编程的灵魂. 注意,这可不是我说的,是无数程序员总结的,话说的很实在也很精辟,若想长久可持续发展,多研究算法还是很有必要的,今天我给大家说说加密算法中的对称加密算法,并且这里将教会大家对称加密算法的编程使用.包含DES.3DES和AES三种对称加密算法的编程使用,干货

  • 史上最全的java随机数生成算法分享

    史上最全的java随机数生成算法分享

    复制代码 代码如下: String password = RandomUtil.generateString(10); 源码如下: 复制代码 代码如下: package com.javaniu.core.util;import java.util.Random;public class RandomUtil { public static final String ALLCHAR = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRS

  • 十种JAVA排序算法实例

    排序算法有很多,所以在特定情景中使用哪一种算法很重要.为了选择合适的算法,可以按照建议的顺序考虑以下标准: (1)执行时间 (2)存储空间 (3)编程工作  对于数据量较小的情形,(1)(2)差别不大,主要考虑(3):而对于数据量大的,(1)为首要. 一.冒泡(Bubble)排序 复制代码 代码如下: void BubbleSortArray() {       for(int i=1;i<n;i++)       {         for(int j=0;i<n-i;j++)       

  • 关于各种排列组合java算法实现方法

    一.利用二进制状态法求排列组合,此种方法比较容易懂,但是运行效率不高,小数据排列组合可以使用 复制代码 代码如下: import java.util.Arrays; //利用二进制算法进行全排列//count1:170187//count2:291656 public class test {    public static void main(String[] args) {        long start=System.currentTimeMillis();        count

  • Java实现蓝桥杯G将军的示例代码

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

  • Java实现蓝桥杯数独游戏的示例代码

    Java实现蓝桥杯数独游戏的示例代码

    你一定听说过"数独"游戏. 如图,玩家需要根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行.每一列.每一个同色九宫内的数字均含1-9,不重复. 数独的答案都是唯一的,所以,多个解也称为无解. 本图的数字据说是芬兰数学家花了3个月的时间设计出来的较难的题目.但对会使用计算机编程的你来说,恐怕易如反掌了. 本题的要求就是输入数独题目,程序输出数独的唯一解.我们保证所有已知数据的格式都是合法的,并且题目有唯一的解. 格式要求: 输入9行,每行9个数字,0代表未知,其它数字为

  • Java实现蓝桥杯 算法提高 线段和点

    目录 一.算法提高 线段和点 1.时间限制 2.问题描述 3.输入格式 4.输出格式 5.数据规模和约定 一.算法提高 线段和点 1.时间限制 1.0s 内存限制:256.0MB 2.问题描述 有n个点和m个区间,点和区间的端点全部是整数,对于点a和区间[b,c],若a>=b且a<=c,称点a满足区间[b,c]. 求最小的点的子集,使得所有区间都被满足. 3.输入格式 第一行两个整数n m 以下n行 每行一个整数,代表点的坐标 以下m行 每行两个整数,代表区间的范围 4.输出格式 输出一行,最

  • Java实现动态获取图片验证码的示例代码

    本文介绍了Java实现动态获取图片验证码的示例代码,分享给大家,具体如下: import javax.imageio.ImageIO; import java.awt.*; import java.awt.image.BufferedImage; import java.io.FileOutputStream; import java.io.IOException; import java.io.OutputStream; import java.io.UnsupportedEncodingEx

  • JAVA实现经典游戏坦克大战的示例代码

    JAVA实现经典游戏坦克大战的示例代码

    目录 前言 主要设计 功能截图 代码实现 总结 前言 小时候大家都玩过坦克大战吧,熟悉的旋律和丰富的关卡陪伴了我们一整个寒暑假,还记得传说中的经典坦克大战 吗?那些怀旧的记忆,伴随着我们一起走过来的经典坦克大战,刚开始那战战兢兢,屡屡被敌人坦克击毁的情景历历在目.现在好了,再也不用担心敌人坦克了,可 以横冲直撞,横扫敌人坦克了.快哉!!! <坦克大战>游戏以坦克战斗为主题,用java语言实现,采用了swing技术进行了界面化处理,设计思路用了面向对象思想. 主要需求 可以生成不同的地图,消灭地

  • Java实现游戏飞机大战-III的示例代码

    Java实现游戏飞机大战-III的示例代码

    目录 前言 主要设计 功能截图 代码实现 游戏面板类 商店类 总结 前言 <飞机大战-III>是一款融合了街机.竞技等多种元素的经典射击手游.华丽精致的游戏画面,超炫带感的技能特效,超火爆画面让你肾上腺素爆棚,给你带来全方位震撼感受,体验飞行战斗的无限乐趣. 游戏是用java语言实现,采用了swing技术进行了界面化处理,设计思路用了面向对象思想. 主要需求 基于Java Swing,以飞机大战为原形,以抗日电视剧<亮剑>中的“李云龙”为主题,实现菜单.选关.难度.等级.技能等功能

  • Java实现经典游戏推箱子的示例代码

    Java实现经典游戏推箱子的示例代码

    目录 前言 主要设计 功能截图 代码实现 核心类 声音播放类 总结 前言 <推箱子>推箱子是一个古老的游戏,目的是在训练你的逻辑思考能力.在一个狭小的仓库中,要求把木箱放到指定的位置,稍不小心就会出现箱子无法移动或者通道被堵住的情况,所以需要巧妙的利用有限的空间和通道,合理安排移动的次序和位置,才能顺利的完成任务. 游戏是用java语言实现,采用了swing技术进行了界面化处理,设计思路用了面向对象思想. 主要需求 控制搬运工上下左右移动,来将箱子推到指定地点 主要设计 1.游戏面板生成显示

  • Java实现经典捕鱼达人游戏的示例代码

    Java实现经典捕鱼达人游戏的示例代码

    目录 前言 主要设计 功能截图 代码实现 游戏窗体 鱼 鱼池类继承自Jpanel 总结 前言 <捕鱼达人>是一款以深海狩猎为题材的休闲竞技游戏.这是一场海底世界的远征,享受捕获大鱼的乐趣,但不是所有的鱼都是友善的,它们会用自己的方式保护自己,保卫属于自己的海底世界.当然,这里也是冒险与机遇共存的地方,诸多埋藏于海底的宝藏等待着被探寻. 游戏是用java语言实现,采用了swing技术进行了界面化处理,设计思路用了面向对象思想. 主要需求 在鱼池中有很多鱼,鱼各自游动. 有一张渔网,随鼠标移动,点

  • Java实现经典游戏Flappy Bird的示例代码

    Java实现经典游戏Flappy Bird的示例代码

    目录 前言 主要设计 功能截图 代码实现 游戏启动类 核心类 工具类 总结 前言 <布谷鸟闯关-简单版>是一个基于java的布谷鸟闯关游戏,摁上键控制鸟的位置穿过管道间的缝隙,需要做碰撞检测,监听键盘事件,背景图片的切换,障碍物管道产生时y轴上需要随机位置. 主要设计 设计游戏界面,用swing实现 设计背景 设计移动墙 设计布谷鸟 设计障碍物 设计背景音乐和音效 由几个关键的布尔类型变量start,crash,over是产生键键盘事件时用来控制界面显示的弹框的 操作:空格键开始游戏,ente

  • Java实现接月饼小游戏的示例代码

    Java实现接月饼小游戏的示例代码

    目录 前言 主要设计 功能截图 代码实现 游戏启动类 核心类 画面绘制 总结 前言 <接月饼小游戏>是一个基于java的自制游戏,不要被月亮砸到,尽可能地多接月饼. 此小项目可用来巩固JAVA基础语法,swing的技巧用法. 主要设计 设计游戏界面,用swing实现 设计背景 设计得分物体-月饼,碰到加一分 设计障碍物-月亮,碰到会死亡 监听鼠标的左右键,用来控制篮子左右移动 设计积分系统 将resource文件夹设为resource(Project Manage中可以设置),因为要用里面的图

随机推荐