信息学集训队作业0046-heroes

1、题目0046 Heros（英雄）题目来源：ZJU Problem Set 1346推荐者：姜尚仆英文原文Comparing Your HeroesNowadays many students wouldnt attend classes in university, instead, they stay in dormitory playing Electronic games on computers. One of the most popular games among the boys is KOF (the King Of Fighters), a kind of action ga

2、me presented by SNK corporation. This series of games becomes so successful that SNK has even created comics and story for it. Although in the story IORI and KYO are the definitely two strongest heroes, it would not affect players true affection of other characters. Actually, every player has his ow

3、n favorite heroes.As a fanatical fan of the KOF game, youre going to help the other players to find out the ranking of their favorite heroes. Players would only provide information of comparisons between the heroes. This sometimes can lead to confusion: maybe not only one ranking satisfies the compa

4、risons. So at first youd like to find out the number of the rankings that satisfy a specific players comparisons.Input:The input consists of several test cases. Each test case begins with a positive integer N on a line, indicating the number of the comparisons. The following N lines are the comparis

5、ons between the heroes. Each one is a line containing 2 names of the heroes separated by a space, means the player prefer the first hero to the second. The name of the hero is a sequence of at most 10 upper case letters. No two comparisons would be same, and you can always assure ones favorite heroe

6、s would not exceed 16.Output:For each test case, print out the number of the rankings that satisfy the comparisons on a single line. If no such ranking exists, just print out 0.Sample Input:4IORI KYOMARY SHERMIEKYO ANDYSHERMIE ANDY3IORI KYOKYO CLARKCLARK IORISample Output:60中文翻译比较你的英雄许多大学生现在不上课却在宿舍玩

7、电子游戏，KOF是最流行的游戏之一。尽管IORI和KYO毋庸置疑是最强的两个人，但是其他的英雄确是各有所爱。作为一个狂热的KOF迷，你帮助玩家们算出他们心目中英雄的排名。玩家提供了一组英雄两两之间比较的信息。有时这种排名不是唯一的。你的任务就是算出共有几种不同的排名方法。输入每组数据的第一行是比较信息的总数。下面每行有一个比较信息，表示前者在玩家心目中强于后者。输出排名方法的总数。样例heroes.in4IORI KYOMARY SHERMIEKYO ANDYSHERMIE ANDY3IORI KYOKYO CLARKCLARK IORIheroes.out60三、初步讨论情况饶向荣求拓扑排序

8、的个数，好像不能被组合数学解决，暂没什么好方法。侯启明记忆化搜索可以做出来，但怀疑有更好的方法.许智磊原题的规模比较小，所以可用记忆化搜索解决：设整数state对应的二进制串代表了某个人是否出现在已排的队列里，Sstate代表某种state对应的不同排列数，很容易得出Sstate的表达式。但是如果规模比较大了，就不好做了，是否有图论的方法呢？张宁这道题目求的是拓扑排序的序列可能种数，不知道有没有标准算法，当然我们只需分别算每一个连通分量，然后再算排列数刘才良不知道n的规模怎样，如果n的规模很小的话，可以用二进制和动态规划求解。如果搜索的话，也可以用一些公式减少搜索量，比如两条路径分开时，可套用

9、排列组合公式。项荣璟简单的图可以通过一些计数知识求得结果；而对于复杂的图，由于约束条件较多，结果不大，搜索应该是比较快的。邵煊程可以构造有向图，每个人代表一个顶点，如果prefer A to B，则AB（有向边）。如果存在回路，则输出0，否则，只需求有向图的顶点的拓扑序列的数目就可以了。何林题目实际上是求所有可能的拓扑序列数。我记得原题n=12，不知道这里怎么没范围了。要是n=12，用带集合的动态规划就可以。不过不知道有什么好的数学方法。周源这题不会做，但是zju上的原题对总人数N是有限制的：N=16，因此我用的是搜索似的DP，用2N个状态记录某个人是否用过，然后就很容易了。王知昆设s为一个h

10、eroes的集合，f(s)表示前|s|个位置放s中的元素的方案数，这样状态数为2n（n为heroes个数），转移时间为n，所以总的时间复杂度是O(n*2n)，空间复杂度为O(2n)，可以在0.00sec内出解林希德利用二进制压缩的DP，可以在空间692K、时间00:00.00s（Zju系统评测结果）内出解。只是该算法仍然是NP，没有将问题彻底解决。Ax：将强于x的英雄集合进行二进制压缩后得到的整数；Gx：将前k位英雄进行二进制压缩得到整数x时的排名总数；易知，G2n-1 = 1，Gx = Gx+2i-1（其中2i-1&x = 0并且Ax&(2n-1-x) = 0） 这里的&是非常快的位操作，可以在O(1)时间内判断英雄i是否可以放在当前尝试安放的位置，因此就该问题而言，复杂度只有O(n2n)。金恺 建图：每个英雄看作一个节点，若i强于j，则添加有向边ij；求拓扑排序的个数。对于任意的这样有向图我没有想出好的算法，但是当这个有向图是棵树那么可以用组合数学做出来；如果有环的话输出0。如果搜索的话也有许多优化：1若i j, j k, i k，则可以删去i k；2若可将图分为互无联系的两部分（连通分量）则可以用组合数学：设两部分节点个数、拓扑序列个数分别为a,b,ta,tb，则合起来的拓扑序列个数为：；3若此图能够分成两部分和一