正文 

当前位置： 首页 > java > java教程

洛谷p1472奶牛家谱cowpedigrees

zbtrs zbtrs     2022-08-07     528

关键词：

 P1472 奶牛家谱 Cow Pedigrees

    • 102通过
    • 193提交
  • 题目提供者该用户不存在
  • 标签USACO
  • 难度普及+/提高

  讨论  题解  

最新讨论

  • 暂时没有讨论

题目描述

农民约翰准备购买一群新奶牛。 在这个新的奶牛群中, 每一个母亲奶牛都生两个小奶牛。这些奶牛间的关系可以用二叉树来表示。这些二叉树总共有N个节点(3 <= N < 200)。这些二叉树有如下性质:

每一个节点的度是0或2。度是这个节点的孩子的数目。

树的高度等于K(1 < K < 100)。高度是从根到最远的那个叶子所需要经过的结点数; 叶子是指没有孩子的节点。

有多少不同的家谱结构? 如果一个家谱的树结构不同于另一个的, 那么这两个家谱就是不同的。输出可能的家谱树的个数除以9901的余数。

输入输出格式

输入格式：

 

两个空格分开的整数, N和K。

 

输出格式：

 

一个整数，表示可能的家谱树的个数除以9901的余数。

 

输入输出样例

输入样例#1：
5 3
输出样例#1：
2

说明

翻译来自NOCOW

USACO 2.3

分析：很显然求方案数选择dp,关键是怎么dp呢？可以从题目中得知影响结果的只有节点数和高度了，那么设f[i][j]为高度为i，节点数为j的二叉树的个数，怎么转移呢？很显然是从它的左右子树上转移过来的，二叉树的方案数=左子树的方案数*右子树的方案数，对于节点的个数，左子树+右子树的和是一定的，所以我们枚举一个子树的节点个数那么另一个子树的节点个数就出来了，如果要构成高度为i的二叉树，那么左右子树中至少要有一个高度为i-1的，那么就要分3中情况讨论，一个是i-1,一个比i-1小;两个都是i-1,将3种情况的方案数加起来就可以了.那么怎么求比i-1小的方案数呢？可以类比noip2015子串，利用前缀和原理，比i-1小就是把比i-2小的加上i-1的即可，这个操作可以在推算f数组的时候进行.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
const int mod = 9901;
int f[110][210],n,k,t[110][210];

int main()
{
    scanf("%d%d", &n, &k);
    f[1][1] = 1;
    for (int i = 2; i <= k; i++)
        for (int j = 1; j <= n; j++)
        {
            for (int p = 1; p < j; p++)
            {
                f[i][j] = (f[i][j] + t[i - 2][p] * f[i - 1][j - p - 1]) % mod;
                f[i][j] = (f[i][j] + t[i - 2][j - p - 1] * f[i - 1][p]) % mod;
                f[i][j] = (f[i][j] + f[i - 1][p] * f[i - 1][j - p - 1]) % mod;
            }
            t[i - 1][j] = (t[i - 2][j] + f[i - 1][j]) % mod;
        }
    printf("%d
", f[k][n]);

    return 0;
}

 

[luogup1472]奶牛家谱cowpedigrees（dp）

传送门 一个深度为i的树可以由一个根节点外加两个深度为i-1的树组成，这就决定了DP该怎么写。然而我真的没有想到。 f[i][j]表示深度为i节点数为j的个数sum[i][j]表示深度小于等于i节点树为j的个数 #include<cstdio>#de... 查看详情

luogu1472奶牛家谱cowpedigrees[动态规划](代码片段)

一时暴搜一时爽一直暴搜一直爽 cxl居然和我写的同款dfs，天呢菜鸡开始对这题并没有什么想法状态方程死活想不出来还是暴搜好1#include<bits/stdc++.h>2usingnamespacestd;3#definelllonglong4#definergregister5constintN=200,K=100,P=9901;6intn,k,f[K+5... 查看详情

洛谷p1827美国血统americanheritagelabel：字符串water

题目描述农夫约翰非常认真地对待他的奶牛们的血统。然而他不是一个真正优秀的记帐员。他把他的奶牛们的家谱作成二叉树，并且把二叉树以更线性的“树的中序遍历”和“树的前序遍历”的符号加以记录而不是... 查看详情

洛谷p1827美国血统americanheritage

P1827美国血统AmericanHeritage题目描述农夫约翰非常认真地对待他的奶牛们的血统。然而他不是一个真正优秀的记帐员。他把他的奶牛们的家谱作成二叉树，并且把二叉树以更线性的“树的中序遍历”和“树的前序遍历&rdquo... 查看详情

洛谷p1827美国血统americanheritage

P1827美国血统AmericanHeritage54通过90提交题目提供者JOHNKRAM标签USACO难度普及- 提交  讨论  题解  最新讨论暂时没有讨论题目描述农夫约翰非常认真地对待他的奶牛们的血统。然而他不是一个真正优秀的记帐... 查看详情

[洛谷2814]家谱

思路：字符串哈希，然后用普通的并查集维护即可。1#include<cstdio>2#include<cctype>3#include<cstring>4constintmod=19260817;5charname[mod][7];6inlineinthash(char*s){7intn=strlen(s),ret=0;8for(inti=0;i<n;i++ 查看详情

美国血统

【题目描述】农夫约翰把他的奶牛们的家谱作成二叉树，并且把二叉树以更线性的“树的中序遍历”和“树的前序遍历”的符号加以记录而不是用图形的方法。你的任务是在被给予奶牛家谱的“树中序遍历”和... 查看详情

家谱（gen）——洛谷p2814

1#include<iostream>2#include<string>3#include<map>4usingnamespacestd;5map<string,string>mp;6intmain()7{8strings1="",s2="";9while(cin>>s1)10{11mp.clear();12while(s1!="$")1 查看详情

洛谷p2814家谱

P2814家谱题目背景现代的人对于本家族血统越来越感兴趣。题目描述给出充足的父子关系，请你编写程序找到某个人的最早的祖先。输入输出格式输入格式： 输入由多行组成，首先是一系列有关父子关系的描述，其中每一组... 查看详情

洛谷p2814家谱

P2814家谱题目背景现代的人对于本家族血统越来越感兴趣。题目描述给出充足的父子关系，请你编写程序找到某个人的最早的祖先。输入输出格式输入格式： 输入由多行组成，首先是一系列有关父子关系的描述，其中每一组... 查看详情

洛谷p1578奶牛浴场

P1578奶牛浴场题目描述由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产... 查看详情

洛谷p2345奶牛集会

题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i头奶牛的坐标为Xi，没有两头... 查看详情

洛谷p2345奶牛集会

题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i头奶牛的坐标为Xi，没有两头... 查看详情

[wc2002][洛谷p1578]奶牛浴场

洛谷题解里那个人可真是话多呢。 题目描述由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛... 查看详情

洛谷p2345奶牛集会

题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i头奶牛的坐标为Xi，没... 查看详情

洛谷p2345奶牛集会

题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i头奶牛的坐标为Xi，没... 查看详情

洛谷p1154奶牛分厩

P1154奶牛分厩农夫约翰有Ｎ（1<=Ｎ<=5000）头奶牛，每头奶牛都有一个唯一的不同于其它奶牛的编号Ｓi，所有的奶牛都睡在一个有Ｋ个厩的谷仓中，厩的编号为０到Ｋ－１。每头奶牛都知道自己该睡在哪一个厩中，因为约翰教... 查看详情

洛谷——p1154奶牛分厩

P1154奶牛分厩题目描述农夫约翰有Ｎ（1<=Ｎ<=5000）头奶牛，每头奶牛都有一个唯一的不同于其它奶牛的编号Ｓi，所有的奶牛都睡在一个有Ｋ个厩的谷仓中，厩的编号为０到Ｋ－１。每头奶牛都知道自己该睡在哪一个厩中，因... 查看详情