题解

9 条题解

  • 0
    @ 2021-07-23 08:53:10

    好难

  • -1
    @ 2007-11-04 09:08:46

    支持c++无敌。。。

    我说我怎么也想不通呢。。。

    料到了。。。

  • -1
    @ 2007-07-20 21:36:25

    本人对此题数据提出怀疑,尽管我AC了……

    lolanv大牛的做法可能是(本人猜测)先求出每个点是必胜还是必败,输出结点时,首先求出哪些点是可以从1到达的,接下来,若小杉胜则输出其中必胜的结点,否则输出必败的,这大概就是所谓的连通性,但我认为这样做不对(其实我是这样AC的)。

    譬如说第3个数据,6有两个结点可以到达,为2和5,但2是1不能从达到的,而5、6均为必胜态,显然作最优决策不会从必胜走到必胜态,所以小杉不可能到达该结点,但按上述算法结果中却有该结点,所以该算法有误。

    这道题gen了我N久~终于解决了,但结果并不令我满意,郁闷ing……

    不知大家对我的上述说法是否有异议,若有,请与我讨论

    • @ 2014-08-08 10:42:55

      6有两个节点可以到达吗?
      不是只能编号大->小吗

  • -1
    @ 2006-09-07 23:16:36

    图的连通性,博弈树的建立,状态的转移,结束

  • -2
    @ 2008-12-14 23:22:36

    这一题的数据明显有问题,正如C++无敌所说,在从1出发进行DFS的时候如果当前点是必胜点,则从它出发只应该走向必败点,而不应该走向必胜点(总是采用最优决策)。而按照数据来说,只要与1连通的都有可能走到,这当然是错误的。

    这一题只要遍历整个图两次(第一次遍历求出每个点的输赢状态,第二次求出那些点可以从1到达)即可,不会超时的。

  • -2
    @ 2008-10-29 09:59:25

    这个题有什么好的优化方法吗???

    全超时了~

    我的思路是先建立一棵树,叶节点为输,再从下向上递推,如果有必赢的子节点 则必输,除非全部子节点都为必输 才为必赢,然后看第一个节点,看谁赢,如果输了,则输出必输的点,如果赢了,则输出必赢的点。

  • -2
    @ 2008-08-29 21:54:25

    这个难度..

    这个通过率..

  • -2
    @ 2008-08-04 20:22:25

    难度为1

  • -2
    @ 2008-07-17 14:45:24

    额,貌似很难

  • 1

信息

ID
1224
难度
8
分类
博弈论 点击显示
标签
(无)
递交数
170
已通过
18
通过率
11%
被复制
3
上传者