gougou1039
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
1039
Family
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1509
15 2006-08-19 06:49:43 00:07.79 27716K C++ glimpse
拓扑排序+高精度。
人是种奇怪的小动物。作为一头ws熊，我也这样。没有AC时把这题骂得狗血喷头，AC了就开始教育ZZT，说这是道经典题。或许看别人做题小郁闷时，心里会窃喜，嘎嘎。（大家不要学我哦）
不过AC这道题的旅程真的有点坎坷。我大约在7月29日AC了其余39题，离圆满只有一题之遥。尝试几次之后，终于在20天后鼓足勇气，用了将近8个小时AC掉了它。
题目的描述比较的清楚，相信大家看了一遍都看懂了。OK。有多少人看明白81.5%是怎么算出来的？那就再看一遍题，看看题目里有没有定义？……不用找了，是没有的。全靠你YY。
我自己有始至终都没有YY出。ZZT帮我YY的，两个怪物a,b之间的关系定义如下：
1．如果a == b，那么relation = 100%
2．如果a，b都是天生Monster，那么他们之间的relation = 0
3．relation = (a 和 b 父亲的relation + a 和 b 母亲的relation)/2
我们看一下sample：
1，2都是野生Monster，毫无疑问是0
2和6母亲1的relation的关系为0，2和6的父亲2的relation的关系为100，所以2和6的关系为50%
7和5的关系：5和7的父亲5的relation为100，5和7母亲6的relation为62.5（5和4为25，5和5为 100），所以7和5的relation为81.5%
3和3的relation为100%
弄明白两个怪物之间的血缘计算方法，这个题目就算解决了一半。因为询问的次数比较多并且方便coding，我决定将任意两个怪物之间的relation 都计算出来。
直接写二重循环肯定是不行的。因为还没有理清怪物之间的父子关系，很有可能在计算a,b的时候，a和b父亲的关系还没有计算。
我的方法是先拓扑一下怪物的家谱，然后按照家谱计算怪物之间的关系。设怪物的拓扑顺序在数组ret中
{{{
1
2 for( int i = 0 ; i < n; i++ )
3 for( int j = 0; j<=i; j++ )
4 a[ret[i]][ret[j]]=a[ret[j]][ret[i]]=cal(i,j);
5
}}}
这样可以保证在计算ret[i]和ret[j]之前，ret[i]和ret[j]父母（如果有）的关系都计算过。
然后根据查询，直接out结果就可以了。
如果题目能够让我们只保留6位小数，到这里就可以AC了。然而变态的题目要求输出一个准确的值。
Double肯定是不行的，也没有大浮点数的类，怎么办呢?伟大的狗狗提供了分数类，只要将分子分母从int改成那个300行的大数，理论上就可以得到正确的解。事实上我做了尝试，也证明这个方法是可以的，但Judge无情的把我TLE了。看来取巧的方法是不行的。
老老实实静下心来，我们不难发现，两个Monster之间的relation可以用一个二进制数表示。第i位为1，就表示relation = relation + (1 / 2^i)。抱歉这段话的内容在做题时是种自发的感觉，所以不知道怎么表达，仔细想想：）
计算两个怪物之间的关系就是把两个relation都往左（右?反正就是让i+1）一位，再加起来。（注意进位哦）
Out的时候数组得到的就是这个01串。如何将这个01串编成最后的浮点数呢？我们不妨找找规律：
{{{
i：0 100% 1 1
i：1 50% 0.5 05
i：2 25% 0.25 025
i: 3 12.5% 0.125 0125
i: 4 0.625 0.0625 00625
……
}}}
这么都就足够了。在数值上 n [ i + 1 ] = n [ i ] * 5。如果 n [ i + 1 ]的第一位比n [ i ] 大，那么i+1其实比i要离小数点远了一位。
初始化的时候写个大数*int（5）的函数，把所有的i位对应的5^i都保存起来。这样没次out的时候，相当于就是做一遍高精度的加法。
问题到这里似乎得到了较为圆满的解决。然而我WA了。WA的我莫名其妙，怀疑测试数据（当一个人接近崩溃时得正常反应），到POJ上交还是WA。
仔细又读了一遍题，发现Monster之间的关系最多可以相差300代（或者是299，298之类的），我的数组越界了，我没有用足够的位数保存 relation的长度，也没有计算足够多的5^i次方。将数组调大，POJ AC。
兴冲冲回到ZOJ上，my god MLE。分析一下，relation数组太大，int a[300][300][300],确实要爆，改成short，仍然爆。无奈只好改成bool型，学着逻辑电路写了个加法器。
终于AC。
----
会java的有福啦，用BigDecimal轻松AC哦。
注意求概率一定要按顺序，简单的记忆化搜索可能是错的，因为calc(parent1[a], a) = calc(parent1[a], parent1[a]) + calc(parent1[a], parent2[a])是对的，但calc(parent1[a], a) = calc(parent1[parent1[a]], a) + calc(parent2[parent1[a]], a)可是错的哦1039
Family
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1509
15 2006-08-19 06:49:43 00:07.79 27716K C++ glimpse
拓扑排序+高精度。
人是种奇怪的小动物。作为一头ws熊，我也这样。没有AC时把这题骂得狗血喷头，AC了就开始教育ZZT，说这是道经典题。或许看别人做题小郁闷时，心里会窃喜，嘎嘎。（大家不要学我哦）
不过AC这道题的旅程真的有点坎坷。我大约在7月29日AC了其余39题，离圆满只有一题之遥。尝试几次之后，终于在20天后鼓足勇气，用了将近8个小时AC掉了它。
题目的描述比较的清楚，相信大家看了一遍都看懂了。OK。有多少人看明白81.5%是怎么算出来的？那就再看一遍题，看看题目里有没有定义？……不用找了，是没有的。全靠你YY。
我自己有始至终都没有YY出。ZZT帮我YY的，两个怪物a,b之间的关系定义如下：
1．如果a == b，那么relation = 100%
2．如果a，b都是天生Monster，那么他们之间的relation = 0
3．relation = (a 和 b 父亲的relation + a 和 b 母亲的relation)/2
我们看一下sample：
1，2都是野生Monster，毫无疑问是0
2和6母亲1的relation的关系为0，2和6的父亲2的relation的关系为100，所以2和6的关系为50%
7和5的关系：5和7的父亲5的relation为100，5和7母亲6的relation为62.5（5和4为25，5和5为 100），所以7和5的relation为81.5%
3和3的relation为100%
弄明白两个怪物之间的血缘计算方法，这个题目就算解决了一半。因为询问的次数比较多并且方便coding，我决定将任意两个怪物之间的relation 都计算出来。
直接写二重循环肯定是不行的。因为还没有理清怪物之间的父子关系，很有可能在计算a,b的时候，a和b父亲的关系还没有计算。
我的方法是先拓扑一下怪物的家谱，然后按照家谱计算怪物之间的关系。设怪物的拓扑顺序在数组ret中
1
2 for( int i = 0 ; i < n; i++ )
3 for( int j = 0; j<=i; j++ )
4 a[ret[i]][ret[j]]=a[ret[j]][ret[i]]=cal(i,j);
5
这样可以保证在计算ret[i]和ret[j]之前，ret[i]和ret[j]父母（如果有）的关系都计算过。
然后根据查询，直接out结果就可以了。
如果题目能够让我们只保留6位小数，到这里就可以AC了。然而变态的题目要求输出一个准确的值。
Double肯定是不行的，也没有大浮点数的类，怎么办呢?伟大的狗狗提供了分数类，只要将分子分母从int改成那个300行的大数，理论上就可以得到正确的解。事实上我做了尝试，也证明这个方法是可以的，但Judge无情的把我TLE了。看来取巧的方法是不行的。
老老实实静下心来，我们不难发现，两个Monster之间的relation可以用一个二进制数表示。第i位为1，就表示relation = relation + (1 / 2^i)。抱歉这段话的内容在做题时是种自发的感觉，所以不知道怎么表达，仔细想想：）
计算两个怪物之间的关系就是把两个relation都往左（右?反正就是让i+1）一位，再加起来。（注意进位哦）
Out的时候数组得到的就是这个01串。如何将这个01串编成最后的浮点数呢？我们不妨找找规律：
i：0 100% 1 1
i：1 50% 0.5 05
i：2 25% 0.25 025
i: 3 12.5% 0.125 0125
i: 4 0.625 0.0625 00625
……
这么都就足够了。在数值上 n [ i + 1 ] = n [ i ] * 5。如果 n [ i + 1 ]的第一位比n [ i ] 大，那么i+1其实比i要离小数点远了一位。
初始化的时候写个大数*int（5）的函数，把所有的i位对应的5^i都保存起来。这样没次out的时候，相当于就是做一遍高精度的加法。
问题到这里似乎得到了较为圆满的解决。然而我WA了。WA的我莫名其妙，怀疑测试数据（当一个人接近崩溃时得正常反应），到POJ上交还是WA。
仔细又读了一遍题，发现Monster之间的关系最多可以相差300代（或者是299，298之类的），我的数组越界了，我没有用足够的位数保存 relation的长度，也没有计算足够多的5^i次方。将数组调大，POJ AC。
兴冲冲回到ZOJ上，my god MLE。分析一下，relation数组太大，int a[300][300][300],确实要爆，改成short，仍然爆。无奈只好改成bool型，学着逻辑电路写了个加法器。
终于AC。
会java的有福啦，用BigDecimal轻松AC哦。
注意求概率一定要按顺序，简单的记忆化搜索可能是错的，因为calc(parent1[a], a) = calc(parent1[a], parent1[a]) + calc(parent1[a], parent2[a])是对的，但calc(parent1[a], a) = calc(parent1[parent1[a]], a) + calc(parent2[parent1[a]], a)可是错的哦