BZOJ 1005: [HNOI2008]明明的烦恼(prufer数列)

时间:2021-01-14 00:52:05

http://www.lydsy.com/JudgeOnline/problem.php?id=1005

题意:

Description

  自从明明学了树的结构,就对奇怪的树产生了兴趣......给出标号为1到N的点,以及某些点最终的度数,允许在
任意两点间连线,可产生多少棵度数满足要求的树?

Input

  第一行为N(0 < N < = 1000),
接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1

Output

  一个整数,表示不同的满足要求的树的个数,无解输出0

思路:
又了解了一个神奇的东西,prufer数列!!!

prufer数列,可以用来解一些关于无根树计数的问题。

prufer数列是一种无根树的编码表示,对于一棵n个节点带编号的无根树,对应唯一一串长度为n-1的prufer编码。

(1)无根树转化为prufer序列。

首先定义无根树中度数为1的节点是叶子节点。

找到编号最小的叶子并删除,序列中添加与之相连的节点编号,重复执行直到只剩下2个节点。

如下图的树对应的prufer序列就是3,5,1,3。

BZOJ 1005: [HNOI2008]明明的烦恼(prufer数列)

具体实现可以用一个set搞定,维护度数为1的节点。复杂度O(nlogn)。

(2)prufer序列转化为无根树。

设点集V={1,2,3,...,n},每次取出prufer序列中最前面的元素u,在V中找到编号最小的没有在prufer序列中出现的元素v,给u,v连边然后分别删除,最后在V中剩下两个节点,给它们连边。最终得到的就是无根树。

具体实现也可以用一个set,维护prufer序列中没有出现的编号。复杂度O(nlogn)。

最后有一个很重要的性质就是prufer序列中某个编号出现的次数就等于这个编号的节点在无根树中的度数-1。

BZOJ 1005: [HNOI2008]明明的烦恼(prufer数列)

接下来就是按照这个式子计算即可,用java计算会比较方便。

 import java.math.*;
import java.util.Scanner; public class Main{
static int n;
static int d[]=new int[1005];
static BigInteger c[]=new BigInteger[1005];
static BigInteger ans; public static void main(String[] args){
Scanner in=new Scanner(System.in);
int flag=0, tot=0, cnt=0;
while(in.hasNextInt()){
n=in.nextInt();
for(int i=0;i<n;i++){
d[i]=in.nextInt();
if(d[i]==0 || d[i]>n-1) flag=1;
if(d[i]==-1) continue;
tot+=d[i]-1;
cnt++;
} if(flag==1) {System.out.println("0");continue;}
c[0]=BigInteger.valueOf(1);
for(int i=1;i<=n;i++) c[i]=c[i-1].multiply(BigInteger.valueOf(i));
ans=c[n-2];
for(int i=1;i<=n-2-tot;i++) ans=ans.multiply(BigInteger.valueOf(n-cnt));
ans=ans.divide(c[n-2-tot]);
for(int i=0;i<n;i++){
if(d[i]==-1) continue;
ans=ans.divide(c[d[i]-1]);
}
System.out.println(ans);
}
in.close();
}
}

BZOJ 1005: [HNOI2008]明明的烦恼(prufer数列)的更多相关文章

  1. BZOJ 1005 &lbrack;HNOI2008&rsqb;明明的烦恼 &starf;&lpar;Prufer数列&rpar;

    题意 N个点,有些点有度数限制,问这些点可以构成几棵不同的树. 思路 [Prufer数列] Prufer数列是无根树的一种数列.在组合数学中,Prufer数列是由一个对于顶点标过号的树转化来的数列,点 ...

  2. bzoj 1005&colon; &lbrack;HNOI2008&rsqb;明明的烦恼 prufer编号&amp&semi;&amp&semi;生成树计数

    1005: [HNOI2008]明明的烦恼 Time Limit: 1 Sec  Memory Limit: 162 MBSubmit: 2248  Solved: 898[Submit][Statu ...

  3. BZOJ 1005 &lbrack;HNOI2008&rsqb;明明的烦恼 &lpar;Prufer编码 &plus; 组合数学 &plus; 高精度&rpar;

    1005: [HNOI2008]明明的烦恼 Time Limit: 1 Sec  Memory Limit: 162 MBSubmit: 5786  Solved: 2263[Submit][Stat ...

  4. bzoj 1005 &lbrack;HNOI2008&rsqb; 明明的烦恼 &lpar;prufer编码&rpar;

    [HNOI2008]明明的烦恼 Time Limit: 1 Sec  Memory Limit: 162 MBSubmit: 5907  Solved: 2305[Submit][Status][Di ...

  5. BZOJ&period;1005&period;&lbrack;HNOI2008&rsqb;明明的烦恼&lpar;Prufer 高精 排列组合&rpar;

    题目链接 若点数确定那么ans = (n-2)!/[(d1-1)!(d2-1)!...(dn-1)!] 现在把那些不确定的点一起考虑(假设有m个),它们在Prufer序列中总出现数就是left=n-2 ...

  6. BZOJ 1005 &lbrack;HNOI2008&rsqb; 明明的烦恼(组合数学 Purfer Sequence)

    题目大意 自从明明学了树的结构,就对奇怪的树产生了兴趣...... 给出标号为 1 到 N 的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树? Input 第一行为 N( ...

  7. BZOJ 1005&colon; &lbrack;HNOI2008&rsqb;明明的烦恼&lpar; 组合数学 &plus; 高精度 &rpar;

    首先要知道一种prufer数列的东西...一个prufer数列和一颗树对应..然后树上一个点的度数-1是这个点在prufer数列中出现次数..这样就转成一个排列组合的问题了.算个可重集的排列数和组合数 ...

  8. BZOJ 1005&colon; &lbrack;HNOI2008&rsqb;明明的烦恼 Purfer序列 大数

    1005: [HNOI2008]明明的烦恼 Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://www.lydsy.com/JudgeOnline/ ...

  9. BZOJ 1005 &lbrack;HNOI2008&rsqb;明明的烦恼 purfer序列,排列组合

    1005: [HNOI2008]明明的烦恼 Description 自从明明学了树的结构,就对奇怪的树产生了兴趣......给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少 ...

随机推荐

  1. MySQL的重装问题解决方法

    最近在工作上遇到了在Windows环境中将MySQL重装的问题,今天记录一下我的解决过程. 首先因为某些原因,我不得不把mysql卸载,然后重装,不论我用控制面板的卸载删除程序方式还是安全卫士的卸载, ...

  2. tar&colon; Removing leading &grave;&sol;’ from member names

    tar: Removing leading `/’ from member names+2 分类:Web服务器 标签:tar 3,910人浏览   这并不是一个错误,而是一个警告,原因很简单,就是你在 ...

  3. springmvc使用pojo和servlet原生api作为参数

    一.Pojo作为参数: 实体: package com.hy.springmvc.entities; public class User { private String username; priv ...

  4. Python 随笔-1

    python的发展史: python 2.7            July 3,2010  目前业内主流使用的工业版本 主讲3.0 32bit = 内存的最大寻址空间为2*32    4G的空间 6 ...

  5. js中session操作

    // 保存数据到sessionStorage sessionStorage.setItem('key', 'value');   // 从sessionStorage获取数据 var data = s ...

  6. Xgboost&colon; 一把屠龙刀的自我修养

    目录 引言 Xgboost 参考文献 引言 集成学习, 在机器学习中是一个非常重要的思想: 把多个弱分类器精巧地组合在一起,成为一个很强大的学习器. 集成学习也因此一直处在风口浪边. 集成学习主要分为 ...

  7. 12C -- ORA-01033&colon; ORACLE initialization or shutdown in progress

    初装oracle 12.2 rac数据库. 登录RAC数据库中第1节点 $ sqlplus '/as sysdba' SQL> select name,open_mode from v$pdbs ...

  8. SD从零开始55-56&comma; 风险管理&comma; 付款卡

    [原创] SD从零开始55 风险管理的内容 应收款风险最小化Risk Minimization for Receivables 每个信用政策的目的是减少由客户应收款带来的风险: 连同信用管理,你也有权 ...

  9. string与位运算

    1.String String  a="abc";  会在常量池中开辟一个空间,保存"abc" String  b=new String("abc&q ...

  10. Oracle session active 和 inactive 状态 说明

    Oracle session active 和 inactive 状态 说明 原创 2011年06月12日 13:08:00 标签: session / oracle / database / ser ...